[petsc-dev] LLCondensed work

[Barry Smith]

   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.

   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