> -----Original Message-----
> From: owner-oon-list@oonumerics.org
> [mailto:owner-oon-list@oonumerics.org]On Behalf Of Brian McCandless
> Sent: Tuesday, April 04, 2000 3:44 PM
> To: oon-list@oonumerics.org
> Subject: OON: How do I make sparse linear algrebra faster?
>
> 4. Has anyone had success with any other tricks to make the matrix
> vector
> multiplication faster?
>
You might try the following:
1. Store the non-zeroes of the matrix in one huge vector, put all the
diagonal entries first, followed by all the off-diagonals.
2. Split the matrix/vector multiply operation into two parts. First, take
the product of only the diagonal entries with the vector; second, perform
the multiplication of the off-diagonals with the corresponding entries of
the vector and sum into the first result.
This strategy might be fast because the first phase of the multiply is
traversing through three vectors with stride 1, some loop unrolling might
help here. The second phase is the slower part, but as you said, some
reordering of the matrix entries would help. If the matrix is symmetric, the
second phase of operations on the lower/upper triangle could be combined.
Have fun.
As for re ordering the entries, in addition to the Metis library, take a
look at
SPOOLES.
http://netlib.bell-labs.com/netlib/linalg/spooles/index.html
________________________________________________
Kevin Copps Voice: (409) 845-0745
Texas A&M University Fax: (409) 845-6051
Aerospace Engineering MS3141
College Station TX 77843 kc@isc.tamu.edu
________________________________________________
--------------------- 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 : Wed Feb 20 2002 - 03:20:12 EST