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

24 次查看（过去 30 天）
Peter
Peter 2011-5-9
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

请先登录，再回答此问题。

采纳的回答

Adrien Leygue
Adrien Leygue 2011-5-9
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
A.
  1 个评论
Peter
Peter 2011-7-1
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

请先登录，再进行评论。

更多回答（1 个）

Wolfgang Schwanghart
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
http://www.mathworks.com/matlabcentral/fileexchange/24119-dont-let-that-inv-go-past-your-eyes-to-solve-that-system-factorize
If latter is the case, then I hope someone else will be able to provide an answer.
HTH, W.

类别

在 Help Center 和 File Exchange 中查找有关 Linear Algebra 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by