Spectral and Multigrid Methods

Spectral methods achieve exponential convergence for smooth problems by using global polynomial or trigonometric approximations. Multigrid methods solve the resulting linear systems in optimal $O(N)$ time by exploiting the multi-scale structure of the error.

Spectral Methods

Definition8.7Spectral Galerkin and Collocation

Spectral methods approximate the solution using global basis functions. For periodic problems, the Fourier basis $e^{ikx}$ is natural; for non-periodic problems, Chebyshev polynomials $T_k(x)$ or Legendre polynomials are used. In the spectral Galerkin approach, the residual is orthogonal to the basis: $\langle \mathcal{L}u_N - f, \phi_k \rangle = 0$ . In spectral collocation (pseudospectral), the PDE is enforced at $N$ collocation points (Chebyshev-Gauss-Lobatto or Gauss-Legendre nodes).

ExampleExponential Convergence

For $-u'' + u = f$ on $[-1,1]$ with analytic $f$ , a Chebyshev spectral method with $N$ modes gives $\|u - u_N\|_\infty = O(\rho^{-N})$ for some $\rho > 1$ depending on the analyticity strip of $u$ . For $f(x) = e^x$ : $N = 16$ Chebyshev modes achieve $10^{-14}$ accuracy, while a finite difference method with the same number of points gives only $O(h^2) \approx 10^{-2}$ accuracy.

Multigrid Methods

Definition8.8Multigrid V-Cycle

Multigrid solves $A_h u_h = f_h$ (with mesh size $h$ ) by cycling through a hierarchy of grids $h, 2h, 4h, \ldots$ . The V-cycle consists of:

Pre-smoothing: Apply $\nu_1$ iterations of a smoother (Gauss-Seidel, Jacobi) on the fine grid
Restriction: Transfer the residual to the coarse grid: $r_{2h} = I_h^{2h}(f_h - A_h u_h)$
Coarse-grid solve: Solve $A_{2h} e_{2h} = r_{2h}$ (recursively or directly)
Prolongation: Correct the fine-grid solution: $u_h \leftarrow u_h + I_{2h}^h e_{2h}$
Post-smoothing: Apply $\nu_2$ iterations of the smoother

RemarkMultigrid Convergence and Optimality

The key insight of multigrid: smoothing eliminates high-frequency error components efficiently (Gauss-Seidel reduces oscillatory errors in $O(1)$ iterations), while the coarse grid represents and eliminates low-frequency errors cheaply. The combination gives a convergence factor $\rho < 1$ independent of $h$ . For the model Poisson problem: $\rho \approx 0.1$ per V-cycle. Since each V-cycle costs $O(N)$ work (the geometric series $N + N/4 + N/16 + \cdots = O(N)$ ), multigrid achieves textbook efficiency: $O(N)$ total work for $N$ unknowns.

Domain Decomposition

Definition8.9Domain Decomposition Methods

Domain decomposition partitions $\Omega = \bigcup_i \Omega_i$ and solves local problems on each subdomain, communicating through interface conditions. Schwarz methods use overlapping subdomains: alternating Schwarz updates boundary conditions from neighboring solutions. Schur complement methods (FETI, BDD) use non-overlapping subdomains and solve the interface problem via a Krylov method preconditioned by local solves. These methods are naturally parallel and achieve $O(N/P)$ work per processor with $P$ processors, given appropriate coarse-space corrections.

ExampleAlgebraic Multigrid (AMG)

Algebraic multigrid constructs the coarse-grid hierarchy from the matrix $A$ alone, without geometric information. AMG identifies "strong connections" (large off-diagonal entries), selects coarse-grid points, and builds interpolation operators algebraically. For unstructured meshes and complex geometries where geometric multigrid is difficult to implement, AMG provides a robust $O(N)$ solver. Modern AMG implementations (BoomerAMG, ML) are the default preconditioners for large-scale scientific computing.