Re: [ublas] Worst case time complexity of ublas::compressed_matrix operations?

From: Paul C. Leopardi (paul.leopardi_at_[hidden])
Date: 2007-01-24 07:05:30

Dear Gunter,
I have appended the results of the test below, with my processor details.
I'm running SUSE Linux 10.1.
Best, Paul

On Wednesday 24 January 2007 10:11, Gunter Winkler wrote:
...
> can you also try
>
> #include <boost/numeric/ublas/vector_of_vector.hpp>
>
> generalized_vector_of_vector< double, row_major, vector< X > >
>
> with X = compressed_vector<double>, coordinate_vector<double>,
> mapped_vector<double>

Dense: ublas::matrix
Matrix addition test:
Dim =     4, CPU =         0.00; Inner product = 0; Fill = 0.5
Dim =     8, CPU =         0.00; Inner product = 0; Fill = 0.5
Dim =    16, CPU =         0.00; Inner product = 0; Fill = 0.5
Dim =    32, CPU =         0.01; Inner product = 0; Fill = 0.5
Dim =    64, CPU =         0.04; Inner product = 0; Fill = 0.5
Dim =   128, CPU =         0.14; Inner product = 0; Fill = 0.5
Dim =   256, CPU =         0.59; Inner product = 0; Fill = 0.5
GVV Mapped: ublas::generalized_vector_of_vector<vector<mapped_vector<double> > 
>
Matrix addition test:
Dim =     4, CPU =         0.00; Inner product = 0; Fill = 0.5
Dim =     8, CPU =         0.01; Inner product = 0; Fill = 0.5
Dim =    16, CPU =         0.07; Inner product = 0; Fill = 0.5
Dim =    32, CPU =         0.29; Inner product = 0; Fill = 0.5
Dim =    64, CPU =         1.16; Inner product = 0; Fill = 0.5
Dim =   128, CPU =         6.80; Inner product = 0; Fill = 0.5
Dim =   256, CPU =        27.00; Inner product = 0; Fill = 0.5
GVV Compressed: 
ublas::generalized_vector_of_vector<vector<compressed_vector<double> > >
Matrix addition test:
Dim =     4, CPU =         0.01; Inner product = 0; Fill = 0.5
Dim =     8, CPU =         0.02; Inner product = 0; Fill = 0.5
Dim =    16, CPU =         0.05; Inner product = 0; Fill = 0.5
Dim =    32, CPU =         0.17; Inner product = 0; Fill = 0.5
Dim =    64, CPU =         0.54; Inner product = 0; Fill = 0.5
Dim =   128, CPU =         1.83; Inner product = 0; Fill = 0.5
Dim =   256, CPU =         7.29; Inner product = 0; Fill = 0.5
GVV Coordinate: 
ublas::generalized_vector_of_vector<vector<coordinate_vector<double> > >
Matrix addition test:
Dim =     4, CPU =         0.01; Inner product = 0; Fill = 0.5
Dim =     8, CPU =         0.02; Inner product = 0; Fill = 0.5
Dim =    16, CPU =         0.08; Inner product = 0; Fill = 0.5
Dim =    32, CPU =         0.22; Inner product = 0; Fill = 0.5
Dim =    64, CPU =         0.69; Inner product = 0; Fill = 0.5
Dim =   128, CPU =         2.37; Inner product = 0; Fill = 0.5
Dim =   256, CPU =         9.60; Inner product = 0; Fill = 0.5
Mapped: ublas::mapped_matrix
Matrix addition test:
Dim =     4, CPU =         0.01; Inner product = 0; Fill = 0.5
Dim =     8, CPU =         0.03; Inner product = 0; Fill = 0.5
Dim =    16, CPU =         0.09; Inner product = 0; Fill = 0.5
Dim =    32, CPU =         0.35; Inner product = 0; Fill = 0.5
Dim =    64, CPU =         1.36; Inner product = 0; Fill = 0.5
Dim =   128, CPU =         7.80; Inner product = 0; Fill = 0.5
Dim =   256, CPU =        33.03; Inner product = 0; Fill = 0.5
Compressed: ublas::compressed_matrix
Matrix addition test:
Dim =     4, CPU =         0.01; Inner product = 0; Fill = 0.5
Dim =     8, CPU =         0.02; Inner product = 0; Fill = 0.5
Dim =    16, CPU =         0.04; Inner product = 0; Fill = 0.5
Dim =    32, CPU =         0.36; Inner product = 0; Fill = 0.5
Dim =    64, CPU =         4.83; Inner product = 0; Fill = 0.5
Dim =   128, CPU =       113.33; Inner product = 0; Fill = 0.5
Dim =   256, CPU =      2160.00; Inner product = 0; Fill = 0.5
Coordinate: ublas::coordinate_matrix
Matrix addition test:
Dim =     4, CPU =         0.01; Inner product = 0; Fill = 0.5
Dim =     8, CPU =         0.06; Inner product = 0; Fill = 0.5
Dim =    16, CPU =         0.54; Inner product = 0; Fill = 0.5
Dim =    32, CPU =         8.10; Inner product = 0; Fill = 0.5
Dim =    64, CPU =       220.00; Inner product = 0; Fill = 0.5
Dim =   128, CPU =      4410.00; Inner product = 0; Fill = 0.5
Dim =   256, CPU =    132100.00; Inner product = 0; Fill = 0.5

leopardi_at_linfinit:~/src/test_add> cat /proc/cpuinfo
processor       : 0
vendor_id       : AuthenticAMD
cpu family      : 15
model           : 4
model name      : AMD Athlon(tm) 64 Processor 3200+
stepping        : 8
cpu MHz         : 800.000
cache size      : 1024 KB
fpu             : yes
fpu_exception   : yes
cpuid level     : 1
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca 
cmov pat pse36 clflush mmx fxsr sse sse2 syscall nx mmxext lm 3dnowext 3dnow
bogomips        : 1609.06
TLB size        : 1024 4K pages
clflush size    : 64
cache_alignment : 64
address sizes   : 40 bits physical, 48 bits virtual
power management: ts fid vid ttp