Re: solving it fast

Hi -- One quick comment on sparse matrix-vector multiply.  If you are  
multiplying a large sparse matrix (larger than cache), the limiting  
factor in performance is going to be memory bandwidth -- there is no  
opportunity for data reuse in matrix-vector product (unlike  
matrix-matrix product where there is lots of reuse).  No algorithm  
tweaking can speed up large sparse matrix-vector product (assuming your  
compiler has applied all expected optimizations).  Most desktops have a  
memory bandwidth around 5% of CPU peak.  One can play some games with  
reordering the sparse matrix for smaller bandwidth (and get a bit of  
reuse in accessing the vector) using RCM or self-avoiding walk  
approaches.

(See for instance the paper by Gropp, Kaushik, Keyes, and Smith  
http://www-unix.mcs.anl.gov/~kaushik/Papers/pcfd99_gkks.pdf).

Cheers,
Andrew Lumsdaine

On Apr 1, 2005, at 8:26 AM, Janusz opechowski wrote:

> Well,
> grats!
>
>
>
> How about using MKL ( intel's tuned lapack ).
> In Matrix*Matrix  it is fast (the code is it SEM ? ).
> so might be in :
> SparseMatrix * Vector
>
> Is it possible to build a matrix object that will use
> some well (vendor) tuned procedures instead of
> standard mtl when multiplying SM * V in bccg ?
>
> ( or ... write own bccg ? )
> please inform me if any.
> Soon I will have same problems.
>
> Regards
> JO
>
>
>
> --- Michael Nielsen <[email protected]> wrote:
>> I've implemented a finite element solver using cg()
>> in the ITL framework. I
>> expected it to be a bit faster, it's only as fast as
>> my "head on"
>> implementation i did. I've pretty much done it like
>> in the example for
>> conjugate gradient on the homepage, using these
>> types:
>>
>> typedef dense1D<float> vector;
>>
>> typedef matrix<float, symmetric<upper>,
>> compressed<>, row_major>::type
>> sparseSymmetricMatrix;
>>
>>
>>
>> Is it the fastest way using ITL?
>>
>>
>>
>> /Michael
>>
>>
>>
>>
>> _______________________________________________
>> This list is archived at
>> http://www.osl.iu.edu/MailArchives/mtl-devel/
>> dear
>
> _______________________________________________________________________ 
> _
> Yahoo! Messenger - Communicate instantly..."Ping"
> your friends today! Download Messenger Now
> http://uk.messenger.yahoo.com/download/index.html
> _______________________________________________
> This list is archived at http://www.osl.iu.edu/MailArchives/mtl-devel/

_______________________________________________
This list is archived at http://www.osl.iu.edu/MailArchives/mtl-devel/