[petsc-dev] LLCondensed work

[Barry Smith]

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

   Wikipedia sucks for all sort/search algorithms; there is no discussion/mention of what happens with duplicate keys at all.  We have many many duplicates that must be eliminated.

   Note that the result is always generated as the merging of "a bunch of sorted lists", thus an algorithm that takes advantage of the sorted nature seems advantages. I tried a heap based scheme but that ended up being useless because of the duplicate issue.

   Barry

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