# What guidelines should I follow when choosing a sparse linear system solver?

Sparse linear systems turn up with increasing frequency in applications. One has a lot of routines to choose from for solving these systems. At the highest level, there is a watershed between direct (e.g. sparse Gaussian elimination or Cholesky decomposition, with special ordering algorithms, and multifrontal methods) and iterative (e.g. GMRES, (bi-)conjugate gradient) methods.

How does one determine whether to use a direct or an iterative method? Having made that choice, how does one pick a particular algorithm? I already know about the exploitation of symmetry (e.g. use conjugate gradient for a sparse symmetric positive definite system), but are there any other considerations like this to be considered in picking a method?

-

The important thing when choosing iterative solvers is the spectrum of the operator, see this paper. However, there are so many negative results, see this paper where no iterative solver wins for all problems and this paper in which they prove they can get any convergence curve for GMRES for any spectrum. Thus, it seems impossible to predict the behavior of iterative solvers except in a few isolated cases, Therefore, your best option is to try them all, using a system like PETSc, which also has direct solvers.

-
"Throw everything you can at it" was pretty much the advice I was accustomed to. :) The third paper you link to is something I haven't seen before; thanks for that! –  Ｊ. Ｍ. Nov 30 '11 at 15:20
Matt has a great answer, but you have to take it within the context of the community he is coming from (large-scale scientific computing). You will find that for small problems (say, less than a hundred thousand unknowns), that direct solvers vastly outperform iterative methods if the problem is not strongly elliptic. I have not seen any good general papers in the literature that would steer you towards an initial starting strategy, which is a bit embarrassing to me. –  Aron Ahmadia Nov 30 '11 at 15:42
Aron's estimate is good but heavily dependent on fill since sparse direct methods usually exhaust memory before they exhaust patience. –  Matt Knepley Nov 30 '11 at 15:50

The choice between direct and iterative methods is dependent on goals and problem at hand.

For Direct methods we can note

• The coefficient matrix of the linear system changes over the course of computation and may for sparse systems exhaust memory requirements and increase work effort due to fill-in
• Must complete to give useful results
• Factorization can be reused in subsequent steps if multiple right hand sides are present
• Can be used for solving linear systems only.
• Seldom fails.

For Iterative methods we can note

• Goal is to give partial result only after a small number of iterations.
• Solution effort should be less than direct methods for same problem.
• Economical with respect to storage (no fill-in)
• Often easy to program.
• A known approximate solution can be exploited.
• Sometimes they are fast and sometimes they are not (sometimes even divergent).
• For complex problems iterative methods are considerably less robust compared to direct methods.

Guidelines for when to use direct or iterative methods?

• Iterative methods when coefficient matrix is sparse and direct methods cannot exploit sparsity efficiently (avoid creating fill-in).
• Direct methods for multiple right hand sides.
• Iterative methods can be more efficient if accuracy is of less concern
• Iterative methods for nonlinear systems of equations.
-
I think that it is important to note that direct methods are not always better for multiple right-hand sides. Perhaps they are better for $O(n)$ right-hand sides, but if the iterative method is $O(n)$ while the direct method is $O(n^2)$, it is still advantageous to use the iterative solver for $O(1)$ right-hand sides. –  Jack Poulson Jan 8 '12 at 18:08