This project has moved and is read-only. For the latest updates, please go here.

Solving Sparse matrix linear system

Jun 19, 2013 at 6:47 PM
I have a rather sparse matrix that represents a system of linear equations. I have tried to solve it using the SparseSquareMatrix.Solve method, but it throws a NonConvergenceException. If I use LUDecomposition on the same matrix (using SquareMatrix instead of SparseSquareMatrix) and solve it that way, then I get a good solution. However, I would prefer to not use the SquareMatrix since my matrices can be as big as 4,000x4,000, with only 8,000-16,000 non-zero entries- all that memory kind of adds up.

Is there any other solution I can leverage here? What would cause the SparseSquareMatrix.Solve to fail? I can re-arrange the columns if that would help it to solve properly. Thanks for your help.
Jun 19, 2013 at 10:42 PM
Most of the time with Meta.Numerics, a NonconvergenceException should be an unusual event, indicating either that we have done something wrong (e.g. if you ever get one when computing an AdvancedMath function) or that you have done something wrong (e.g. ask to integrate a function to an accuracy with is simply impossible given your evaluation budget). SparseSquareMatrix.Solve is an exception to that rule. There are some matrix problems for which the iterative algorithm will converge very rapidly, and others for which it will never converge at all. In a future release we plan to add a pre-conditioner, which should increase the space of problems for which it will converge rapidly, and we plan to let you specify an evaluation budget, which would allow you to say that you are willing to wait longer. But the nature of known algorithms for linear systems is such that for some systems convergence will be problematic.

If you can re-arrange variables, the best arrangement for rapid convergence is probably one which is as close to diagonal as possible, i.e. it is better to have non-zero elements in bands 1-10 than in bands 100-1000.

And of course, we would be happy to take your problem as a test case when we do add pre-conditioning.
Jun 20, 2013 at 5:08 PM
Edited Jun 20, 2013 at 5:09 PM
Thanks for the full explanation and for your work on this- you do a great job.

The matrix is already arranged so that all the non-zero elements are no more than 2 bands away from the diagonal, so I'm not sure I would get any benefit there. How may I send you the matrices? I have several examples I can send you, all of which fail.