5
$\begingroup$

What's the best solver that can solve a large sparse but indefinite matrix?

$\endgroup$
  • 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$ – Jan Jul 17 '13 at 11:42
7
$\begingroup$

You may want to watch lecture 34 here: http://www.math.tamu.edu/~bangerth/videos.html

$\endgroup$
  • 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$ – Jack Poulson Jul 17 '13 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$ – Wolfgang Bangerth Jul 18 '13 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$ – Jack Poulson Jul 18 '13 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$ – Jed Brown Jul 20 '13 at 19:44
  • $\begingroup$ Thanks, guys, for pointing this out. I'll have to update the description of this talk with an erratum. $\endgroup$ – Wolfgang Bangerth Jul 21 '13 at 2:05
6
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.