Matrix fill-in when solving sparse linear systems
4 views (last 30 days)
Show older comments
I am solving the sparse linear system y=c'\b where c (10'000x10'000 density 0.0076) is the result of a Cholesky factorization while b (10'000x23'000 density 0.0027) is a generic sparse matrix. The result y is 10'000x23'000 and it has a density equal to 0.0711. The problem is that many of the non-zero elements are between 1e-15 and 1e-50 while (I suppose) they should be zero.
Things are even worse when I subsequently solve x=c\y in which case the density of x is 0.77 but again most of the elements are lower than eps.
Any idea why this happens?
Indeed, if I use an iterative method (such as the Biconjugate gradients method) and solve c\b(:,i) I get a vector where those near-zero elements are actually zero but I cannot iterate the iterative method over the 23'000 columns of b as it takes ages.
Thanks for your help
0 Comments
Accepted Answer
Richard Brown
on 9 May 2012
Firstly, is there any reason to believe that x should be sparse? Just because your matrix A = C*C' and your right hand sides b are both sparse, doesn't mean that A^(-1)*b should be ... in fact I'd expect that x would not be sparse unless your matrix A has some kind of special structure.
If x should in fact be sparse, then you could solve your problem in batches, maybe doing 100, or 500 or 1000 columns at a time, and thresholding the solution x before storing it
2 Comments
Richard Brown
on 10 May 2012
Can you be a little more precise? Do you mean you are trying to evaluate W - ZA^-1Z^ T and that the properties of your problem should guarantee that both terms have the same sparsity? Is there anything special about Z? Are you able to make your matrices available?
More Answers (0)
See Also
Categories
Find more on Sparse Matrices in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!