[petsc-dev] LLCondensed work

[Barry Smith]

 The use of PetscBT always makes the algorithm unscalable. It works fine even for large max index because it only uses on bit per max index but eventually even that is not scalable so for moderate sizes likely using PetscBT is good, but super large sizes needs to be avoided.

    Barry


On Dec 20, 2011, at 1:03 PM, Matthew Knepley wrote:

> On Mon, Dec 19, 2011 at 10:54 PM, Barry Smith <bsmith at mcs.anl.gov> wrote:
> 
> 
> 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.
> 
> Okay, so you want fast Merge-wo-Duplicates and Traverse. To summarize
> 
> Option 1: What is currently there
> 
>   Merge-wo-Duplicates:
> 
>     A Fortran-style linked list is used to hold the indices, a PetscBT (bitmap) is used to check for membership.
> 
>     The indices are pushed in one-by-one, checking the BT each time
> 
>  Option 2: Brain dead
> 
>     Put values directly after current values and sort in place
> 
>   Option 3: Traditional
> 
>     Put values directly after and merge in place (std::inplace_merge)
> 
> Both 2 and 3 are not taking account of duplicates. I see at least three ways to do this:
> 
>   1) Use a PetscBT and ignore duplicates in the input array
> 
>   2) Use a PetscBT and squish duplicates out of the output array (prob too much data movement)
> 
>   3) Ignore duplicates on traversal. This would be fast, its just a question of the memory overhead
> 
>      Matt
>  
> 
>   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
> 
> 
> 
> 
> -- 
> 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