[petsc-dev] LLCondensed work

[Matthew Knepley]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20111220/55545567/attachment.html>