Solver Decision Tree

Solver Decision Tree

Comprehensive decision guide for selecting linear solvers for Ax = b.

Matrix Classification

Key Properties to Determine

Quick Classification

Check symmetry: ||A - Aᵀ||_F / ||A||_F < ε
Check SPD: try Cholesky, if succeeds → SPD
Check sparsity: nnz / n² gives density
Check conditioning: estimate κ using power iteration or Lanczos

Primary Decision Tree

START: Need to solve Ax = b
│
├─ Is n < 5000 and matrix dense?
│   └── YES → Use DIRECT solver
│       ├── Symmetric PD → Cholesky (LLᵀ)
│       ├── Symmetric indefinite → LDLᵀ (Bunch-Kaufman)
│       ├── Nonsymmetric → LU with pivoting
│       └── Least squares → QR or SVD
│
└── NO → Use ITERATIVE solver
    │
    ├─ Is matrix symmetric?
    │   │
    │   ├── YES → Is it positive definite?
    │   │   │
    │   │   ├── YES (SPD) → CG (Conjugate Gradient)
    │   │   │   ├── Elliptic PDE → AMG preconditioner
    │   │   │   ├── Banded structure → IC(0) or IC(k)
    │   │   │   └── General sparse → AMG or IC
    │   │   │
    │   │   └── NO/Unknown (symmetric indefinite)
    │   │       ├── Eigenvalues both signs → MINRES
    │   │       ├── Near-singular → SYMMLQ
    │   │       └── Preconditioner: ILU or block diagonal
    │   │
    │   └── NO (nonsymmetric) → Is it nearly symmetric?
    │       │
    │       ├── YES (A ≈ Aᵀ) → BiCGSTAB
    │       │   ├── Smooth convergence needed → BiCGSTAB(ℓ)
    │       │   └── Preconditioner: ILUT or AMG
    │       │
    │       └── NO (strongly nonsymmetric) → GMRES
    │           ├── Memory limited → GMRES(m) restarted
    │           ├── Very nonsymmetric → Full GMRES if affordable
    │           └── Preconditioner: ILU(k), ILUT, or AMG

Direct Solver Selection

When to Use Direct

Direct Solver Types

Memory Considerations

Iterative Solver Details

Conjugate Gradient (CG)

Requirements: A must be SPD

Convergence:

||e_k||_A ≤ 2 × ((√κ - 1)/(√κ + 1))^k × ||e_0||_A

Breakdown: CG is breakdown-free for SPD matrices.

GMRES

Requirements: None (works for any nonsingular matrix)

Properties:

• Minimizes residual over Krylov subspace
• Optimal for nonsymmetric systems
• Memory: O(m × n) for m iterations

Restart Strategy:

GMRES(m): Restart after m iterations
├── m = 20-30: Typical for memory-limited
├── m = 50-100: Better convergence
└── m = n: Full GMRES (no restart)

When GMRES stalls:

• Increase restart parameter m
• Improve preconditioner
• Check for near-singularity

BiCGSTAB

Requirements: Works for nonsymmetric, best if A ≈ Aᵀ

Properties:

• Lower memory than GMRES
• May have irregular convergence
• Two matrix-vector products per iteration

Variants:

MINRES

Requirements: A symmetric (not necessarily PD)

Properties:

• Works for indefinite symmetric systems
• Minimizes residual (like GMRES for symmetric)
• Short recurrences (memory efficient)

Use for:

• Saddle-point systems
• Systems from variational problems
• Eigenvalue problems (shift-invert)

Special Matrix Structures

Saddle-Point Systems

[A   B ] [x]   [f]
[Bᵀ  -C] [y] = [g]

Solvers:

• Schur complement method
• Uzawa iteration
• Block preconditioned GMRES/MINRES

Preconditioners:

Block diagonal: [A⁻¹   0  ]
                [0    S⁻¹]

Block triangular: [A⁻¹  0 ]
                  [Bᵀ   S⁻¹]

Where S = C + BᵀA⁻¹B is the Schur complement.

Banded Systems

For bandwidth b << n:

Block Systems

When A has natural block structure:

Block Jacobi: Solve diagonal blocks independently
Block Gauss-Seidel: Sequential block updates
Block ILU: Factor with block structure preserved

Solver Selection by Application

Elliptic PDEs (Laplacian-like)

Parabolic PDEs (Heat equation)

Hyperbolic PDEs (Advection-dominated)

Navier-Stokes

Phase-Field

Failure Modes and Remedies

Common Problems

When All Else Fails

1. Check the matrix: Is it actually nonsingular?
2. Scale rows/columns: Equilibrate to unit row norms
3. Try direct solver: Even for large sparse, may work
4. Regularize: Add small diagonal for near-singular
5. Reformulate problem: Different discretization

Quick Reference Table