What's the best solver that can solve a large sparse but indefinite matrix?
$\begingroup$
$\endgroup$
1
-
3$\begingroup$ Welcome to scicomp. To get good and useful answers, I suggest you make your question more specific. Try to avoid the word 'best' as it is hard to define what is the best. How about, 'how to solve large sparse indefinite linear systems?' $\endgroup$– JanJul 17, 2013 at 11:42
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
8
You may want to watch lecture 34 here: http://www.math.tamu.edu/~bangerth/videos.html
answered Jul 17, 2013 at 11:05
-
1$\begingroup$ The sparse direct complexities around the five minute mark are a bit off. For 3D and higher meshes, the computational and memory complexities behave like $O(N^{3(1-1/d)})$ and $O(N^{2(1-1/d)})$, which matches the well-known 3D complexities of $O(N^2)$ and $O(N^{4/3})$. For 2D, the classical complexities are $O(N^{3/2})$ and $O(N \log N)$. $\endgroup$ Jul 17, 2013 at 17:00
-
$\begingroup$ Hm, thanks for pointing it out. I'm sure I had something in mind when I wrote these slides. In particular, for memory, the bandwidth of the matrix for a regular mesh is $(1/h)^{d-1}=(N^{1/d})^{d-1}=N^{(d-1)/d}$ and consequently the total number of nonzeros in the band is $N$ times the bandwidth. Is this not the correct computation? $\endgroup$ Jul 18, 2013 at 2:00
-
2$\begingroup$ I think that you're calculating the complexities for banded solvers. Sparse-direct methods achieve much lower complexities by carefully reordering the entries in a manner which further reduces fill. Chapter 2 of my dissertation derives all of this from scratch. $\endgroup$ Jul 18, 2013 at 2:03
-
$\begingroup$ @WolfgangBangerth Indeed, "bandwidth" is not the relevant measure for sparse direct methods. I don't know where that myth started, but it gives the wrong impression and we should do our best to kill it. Minimal vertex separator is not that different of a concept, but allows accurate reasoning. $\endgroup$ Jul 20, 2013 at 19:44
-
$\begingroup$ Thanks, guys, for pointing this out. I'll have to update the description of this talk with an erratum. $\endgroup$ Jul 21, 2013 at 2:05
$\begingroup$
$\endgroup$
Prof. Bangerth's lecture has already covered most of it, but I'd recommend you look at this paper. The authors take three of the most common methods (GMRES, CGS and CGNE) and give some matrices for which one method will converge in O(1) operations and the other two converge in O(N). The upshot of this is that there is no uniformly best iterative method for indefinite systems.
There are some special cases. For example, if your matrix is symmetric but indefinite, you'll want to use MINRES, or if your matrix comes from a constrained optimization problem there's a family of methods based on the Uzawa algorithm that you'd want to look at. Nonetheless, no one method works best for everything.
All told, you'll be better off asking what's the best preconditioner for the specific problem you have in mind. Prof. Bangerth has a bunch of lectures on this topic already, but I'll mention ILU as a fairly popular approach which works for a lot of problems and is pretty easy to understand (if not to analyze).
If you want more background, you can refer to Yousef Saad's book on iterative methods for sparse linear systems or Tim Davis's book on direct methods.
answered Jul 17, 2013 at 17:04
$\begingroup$
$\endgroup$
The question cannot be answered in this generality. It depends on the system. If it is related to the discretization of partial differential equations, a well designed multigrid method is of linear complexity. It can be used as a preconditioner in a Krylov-space method for additional robustness.
