Krylov, Multigrid, and Domain Decomposition¶
Job: develop the Krylov methods (CG / GMRES / preconditioning), the multigrid (V-cycle / \(O(N)\)), the domain decomposition (Schwarz / FETI / BDDC), and the fast algorithms (FFT / butterfly) — with the CG / multigrid for the Poisson as the worked example.
Core¶
Krylov methods¶
| CG / GMRES / preconditioning | Description |
|---|---|
| CG | the SPD, \(\|x-x_k\|_A\le 2((\sqrt\kappa-1)/(\sqrt\kappa+1))^k\|x-x_0\|_A\) (the linear algebra) |
| GMRES / MINRES | the nonsymmetric / the indefinite (the Saad–Schultz) |
| Preconditioning | the \(M^{-1}A\) (the optimization) |
Multigrid¶
| Multigrid / V-cycle / \(O(N)\) | Description |
|---|---|
| V-cycle | the smoothing (the high-freq), the restriction (the coarse), the prolongation (the Hackbusch) |
| Convergence | the \(O(N)\) the optimal (the smoothing the high-freq, the coarse the low-freq) |
Domain decomposition¶
| Schwarz / FETI / BDDC | Description |
|---|---|
| Schwarz | the overlapping (the additive / the multiplicative, the optimization) |
| FETI / BDDC | the non-overlapping (the interface, the optimization) |
Fast algorithms and the FFT / butterfly¶
| FFT / butterfly / \(O(N\log N)\) | Description |
|---|---|
| FFT | the \(O(N\log N)\) (the Fourier analysis) |
| Butterfly | the \(O(N\log N)\) the general (the O'Neil–Rokhlin) |
See it¶
CG for the SPD and the multigrid V-cycle for the Poisson. The CG: the \(Ax=b\) the SPD, the \(\|x-x_k\|_A\le 2\rho^k\|x-x_0\|_A\) (\(\rho=(\sqrt\kappa-1)/(\sqrt\kappa+1)\), the linear algebra). The multigrid: the Poisson \(-\Delta u=f\), the V-cycle (the Jacobi / Gauss–Seidel the smoothing the high-freq, the restriction the coarse, the prolongation), the \(O(N)\) the optimal (the Hackbusch). The key point: the CG the \(\kappa\) the rate, the multigrid the \(O(N)\) the Poisson — the iterative / multigrid.
Check¶
Show that the CG rate depends on \(\kappa(A)\), and explain the multigrid V-cycle.
The CG: the \(A\) the SPD, the \(\|x-x_k\|_A\le 2((\sqrt\kappa-1)/(\sqrt\kappa+1))^k\|x-x_0\|_A\) (the Chebyshev the bound, the \(\kappa=\lambda_{\max}/\lambda_{\min}\), the linear algebra). The multigrid: the V-cycle (1) the smoothing: the \(\nu\) Jacobi / Gauss–Seidel (the high-freq the damping, the low-freq the remaining), (2) the restriction: the \(r_h\to r_{2h}\) (the coarse grid), (3) the coarse solve: the \(e_{2h}=A_{2h}^{-1}r_{2h}\) (the recursive / the exact), (4) the prolongation: the \(e_{2h}\to e_h\) (the interpolation), the \(u_h\to u_h+e_h\). The \(O(N)\): the smoothing the \(O(N)\), the restriction / prolongation the \(O(N)\), the coarse the \(O(N/4)\) (the recursion), the total \(O(N)\). So the CG the \(\kappa\), the multigrid the \(O(N)\).
Explain the Schwarz alternating and the FETI / BDDC non-overlapping.
The Schwarz: the \(\Omega=\Omega_1\cup\Omega_2\) the overlapping, the alternating \(u_1\) on \(\Omega_1\) (the \(u_2\) fixed), \(u_2\) on \(\Omega_2\) (the \(u_1\) fixed), the convergence (the Lions, the optimization). The additive: the parallel (the \(u_1, u_2\) the simultaneous). The FETI / BDDC: the \(\Omega=\Omega_1\cup\Omega_2\) the non-overlapping, the interface \(\Gamma\), the FETI the tearing (the \(\Omega_i\) the independent, the \(\Gamma\) the Lagrange the gluing), the BDDC the balancing (the coarse the interface). So the Schwarz the overlapping, the FETI / BDDC the non-overlapping.
Pitfalls¶
- The CG the SPD (the \(\kappa\), the linear algebra) — the CG the SPD, the GMRES the nonsymmetric.
- The multigrid the \(O(N)\) (the smoothing the high-freq, the coarse the low-freq) — the multigrid the optimal, the Jacobi the slow (the low-freq).
- The Schwarz the overlapping (the Lions, the optimization) — the Schwarz the overlapping, the FETI / BDDC the non-overlapping.
- The FFT the \(O(N\log N)\) (the Fourier analysis) — the FFT the fast, the butterfly the general.
Refs¶
- Hackbusch, Multi-Grid Methods (1985); the V-cycle / the \(O(N)\)
- Saad, Iterative Methods for Sparse Linear Systems (2003); the GMRES
- Toselli–Widlund, Domain Decomposition Methods (2005); the Schwarz / FETI
- O'Neil–Rokhlin, "A class of integral transforms" (2010); the butterfly
Next¶
NA index · Foundations · FEM & Variational · Geometric Integration · High-Dimensional & UQ · Linear algebra · Fourier analysis · Optimization