On Mon, Dec 19, 2011 at 11:01 PM, Barry Smith <span dir="ltr"><<a href="mailto:bsmith@mcs.anl.gov">bsmith@mcs.anl.gov</a>></span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
   Note that this same operation (merging collections of sorted integers) is also needed for factorization so having a solid toolkit of different algorithms that perform this well for different size problems and different levels of sparsity would be a useful thing in PETSc.</blockquote>
<div><br></div><div>My understanding of the GNU sort utility is that the last step does just this. They sort many streams (16 by default)</div><div>and then merge the outputs, I believe with a priority queue. We should look at the source code. This had to be</div>
<div>rewritten at Akamai to drastically increase the number of streams since our problem was so large.</div><div><br></div><div>   Matt</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<span class="HOEnZb"><font color="#888888"><br>
   Barry<br>
</font></span><div class="im HOEnZb"><br>
<br>
On Dec 19, 2011, at 9:30 PM, Matthew Knepley wrote:<br>
<br>
</div><div class="HOEnZb"><div class="h5">> I looked at the new checkins for fast MatMatSym. It looks to me like you want a data<br>
> structure that has<br>
><br>
>   a) O(N) space, where N is the number of entries<br>
><br>
>   b) fast insert<br>
><br>
>   c) fast traversal<br>
><br>
> It seems like the best data structure of this is<br>
><br>
>    <a href="http://en.wikipedia.org/wiki/Y-fast_trie" target="_blank">http://en.wikipedia.org/wiki/Y-fast_trie</a><br>
><br>
> It has O(N) space, and O(log log M) where M is the maximum key size. It basically<br>
> uses prefix compression on the bitwise representation of the keys, so that runs of<br>
> consecutive integers are handled well.<br>
><br>
> So far, I cannot find any free implementations.<br>
><br>
>    Matt<br>
><br>
> --<br>
> What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>
> -- Norbert Wiener<br>
<br>
</div></div></blockquote></div><br><br clear="all"><div><br></div>-- <br>What most experimenters take for granted before they begin their experiments is infinitely more interesting than any results to which their experiments lead.<br>
-- Norbert Wiener<br>