Re: [ublas] Element-wise operations are really slow

Subject: Re: [ublas] Element-wise operations are really slow
From: Gunter Winkler (guwi17_at_[hidden])
Date: 2010-04-28 17:06:17

Hello xiss,

I still cannot agree with you numbers.

Am Wednesday 28 April 2010 schrieb xiss burg:
> Gunter,
>
> Actually I got confused because you said both push_back and
> append_element. Anyway, I tried both. append_element is 100 times
> slower than an ublas::matrix with +=s. I don't know what I'm doing
> wrong (sorry if there's something really stupid there). Please take a
> look at the source attached.

I slightly modified your example an get the following timings on my 
machine (AMD Athlon(tm) 64 X2 Dual Core Processor 4800+)

$ g++ -DNDEBUG -O2 -I /home/gw/include/ -o fetest assemble_femat.cpp
$ ./fetest 
numNodes       : 200
numTetrahedrons: 800
GVOV with COO-vector
time elapsed: 0.03
COO-matrix
time elapsed: 0.09
CRS-matrix
time elapsed: 5
dense-matrix
time elapsed: 0.01
gvov - coo: 3.57628e-06
gvov - crs: 3.09944e-06
crs  - coo: 2.68221e-06

and 

numNodes       : 400
numTetrahedrons: 1600
GVOV with COO-vector
time elapsed: 0.12
COO-matrix
time elapsed: 0.19
CRS-matrix
time elapsed: 33.78
dense-matrix
time elapsed: 0.01
gvov - coo: 4.47035e-06
gvov - crs: 3.8743e-06
crs  - coo: 3.63588e-06

and finally

numNodes       : 4000
numTetrahedrons: 16000
GVOV with COO-vector
time elapsed: 0.6
COO-matrix
time elapsed: 2.18
CRS-matrix
skipped due to size
dense-matrix
time elapsed: 0.83
gvov - coo: 3.8594e-06

So I still believe that the sparse types have a comparable performance. 
Of course you have to take some special care when you are dealing with 
very large matrices. So you should try to fill the matrix from top to 
bottom (or only fill half of the matrix when it is symmetric). 
Additionally the asymptotic costs of the different sparse matrices 
differ.
The filling of a sparse matrix is by design always slower than for a 
dense matrix (and it is quite possible to have a factor of 10 for 
single operations). However this must be compared to the better 
complexity because sparse operations should be O(nnz) or maybe 
O(log(n)*nnz). Operations on dense types usually have the complexity 
O(n) or worse. Thus it makes only little sense to compare sparse and 
dense algorithm for small matrices.

numNodes       : 32000
numTetrahedrons: 128000
GVOV with COO-vector
time elapsed: 4.96
COO-matrix
time elapsed: 19.74

BTW: If you really want to solve big FE problems, then you should think 
about using a specialized package, e.g., http://www.dealii.org/
(more links on 
http://homepage.usask.ca/~ijm451/finite/fe_resources/node138.html )

mfg
Gunter