[petsc-users] Algorithms for counting nonzeros!

[Jed Brown]

Eric Chamberland <Eric.Chamberland at giref.ulaval.ca> writes:

> Hi all,
>
> we are in the process of adding new functionalities to our parallel 
> finite-element code and are facing new challenges in computing the 
> number of non-zeros of a sparse matrix.  Since we use Petsc, we want to 
> be able to give this information before the first assembly (to pass to 
> Mat{MPI,SEQ}AIJSetPreallocation).
>
> Willing to rewrite the nonzeros counting algorithm from scratch if 
> necessary, we asked ourselves a number of questions:
>
> 1) Do algorithms in general count the *exact* number of non-zeros?  or 
> do they just count a maximum and let Petsc release the memory after the 
> first assembly?

PETSc does not currently use "realloc" to shrink the allocation size.
It does, however, compress the used entries up into the top of the
array, so the unused part is harmless except insofar as it has been
allocated.

PETSc developers: we have discussed realloc() in the past and never
added it.  It would be useful and fairly harmless in this case, since
using it does not increase the peak memory usage.  It's still important
to allocate precisely if you want to be able to use huge pages or run on
a system without virtual memory (like Blue Gene), but for normal users,
realloc would allow them to allocate twice as much as they will need
without consequences (preallocation/assembly comes before preconditioner
setup).

> 2) How bad is it to reserve too-much non-zeros before the first assembly?
>
> 3) Where could we find some hints/articles examples or information about 
> that kind of algorithm (working in parallel of course) ?

Here is a clever strategy that often works.

http://mail-archive.com/search?l=mid&q=3BEF7FCC-AF4A-461A-B068-9DB01EF94B7A@mcs.anl.gov
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 835 bytes
Desc: not available
URL: <http://lists.mcs.anl.gov/pipermail/petsc-users/attachments/20131113/e8bc55f6/attachment-0001.pgp>