Hallo,

one of our students looked at the performance of the cholesky decomposition
using ublas. The result is quite surprising:

$ for i in 100 200 400 800 1600; do ./cholesky_test $i ; done
0: 0 (deco: 0 sec) (prod: 0.02 sec) 100
0: 0 (deco: 0.01 sec) (prod: 0.01 sec) 100
0: 0 (deco: 0 sec) (prod: 0.01 sec) 100

0: 0 (deco: 0.03 sec) (prod: 0.13 sec) 200
0: 0 (deco: 0.06 sec) (prod: 0.06 sec) 200
0: 0 (deco: 0.02 sec) (prod: 0.01 sec) 200

0: 0 (deco: 0.18 sec) (prod: 1.03 sec) 400
0: 0 (deco: 0.43 sec) (prod: 0.41 sec) 400
0: 0 (deco: 0.03 sec) (prod: 0.03 sec) 400

0: 0 (deco: 1.56 sec) (prod: 8.14 sec) 800
0: 0 (deco: 3.42 sec) (prod: 3.22 sec) 800
0: 0 (deco: 0.09 sec) (prod: 0.05 sec) 800

0: 0 (deco: 12.28 sec) (prod: 65.42 sec) 1600
0: 0 (deco: 26.68 sec) (prod: 25.48 sec) 1600
0: 0 (deco: 0.28 sec) (prod: 0.09 sec) 1600

The table lists the times for performing the cholesky decomposition of
different matrix types and sizes. The first line of each block shows the
decomposition time of a dense matrix (only accessing the lower triangle). The
second line uses a (lower) triangular_matrix. This should at least be as fast
as the dense case but takes 3 times as long. The third line show the times
for a banded matrix with (at most) 50 bands below the diagonal. (If the
banded matrix has all maximal possible bands it is even slower than the
triangular matrix.)

I suspect the matrix rows/columns and vector ranges to be the source of the
slow down. So I have to do more research on that.

see http://www.bauv.unibw-muenchen.de/~winkler/ublas/examples/

Do you have an idea how to reduce the slow down?

mfg
Gunter