mldivide (backslash): advantage by using sparse matrix instead of a full matrix with respect to the quality of the results?

I am solving a linear system of equations Ax = B with the backslash operator. I have two versions of A implemented: a sparse and a full matrix.

Sometimes I get the warning that my matrix is close too singular. However, I get it more seldom if I am using sparse matrices. Is there a reason for it? Does this mean that the results are more reliable using sparse matrices?

When I compute the condition number for both cases using the command condest(A), I obviously get the same result for the sparse and the full matrix. I have an example where condest(A) = 3.65e27 which is of course very high. However, I get only a warning that the matrix is close too singular in the case of the full matrix. Does this make sense? Can I conclude that the solution is better for the sparse matrix since I do not get a warning?

[Torsten]

Just computing the residual A*X - B should answer your question.

I can't imagine that the reliability depends on whether you use the sparse or full option.

Maybe the internal limit to give a warning is differently implemented.

Answer 1

[Christine Tobler]

The condition estimate used in mldivide to decide if a warning should be given is much less accurate for the sparse case. This is simply because it could get very expensive to compute in the sparse case, so we use a cheap heuristic.

So for sparse matrices, the result from condest should be trusted much more than whether a warning is given in mldivide.

Answer 2

[Bruno Luong]

If your condition is 3.65e27 you wi=on't get any reliable solution regardless the method.

The full matrix use QR with permutation and detect the conditioning issue better than sparse. MATLAB try to prevent sparse structure so it might not detect as well conditioning issue.

No I disagree with Torsen, for ill conditining system you can get wrong result even if the residual norm |A*x-b| is small. I can also guess the residual is smaller if you use full-sover, but it doesn't mean the solution is good.

[Torsten]

What do you mean by "wrong result" in the above context ?

[Bruno Luong]

wrong results means |x-xtrue| is not small.

[Bruno Luong]

Illustration of both methods fail

A=magic(100);
xtrue=randn(100,1);
b=A*xtrue;

cond(A)

ans = 2.4494e+19

S=sparse(A);
xd=A\b; % dense solution

Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 1.294285e-21.

xs=S\b; % sparse solution

Warning: Matrix is close to singular or badly scaled. Results may be inaccurate. RCOND = 3.066166e-19.

% solution errors, flop
errreldense=norm(xd-xtrue)/norm(xtrue)

errreldense = 4.4846e+03

errrelsparse=norm(xs-xtrue)/norm(xtrue)

errrelsparse = 1.1734e+04

% solution residual, still OK
relresnormsdense=norm(A*xd-b)/norm(b)

relresnormsdense = 2.8692e-13

relresnormssparse=norm(A*xs-b)/norm(b)

relresnormssparse = 5.9232e-13

[Torsten]

Within the model in which you calculate x from A*x = b, an x for which norm(A*x-b) is small is the xtrue (in my opinion). Whether this x makes physical sense is a different question.

[Bruno Luong]

Not really, in deconvolution problem one arrives at linear system A*x = b, where x is the signal to be revovered from b=A*xtrue. One can hardly recover xtrue numerically even A*x-b is small. In therory it should give back xtrue. The problem is A is ill-conditioned matrix and finite-precision calculation just give wrong solution due to numerical truncation (let alone data error at the moment). To me that problem clearly occurs when cond(A) > 1/eps(1) (even before that). Working with matrix with cond(A) > 1e12 is already hopeless.

[Torsten]

ok, I'm convinced.

[Michael Loibl]

Thank you. I won some new insights. Thank you very much for the illustrative example.

I was aware that a condition number of 1e27 is very bad. Before I thougt that I could simply trust the warnings from Matlab and lean back. When I started computing with sparse matrices, I often did not get warnings, but I started checking for the conditioning by myself. In consequence, I will add a check for the conditioning by myself now for the sparse case.