[petsc-dev] LLCondensed work

[Jed Brown]

On Mon, Dec 19, 2011 at 19:30, Matthew Knepley <knepley at gmail.com> 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.
>

Do you have a reference showing that the constants are decent?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20111219/1eebd295/attachment.html>