Preconditioner strategies

1. Relaxation

Split into lower, diagonal, upper parts: \(A = L + D + U\).

1.1. Jacobi

Cheapest preconditioner: \(P^{-1}=D^{-1}\).

# sequential
pc-type=jacobi
# parallel
pc-type=block_jacobi

1.2. Successive over-relaxation (SOR)

\[\left(L + \frac 1 \omega D\right) x_{n+1} = \left[\left(\frac 1\omega-1\right)D - U\right] x_n + \omega b \\ P^{-1} = \text{$k$ iterations starting with $x_0=0$}\]

  • Implemented as a sweep.

  • \(\omega = 1\) corresponds to Gauss-Seidel.

  • Very effective at removing high-frequency components of residual.

# sequential
pc-type=sor

2. Factorization

Two phases

  • symbolic factorization: find where fill occurs, only uses sparsity pattern.

  • numeric factorization: compute factors.

2.1. LU decomposition

  • preconditioner.

  • Expensive, for \(m\times m\) sparse matrix with bandwidth \(b\), traditionally requires \(\mathcal{O}(mb^2)\) time and \(\mathcal{O}(mb)\) space.

    • Bandwidth scales as \(m^{\frac{d-1}{d}}\) in d-dimensions.

    • Optimal in 2D: \(\mathcal{O}(m \cdot \log m)\) space, \(\mathcal{O}(m^{3/2})\) time.

    • Optimal in 3D: \(\mathcal{O}(m^{4/3})\) space, \(\mathcal{O}(m^2)\) time.

  • Symbolic factorization is problematic in parallel.

2.2. Incomplete LU

  • Allow a limited number of levels of fill: ILU(\(k\)).

  • Only allow fill for entries that exceed threshold: ILUT.

  • Usually poor scaling in parallel.

  • No guarantees.

3. 1-level Domain decomposition

Domain size $$L$$, subdomain size $$H$$, element size $$h$$

  • Overlapping/Schwarz

    • Solve Dirichlet problems on overlapping subdomains.

    • No overlap: \(\textit{its} \in \mathcal{O}\big( \frac{L}{\sqrt{Hh}} \big)\).

    • Overlap \(\delta: \textit{its} \in \big( \frac L {\sqrt{H\delta}} \big)\).

  • Neumann-Neumann

    • Solve Neumann problems on non-overlapping subdomains.

    • \(\textit{its} \in \mathcal{O}\big( \frac{L}{H}(1+\log\frac H h) \big)\).

    • Tricky null space issues (floating subdomains).

    • Need subdomain matrices, not globally assembled matrix.

Multilevel variants knock off the leading \(\frac L H\).
Both overlapping and nonoverlapping with this bound.

  • BDDC and FETI-DP

    • Neumann problems on subdomains with coarse grid correction.

    • \(\textit{its} \in \mathcal{O}\big(1 + \log\frac H h \big)\).

4. Multigrid

4.1. Introduction

Hierarchy: Interpolation and restriction operators \(\Pi^\uparrow : X_{\text{coarse}} \to X_{\text{fine}} \qquad \Pi^\downarrow : X_{\text{fine}} \to X_{\text{coarse}} \)

  • Geometric: define problem on multiple levels, use grid to compute hierarchy.

  • Algebraic: define problem only on finest level, use matrix structure to build hierarchy.

Galerkin approximation

Assemble this matrix: \(A_{\text{coarse}} = \Pi^\downarrow A_{\text{fine}} \Pi^\uparrow\)

Application of multigrid preconditioner (\(V\)-cycle)

  • Apply pre-smoother on fine level (any preconditioner).

  • Restrict residual to coarse level with \(\Pi^\downarrow\).

  • Solve on coarse level \(A_{\text{coarse}} x = r\).

  • Interpolate result back to fine level with \Pi^\uparrow.

  • Apply post-smoother on fine level (any preconditioner).

4.2. Multigrid convergence properties

  • Textbook: \(P^{-1}A\) is spectrally equivalent to identity

    • Constant number of iterations to converge up to discretization error.

  • Most theory applies to SPD systems

    • variable coefficients (e.g. discontinuous): low energy interpolants.

    • mesh- and/or physics-induced anisotropy: semi-coarsening/line smoothers.

    • complex geometry: difficult to have meaningful coarse levels.

  • Deeper algorithmic difficulties

    • nonsymmetric (e.g. advection, shallow water, Euler).

    • indefinite (e.g. incompressible flow, Helmholtz).

  • Performance considerations

    • Aggressive coarsening is critical in parallel.

    • Most theory uses SOR smoothers, ILU often more robust.

    • Coarsest level usually solved semi-redundantly with direct solver.

  • Multilevel Schwarz is essentially the same with different language

    • assume strong smoothers, emphasize aggressive coarsening.