|
|
Ublas : |
From: Paul C. Leopardi (paul.leopardi_at_[hidden])
Date: 2007-01-21 03:04:56
Hi all,
Is the worst case time complexity of ublas::compressed_matrix operations
documented anywhere? For addition of square matrices where each of the
operands is half full with no non-zeros in common, using operator+=
from Boost 1.33.0 and 1.33.1, I'm getting about O(dim^2) for ublas::matrix and
about O(nnz * dim^2) for ublas::compressed_matrix. Is this what should be
expected in this case? Is it the worst case?
Can the algorithm for operator+= for ublas::compressed_matrix be improved, or
is it up to the user (ie. me) to find and use a faster algorithm? Or should
the user just give up on using ublas::compressed_matrix when nnz > O(dim) ?
Results follow. The test code is atteched.
Best regards, Paul
leopardi_at_linfinit:~/src/test_add>
g++ -I../boost/boost_1_33_0 -Wall -ansi -DNDEBUG -O3 -o test_add_1_33_0
test_add.cpp
leopardi_at_linfinit:~/src/test_add>
g++ -I../boost/boost_1_33_1 -Wall -ansi -DNDEBUG -O3 -o test_add_1_33_1
test_add.cpp
leopardi_at_linfinit:~/src/test_add> ./test_add_1_33_0 9
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.01; Inner product = 0; Fill = 0.5
Dim = 32, CPU = 0.02; Inner product = 0; Fill = 0.5
Dim = 64, CPU = 0.08; Inner product = 0; Fill = 0.5
Dim = 128, CPU = 0.26; Inner product = 0; Fill = 0.5
Dim = 256, CPU = 0.78; Inner product = 0; Fill = 0.5
Dim = 512, CPU = 2.79; 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.01; Inner product = 0; Fill = 0.5
Dim = 16, CPU = 0.07; Inner product = 0; Fill = 0.5
Dim = 32, CPU = 0.44; Inner product = 0; Fill = 0.5
Dim = 64, CPU = 5.15; Inner product = 0; Fill = 0.5
Dim = 128, CPU = 110.00; Inner product = 0; Fill = 0.5
Dim = 256, CPU = 2170.00; Inner product = 0; Fill = 0.5
Dim = 512, CPU = 86790.00; Inner product = 0; Fill = 0.5
leopardi_at_linfinit:~/src/test_add> ./test_add_1_33_1 9
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.00; Inner product = 0; Fill = 0.5
Dim = 64, CPU = 0.07; Inner product = 0; Fill = 0.5
Dim = 128, CPU = 0.28; Inner product = 0; Fill = 0.5
Dim = 256, CPU = 1.11; Inner product = 0; Fill = 0.5
Dim = 512, CPU = 2.77; 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.01; Inner product = 0; Fill = 0.5
Dim = 16, CPU = 0.05; Inner product = 0; Fill = 0.5
Dim = 32, CPU = 0.38; Inner product = 0; Fill = 0.5
Dim = 64, CPU = 4.90; Inner product = 0; Fill = 0.5
Dim = 128, CPU = 108.89; Inner product = 0; Fill = 0.5
Dim = 256, CPU = 2150.00; Inner product = 0; Fill = 0.5
Dim = 512, CPU = 88420.00; Inner product = 0; Fill = 0.5