Are iterative methods always better than direct methods for solving large linear systems?

19 views (last 30 days)
I am trying to solve a very sparse linear system Ax = b. A is very sparse - if A is of size N^2 x N^2, all nontrivial elements for any row k are located in between (k-2N, k+2N). The overall the number of nontrivial elements in A is bounded by 13*N^2 (for a matrix with N^4 elements)
Now back to the original question: Currently I am using mldivide to solve the system. On a 1e6 x 1e6 matrix, the program takes around 60-75s 64 bit machine. Now it is possible to beat this performance using iterative methods? The ones I have tried (built into MATLAB) do not seem to offer any advantages; however, I think that may be due to the fact that I am not using a preconditioner. The problem is, how do I effectively get a preconditioner? I tried using ilu, but that is also pretty slow (and there is no guarantee that it will do the trick).
Thanks, Peter

Accepted Answer

Adrien Leygue
Adrien Leygue on 9 May 2011
From my personal experience, there is only one case where I have been able to outperform mldivide through the use of one of the Matlab-provided iterative solvers. In this particular application I had to solve many linear systems (several hundredth, size > 1e5 unknowns), all the systems were different (left and right hand side) but each system to solve was very close to the previous one. I could therefore provide a very good initial guess for the solution. There PCG with incomplete factorization provided some speed improvement as only a few iterations were needed.
The problem is that mldivide is so efficient that unless you have memory issues (or if you have a very good estimate of your solution), the provided iterative solvers are no match.
Hope this helps
  1 Comment
Peter on 1 Jul 2011
Hi Adrien,
Sorry for the late response, but with my recent work I seem to be coming to the same response. I recently tried to use iterative solvers again as I am looking at some very big matrices (4e6 x 4e6) for a finite difference scheme. The direct solver with mldivide can invert the system in ~ 40 minutes. The iterative solvers though are not that promising. I think the issue is that I cannot find a good preconditioner (I tried Jacobi and ILU). They don't seem to affect any of the methods except GMRES. The issue with GMRES is that while 10 iterations gives a rel residual of ~ 1e-2 - 1e-3, it seems to stangate as one approaches the 1e-6 tolerance

Sign in to comment.

More Answers (1)

Wolfgang Schwanghart
Wolfgang Schwanghart on 9 May 2011
Why is performance a problem? Do you have to solve the system repeatedly or do you want to solve larger systems? If former is the case, then take a look at Tim Davis' factorize
If latter is the case, then I hope someone else will be able to provide an answer.


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!