[boost] [ublas] Weakness in large sparse matrices

From: Johan Jansson (johanjan_at_[hidden])
Date: 2003-02-07 14:13:32

Hi,

I've done some testing of matrix representations to decide what we're
going to use for a project, and I get strange results with uBLAS. What
we need is efficient memory usage, fast large sparse matrix assembly
(insertion speed) and fast large sparse matrix-vector multiply. Large here
means on the order n = 1e6.

Let's look at just assembly for now. We start by creating an 1e5 x 1e5
sparse matrix.  We then successively insert 1e5 elements in the diagonal.
What happens is that the insertion speed is linear for the first ~50000
elements, and then grinds to a halt. The initial insertion speed is
somewhere at 1e5 elements/s, after 50000 elements it sharply falls to
1000 elements/s (to compare, our naive implementation gets 1e6 elements /
s).

This is quite bizarre.

With an 1e6 x 1e6 matrix, the insertion speed is smoother, but slow
throughout (on the order 1000 elements / s).

I've tested this on two different computers, one dual Athlon and one PII
laptop, and the result is identical (aside from the absolute speed
numbers). Memory is not at all full, so that can't be an issue.

The code for this simple test is at the end.

The compiler used was g++-2.95 (in Debian) and Boost 1.29 (also Debian).

I've also observed a quadratic time complexity (in the non-zero elements)
in sparse matrix-vector multiplication. I think this has been brought up
before though.

We've also tested MTL, and while it doesn't produce these kinds of wild
irregularities, the performance is a factor 2 or 3 worse than our naive
implementation, and the memory usage is a factor 1.5-2 worse.

This makes me question the claim that genericity does not add overhead (in
practice). 10-20% overhead is acceptable, but when we have 100-200%
overhead, both in performance and memory, then it makes it impossible to
justify its use.

  Johan

-- CUT --

#include <iostream>
#include <boost/numeric/ublas/matrix_sparse.hpp>

#define N 100000

using namespace boost::numeric::ublas;
namespace ublas = boost::numeric::ublas;

typedef ublas::sparse_matrix<double> uBLASSparseMatrix;
typedef ublas::vector<double> uBLASVector;

int main()
{
  cout << "Creating a " << N << " x " << N << " matrix" << endl;
  uBLASSparseMatrix A(N, N);

  cout << "Assembling" << endl;
  for (int i = 0; i < N; i++) {

    A(i,i) = 1.0;

    if(i % 1000 == 0)
      cerr << "i: " << i << endl;
  }
}

-- CUT --