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
