Efficiently solving sparse matrices

Question

For solving spare matrices,

in general, how big does the matrix have to be (as a rule of thumb)

for methods like congraduate descent to be faster than brute force solvers (that do not take advantage o sparsity)?

Answer 1

I'm not sure that your dichotomy between conjugate gradient solvers and 'brute force' solvers is useful. CG, for instance, can be applied to both dense and sparse matrices. You might find this book helpful.

Answer 2

It depends not only on the size of the matrices, but also how sparse they are, and what sparseness structure they have. Obviously, you can solve a tridiagonal system much faster than a system with the same number of non-zero entries distributed randomly through the matrix.

As High-Performance Mark noted, CG works for dense matrices as well as sparse, so the question you want to ask is something more along the lines of "how large and how sparse does a matrix need to be before solvers can benefit from treating it as a sparse matrix instead of a dense matrix that happens to have a lot of zeros".

The answer to this depends, as I noted, on the sparseness structure. A matrix with no special structure that's 10% full, as a first guess, I would use dense methods until the matrix filled cache (on modern commodity hardware, that's going to be around 1000 x 1000). If the matrix is dramatically sparser, or has some special structure that makes it easier to work with (dense blocks of non-zero data, or some band structure, for example), then that threshold will become much smaller.

Can you give us more information about the specific problem that you're working with?