[petsc-dev] use of hash table vs array in various places in PETSc

[Dmitry Karpeev]

On Mon, Sep 19, 2011 at 8:31 PM, Barry Smith <bsmith at mcs.anl.gov> wrote:

>
> On Sep 19, 2011, at 6:11 PM, Jed Brown wrote:
>
> > On Tue, Sep 20, 2011 at 01:05, Barry Smith <bsmith at mcs.anl.gov> wrote:
> >
> > On Sep 19, 2011, at 4:47 PM, Jed Brown wrote:
> >
> > > On Mon, Sep 19, 2011 at 23:29, Mark F. Adams <mark.adams at columbia.edu>
> wrote:
> > > An alternative to a virtual function is changing the hash table code:
> > >
> > > #define HASH_FACT 79943
> > > #define HASHT(ta,x) ((unsigned long)((HASH_FACT*(unsigned
> long)x)%ta->tablesize))
> > >
> > > and make HASH_FACT a variable.  Set HASH_FACT  to 1 if you want an
> array (and thus the index (x) is less than the table size tablesize).  The
> index x is one based so the hash function should modified:
> > >
> > > #define HASHT(ta,x) ((unsigned long)((HASH_FACT*(unsigned
> long)(x-1))%ta->tablesize))
> > >
> > > This is an interesting idea. Storage is still double the array, but I
> think the cases where we want a dense array will generally not be so space
> limited.
> >
> >  It may very well be limiting with MatGetSubMatrix() for VI solvers. In
> fact we may need yet a different approach to make the MatGetSubMatrix()
> itself memory scalable for very large problems; that is rather than doing an
> ISAllGather on the columns it has to be smart about knowing what processes
> need to know about what columns based on the sparsity of the matrix.
> >
> >
> > Oh, you're working with the global column space? That explains why it's
> so expensive. This gather is a problem in PCFieldSplit too unless you use
> MatNest (which should be easy now). VI doesn't have that luxury, so
> MatGetSubMatrix() needs to get a scalable implementation. Didn't we talk
> about this several months ago and Dmitry started writing code for it?
>
>     I am not aware of Dmitry writing code for this nor use talking about it
> :-)
>

I have code that handles similar, but not identical, issues for GASM.
It's possible that it could be adapted for MatGetSubMatrix.

>
> > How did that turn out?
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.mcs.anl.gov/pipermail/petsc-dev/attachments/20110920/c073fa5a/attachment.html>