Numerical Analysis — Advanced

Partial differential equations and advanced techniques (graduate level)

Overview

The advanced level treats numerical methods for partial differential equations and other advanced numerical techniques. We cover finite differences, the finite element method, and the fast Fourier transform — central to optimization and signal processing.

Learning goals

  • Discretize PDEs by the finite difference method
  • Understand the basic ideas of the finite element method
  • Use Krylov subspace methods (CG, GMRES)
  • Understand fundamental algorithms of numerical optimization
  • Understand the principles and applications of the FFT

Table of contents

§A. Advanced linear algebra

  1. Krylov subspace methods

    Conjugate gradient (CG), GMRES, preconditioning

  2. Lanczos algorithm

    Tridiagonalization of symmetric matrices, Krylov subspaces, eigenvalue computation

  3. Fast Givens rotations

    Accelerated QR decomposition, square-root-free rotations

  4. Randomized SVD

    Low-rank approximation via randomization, Halko-Martinsson-Tropp

  5. Strassen's matrix multiplication

    $O(n^{\log_2 7})$ matrix multiplication, recursive partitioning

  6. Model order reduction

    POD, reduced basis, balanced truncation

§B. Linear PDE solver infrastructure

  1. Multigrid methods

    V-cycle, W-cycle, smoothers, Galerkin coarse grid

  2. Domain decomposition

    Schwarz iterations, Schur complement, parallel preconditioners

§C. Numerical integration

  1. Adaptive quadrature

    Local error estimation, Romberg, recursive bisection

  2. Gauss-Kronrod quadrature

    Nested nodes, error estimation, QUADPACK

  3. Monte Carlo integration

    Random sampling, error estimates, variance reduction, high-dimensional integration

  4. Quasi-Monte Carlo methods

    Low-discrepancy sequences, Halton, Sobol, Koksma-Hlawka inequality

§D. Automatic differentiation

  1. Automatic differentiation

    Forward and reverse modes, dual numbers, computational graphs

§E. PDEs: finite differences

  1. Finite difference method

    Spatial discretization, heat equation, wave equation, CFL condition

  2. Parabolic and hyperbolic equations

    Explicit and implicit schemes, stability analysis, method of characteristics

  3. FDTD (finite-difference time-domain)

    Numerical Maxwell solvers, Yee grid, leapfrog, PML

§F. PDEs: elliptic and FEM

  1. Elliptic PDEs

    Laplace and Poisson equations, boundary value problems

  2. Introduction to the finite element method

    Weak formulation, Galerkin method, basis functions, element matrices

  3. Discontinuous Galerkin (DG)

    Numerical fluxes, conservation laws, hybrid discretizations

  4. hp-FEM

    h-refinement, p-enrichment, exponential convergence, error indicators

  5. Isogeometric analysis

    NURBS, CAD integration, high-order continuity

  6. Spectral methods

    Chebyshev expansion, Galerkin, collocation, exponential convergence

  7. Finite volume method

    Conservative form, fluxes, Riemann solvers

  8. Meshfree methods

    SPH, MLS, RBF, particle methods

  9. Lattice Boltzmann method

    D2Q9 / D3Q19, BGK approximation, fluid simulation

§G. ODEs: symplectic

  1. Symplectic integrators

    Leapfrog, Störmer-Verlet, Yoshida higher-order schemes, conservation in Hamiltonian systems

§H. Discrete Fourier and FFT

  1. Discrete Fourier and FFT (chapter hub)

    Overview of DFT, Cooley-Tukey, Bluestein, and NTT with links to the in-depth articles

§I. Polynomials and sequence acceleration

  1. Advanced polynomial root-finding

    Jenkins-Traub method, companion matrix with QR

  2. Laguerre's method

    Global convergence to complex zeros, cubic convergence

  3. Wynn's epsilon algorithm

    Sequence acceleration, generalization of Aitken's method, Padé approximation

§J. Integral equations and BEM

  1. Integral equations

    Fredholm and Volterra equations, discretization via numerical integration

  2. Boundary element method (BEM)

    Boundary integral equations, Green's functions, dimension reduction, exterior problems

§K. Inverse problems and regularization

  1. Inverse problems and ill-posedness

    Hadamard's well-posedness, condition number, Picard condition, applications

  2. Regularization

    Tikhonov regularization, L1 regularization, TV regularization, parameter selection

Visualizing the finite difference method

A PDE is discretized on a grid and converted to an algebraic system.

5-point stencil for the 2D Laplacian on a uniform grid Boundary nodes (gray) on the perimeter, interior unknowns (blue), and a central highlighted node (pink) connected to four neighbors via the 5-point stencil. u_{i,j} u_{i,j+1} u_{i,j-1} u_{i-1,j} u_{i+1,j} x y Boundary Unknown 5-pt stencil ∇²u ≈ (u_{i+1,j} + u_{i-1,j} + u_{i,j+1} + u_{i,j-1} − 4u_{i,j}) / h²

The finite element method, conceptually

Triangular finite element mesh and a piecewise-linear hat basis function A triangulated 2D domain with nodes (pink) and elements (shaded), and an orange dashed tent function illustrating one nodal basis function. φₐ(x): nodal basis function Triangular element mesh Partition the domain into elements (triangles) → define a tent-shaped basis φₐ at each node → assemble the weak-form linear system

Root-finding via the companion matrix

The roots of $p(z) = z^n + a_{n-1}z^{n-1} + \cdots + a_0$ are the eigenvalues of its companion matrix.

From a polynomial to its companion matrix to its roots via the QR algorithm The polynomial p(z) yields a companion matrix C; running the QR algorithm on C produces eigenvalues that are the roots of p(z), shown as conjugate pairs in the complex plane. p(z) = z⁴ + a₃z³ + a₂z² + a₁z + a₀ Companion matrix C -a₃ -a₂ -a₁ -a₀ 1 0 0 0 0 1 0 0 0 0 1 0 QR algorithm Eigenvalues = roots z₁ z̅₁ z₂ z̅₂ Re Im Theorem: det(C − zI) = (−1)ⁿ p(z), so the eigenvalues of C are the roots of p(z). Advantages: the QR algorithm is highly accurate and stable; mature libraries (LAPACK, etc.) are available. Complexity: O(n³), but very fast and reliable in practice. Coefficient row Shift block

Prerequisites