[petsc-dev] LLCondensed work

[Matthew Knepley]

On Mon, Dec 19, 2011 at 11:01 PM, Barry Smith <bsmith at mcs.anl.gov> wrote:

>
>   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.


My understanding of the GNU sort utility is that the last step does just
this. They sort many streams (16 by default)
and then merge the outputs, I believe with a priority queue. We should look
at the source code. This had to be
rewritten at Akamai to drastically increase the number of streams since our
problem was so large.

   Matt


>
>   Barry
>
>
> On Dec 19, 2011, at 9:30 PM, Matthew Knepley wrote:
>
> > I looked at the new checkins for fast MatMatSym. It looks to me like you
> want a data
> > structure that has
> >
> >   a) O(N) space, where N is the number of entries
> >
> >   b) fast insert
> >
> >   c) fast traversal
> >
> > It seems like the best data structure of this is
> >
> >    http://en.wikipedia.org/wiki/Y-fast_trie
> >
> > It has O(N) space, and O(log log M) where M is the maximum key size. It
> basically
> > uses prefix compression on the bitwise representation of the keys, so
> that runs of
> > consecutive integers are handled well.
> >
> > So far, I cannot find any free implementations.
> >
> >    Matt
> >
> > --
> > What most experimenters take for granted before they begin their
> experiments is infinitely more interesting than any results to which their
> experiments lead.
> > -- Norbert Wiener
>
>


-- 
What most experimenters take for granted before they begin their
experiments is infinitely more interesting than any results to which their
experiments lead.
-- Norbert Wiener
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20111220/cfd0f92e/attachment.html>