Issues with solving large sparse linear equations

Question

I have some issues solving sparse linear equations Ax = b

My matrix A is sparse with dimension of 5 million by 5 million. Actually, it is a combination of two matrices. One is tridiagonal and the other matrix has a bigger band. For example the $29450^{th}$ row has non zero diagonal entry. Plus non zero element at $14725^{th}$, $44175^{th}$, $29451^{th}$, $29449^{th}$,$29605^{th}$,$29295^{th}$,column. So every row has almost 6 non zero elements plus non zero diagonal entry.

I tried to use a couple of iterative solvers in matlab, but they don't seem to give good accuracy. Also if I run the iteration for a long time, I will have round off errors and all. What can I do to get the best estimate?

Answer 1

The convergence of iterative methods doesn't depend on the sparsity structure of the matrix, but (for Krylov methods) on the distribution of its eigenvectors. One can even construct diagonal (!) matrices for which GMRES converges prohibitively slowly.

If your matrix had narrow bandwidth, it would be safe to advice some sort of LU-solver. However, those entries 14725 and 44175 indicate a wide range, and LU might have to use a lot of memory due to the fill-in effect.

In any case, if you're exploring solution methods for your linear system, 5 million unknowns are way to many to play around with. My first advice would be to adapt your problem such that the number of unknowns are around a few thousand (if your problem stem from a PDE, you could increase the mesh size), and then check out spectral properties and see about a solver.