Brian McCandless wrote:
>
> Hello All,
>
> I have an application that spends nearly all its time in a generalize
> eigenvalue problem with very large (say 10-20 million rows)
> and very sparse (either ~16 or ~44 non zeros per row) matrices.
> [note: my colleagues with the ASCI project will probably object to me
> calling
> these matrices "very large"].
>
> I currently use Aztec from Sandia (written mostly in C) for
> both the storage format (modified sparse compressed row)
> and the iterative methods. In the latest versions of Aztec, there is
> a matrix free interface that permits the application writer to supply
> their own
> storage formats and matrix vector multiplication routines.
Do you only solve an Eigenvalue Problem or do you
solve linear systems too?
Did you try ARPACK/ARPACK++ (http://www.caam.rice.edu/software/ARPACK/)
for the eigenproblem? The IMPLICIT restarting implemented in this
software
may save you a lot of iteration (and consequently a lot of sparse matrix
product)
>
> I plan to use this matrix free interface in order to support
> symmetric matrices in my application (currently not supported
> directly in Aztec). I am doing this mainly to save on memory.
> But while I'm at it, I would also like to improve performance.
> Here are my questions:
>
> 1. What is the "best" storage format for sparse matrices to get the most
> efficient matrix vector multiplication? Or does the format not matter so
> much compared to the sparsity pattern.
>
> 2. My impression is the with sparse matrix multiplication the language
> doesn't matter (Fortran has no advantage over C, like it does wit
> dense linear algebra). Is this impression correct?
This is another thread (OON: Comparison between Fortran & C++)
but Fortran vs C/C++ war is more a matter of
taste as soon as you use state of the art libraries.
Moreover if you use libraries (I mean you don't code it yourself)
you may easilly use Fortran lib from C/C++ or C lib from
Fortran.
(using C++ lib from Fortran may need more effort).
>
> 3. I am planning to reorder the matrices, using something like Reverse
>
> Cuthill-McKee (RCM), to reduce the bandwidth of the matrices.
> My hope is that this will reduce cache misses and improve performance.
> Will this reordering have a significant impact? (I know this is impossible
> to answer in general, but I would like to hear people's opinions).
I am a bit surprised here since reordering the matrix will change both
the spectrum and the corresponding eigenspace, unless your reordering
make A_reordered similar to A (eigenvectors are changed but not the
eigenvalues).
If this reodering is made for linear system solving then this is
different,
and you may have a look at (Par)METIS library:
http://www-users.cs.umn.edu/~karypis/metis/
>
> 4. Has anyone had success with any other tricks to make the matrix vector
> multiplication faster?
You didn't mentionned if it was parallel run or not? (I don't no much
of the features
of Aztec)
You may first verify that your long eigenvalue solve is really bounded
by
the number (and time) of the sparse matrix product.
If it is parallel and sparse matrix product bounded you may verify that
the sparse matrix/vector product is Communication bounded. If this is
the case:
1) reorder the matrix to minimize communication (Only for Linear
System)
2) Try to plot the sparsity pattern and find a better distribution of
you sparse matrix in order to minimize communication
or
make communication/computation to overlap.
Would you be able to give me your matrices?
(as a file or programs that does matrix product)
I'm developping a prototype library for iterative eigenvalue solvers,
it doesn't solve general eigenvalue problem for now but I may be
interested in
your test case.
--
Eric NOULARD
-------------------------------------------------------------------
Groupe ADULIS * Laboratoire PRiSM
Tel: +33 1 69 59 26 66 * Tel: +33 1 39 25 40 71
Fax: +33 1 64 46 29 59 * Fax: +33 1 39 25 40 57
E-mail: E.Noulard@adulis.fr * E-mail: Eric.Noulard@prism.uvsq.fr
--------------------- Object Oriented Numerics List --------------------------
* To subscribe/unsubscribe: use the handy web form at
http://oonumerics.org/oon/
* If this doesn't work, please send a note to owner-oon-list@oonumerics.org
This archive was generated by hypermail 2b29 : Mon Apr 10 2000 - 12:47:56 EST