mldivide with sparse matrix

Hi,

I need to solve large sparse system of linear equations A*x=b. A is a sparse matrix, but b is vector which has only few zero entries. The question is, regarding memory consumption, when I call

   mldivide(A,b)

when A is sparse matrix and b is full vector, will matlab internally transform A into full matrix and solve the system, or handle it like sparse.

Thanks! K

Answer 1

[Matt J]

The following speed comparison is pretty good evidence that only the type of A (sparse or full) dictates how things will be handled,

    >> N=6000; A=speye(N); b=rand(N,1); bsp=sparse(b); Af=full(A);

    >> tic;A\b;toc
    Elapsed time is 0.000316 seconds.
    >> tic;A\bsp;toc
    Elapsed time is 0.000301 seconds.
    >> tic;Af\b;toc
    Elapsed time is 0.071560 seconds.
    >> tic;Af\bsp;toc
    Elapsed time is 0.030398 seconds.

In principle, though, it wouldn't matter. You could have still converted b to sparse type, no matter how dense it actually is, if that's what was needed to force a sparse algorithm to be used. The memory penalty is negligible if b is just a vector.

Answer 2

[Star Strider]

MATLAB has a large number of functions for sparse matrices, all as part of its core functions.

For your problem, I would use the lsqr function.

[John D'Errico]

While it may be the tool to be used in the end, that does not answer the question about internal conversion to full.

Answer 3

[John D'Errico]

The fullness of the right hand side vector (b) is not relevant.

When you use mldivide (or just backslash for that matter), MATLAB performs a sparse decomposition of the matrix A, then applies that decomposition to the right hand side vector, b. Depending on the shape of A, there are different choices it might make. For example, if A is square, then an LU will probably be performed. If A is not square, then a QR would apply. In both cases, I presume pivoting is done. And if A is square, symmetric & positive definite, then chol would be used.

In any case, MATLAB does not worry about the fullness of the right hand side vector (b) to determine if the decomposition is done as a full matrix. What is important is the amount of fill-in that is needed, so the sparsity of A, and where the non-zero elements are in A. That fill-in may slow things down by a lot if it is excessive, since the internally created decomposition may be come quite full in some cases.

If your matrix is such that it creates much fill-in (so it is not terribly sparse or the pattern of the non-zeros causes excessive fill-in) then you may need to use an iterative solver. Iterative solvers can sometimes be useful, but I would ALWAYS attempt first to use a direct solver via backslash, mldivide, linsolve, etc. Only if the direct solve is a memory problem would I go the iterative route. Finally, note that iterative solvers may often need to use a preconditioning matrix to work efficiently.

It is very possible that you have tried to use mldivide for your problem, and you are seeing it take too much time for you. Again, the fullness of the right hand side does not impact the problem, only the nature of A. In that case, you may well be right to use an iterative scheme (such as lsqr, or others.) You may also need to learn about tools such as luinc, cholinc, etc., as these are often good tools to improve the convergence of an iterative method.