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).
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
More Answers (1)
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.