Ubiquitous Laplacian: An Introduction to Numerical PDEs with Applications in Data Science

By Rongjie Lai and Xiangxiong Zhang    

DOI: 10.1142/14349

This book contains problems and projects that may serve as homework and exam problems, or even as potential building blocks for designing computational mathematics research projects suitable for both undergraduate and graduate students. If using this book as a textbook, solutions and codes are available upon request (contact Zhang for Part I and Lai for Part II).

Table of Contents

• Preface
• 1. Introduction
  • 1.1 Linear partial differential equations
  • 1.2 Random walks and the heat equation
  • 1.3 Numerical schemes
  • 1.4 Examples and applications of the discrete Laplacian
  • 1.5 A reader’s guide
• Part I: Cartesian grids and meshes
• 2. Finite difference method
  • 2.1 Second order finite difference approximations
  • 2.2 Dirichlet boundary conditions in one dimension
    • 2.2.1 Consistency, stability and convergence
    • 2.2.2 Stability by eigenvalues of K
    • 2.2.3 An implementation in MATLAB
    • 2.2.4 Nonhomogeneous Dirichlet boundary conditions
  • 2.3 Dirichlet and Neumann b.c. in one dimension
    • 2.3.1 A symmetric matrix T
    • 2.3.2 Nonsymmetric matrix T2
  • 2.4 Convergence in maximum norm
    • 2.4.1 Dirichlet boundary conditions
    • 2.4.2 Dirichlet and Neumann b.c.
    • 2.4.3 Why the scheme T2Uh = F is second order accurate
  • 2.5 Neumann boundary conditions in one dimension
    • 2.5.1 The matrix B on the one-half grid
    • 2.5.2 The matrix B on the integer grid
    • 2.5.3 The matrix B2 on the integer grid
    • 2.5.4 Compatibility condition of Neumann b.c.
    • 2.5.5 Inverting B
    • 2.5.6 Inverting B2
  • 2.6 Periodic boundary conditions in one dimension
  • 2.7 Dirichlet boundary conditions in two dimensions
  • 2.8 Neumann boundary conditions in two dimensions
  2.9 Efficient implementations in three dimensions
  • 2.10 Higher order accuracy: the 9-point discrete Laplacian
  • 2.11 Variable coefficient problems
    • 2.11.1 Dirichlet boundary conditions in one dimension
    • 2.11.2 Dirichlet boundary conditions in two dimensions
    • 2.11.3 Neumann boundary conditions in one dimension
• 3. Finite element method on rectangular meshes
  • 3.1 Motivation and overview
  • 3.2 Preliminaries
    • 3.2.1 Weak derivatives and Sobolev spaces
    • 3.2.2 Interpolation and quadrature
  • 3.3 Homogeneous Dirichlet b.c. in one dimension
    • 3.3.1 Variational formulation
    • 3.3.2 Bilinear form
    • 3.3.3 The abstract finite element method
    • 3.3.4 The abstract implementation
    • 3.3.5 The simple implementation on uniform meshes
  • 3.4 Basic properties of the bilinear form
    • 3.4.1 Continuity
    • 3.4.2 Coercivity
    • 3.4.3 Coercivity is stability
  • 3.5 Error estimates of the abstract finite element method
    • 3.5.1 H1-norm estimate and convergence
    • 3.5.2 L2-norm estimate
    • 3.5.3 Summarization and comparison
  • 3.6 Properties of the bilinear form with quadrature
    • 3.6.1 Equivalent norms of the piecewise linear polynomial
    • 3.6.2 Coercivity and continuity of the bilinear form Ah
    • 3.6.3 Coercivity implies stability of the finite difference scheme
  • 3.7 Error estimates of the finite element method with quadrature
    • 3.7.1 First Strang Lemma
    • 3.7.2 Quadrature estimate: Bramble-Hilbert Lemma
    • 3.7.3 Error estimates
  • 3.8 Generalization: general domain in two dimensions
  • 3.9 Generalization: purely Neumann b.c.
    • 3.9.1 Quotient space H1(Ω)/P 0(Ω)
    • 3.9.2 Variational formulation and coercivity
    • 3.9.3 The finite element method
    • 3.9.4 Coercivity implies the stiffness matrix null space
    • 3.9.5 The finite difference form
    • 3.9.6 How to solve the singular linear system
    • 3.9.7 Why symmetry of S is important
  • 3.10 Generalization: nonhomogeneous Dirichlet b.c.
    • 3.10.1 A scheme in theory
    • 3.10.2 A simple and practical scheme
    • 3.10.3 A scheme in theory for a general domain Ω
    • 3.10.4 A simple and practical scheme in two dimensions
    • 3.10.5 The error in the 2-norm over grid point values
  • 3.11 Generalization: a general elliptic operator
  3.12 Generalization: higher order accuracy via P2
  • 3.12.1 Dirichlet b.c.
  • 3.12.2 Neumann b.c.
  • 3.12.3 The fourth order accuracy of P2 FEM as a finite difference scheme
  • 3.13 Efficient inversion of Laplacian in three dimensions
  • 3.14 Superconvergence
    • 3.14.1 The delta function
    • 3.14.2 The one-dimensional Green’s function
    • 3.14.3 Superconvergence at knots in one dimension
  • 3.15 Comparison with traditional finite difference method
    • 3.15.1 Advantages of the finite element method
    • 3.15.2 Limitations of the finite element method
• 4. Applications and examples on Cartesian grids
  4.1 Poisson solver in computational fluid dynamics
  • 4.1.1 Navier-Stokes equations in fluid dynamics
  • 4.1.2 Why Laplacian is hidden in incompressibility
  • 4.1.3 Project: incompressible flows with periodic boundary
  • 4.1.4 Project: Lid Driven Cavity flow
  • 4.1.5 Project: 3D Cahn-Hilliard equation in phase field models
  4.2 Total Variation norm for image processing
  • 4.2.1 Continuum ROF image denoising model
  • 4.2.2 Discrete ROF model
  • 4.2.3 Primal, dual and primal-dual forms
  • 4.2.4 Poisson solver in ADMM for the primal problem
  • 4.2.5 Poisson solver in DRS on the dual problem
  • 4.2.6 Project: ADMM for TV norm minimization
  • 4.3 Sobolev gradient flow for Gross-Pitaevskii eigenvalue problem
    • 4.3.1 The ground state eigenvalue problem
    • 4.3.2 The finite element method with quadrature
    • 4.3.3 The matrix-vector form
    • 4.3.4 Explicit finite difference formulation
    • 4.3.5 Gradient flow methods
    • 4.3.6 Project: gradient flows for the ground state
  • 4.4 Optimal Transport problems
    • 4.4.1 Dynamical formulation
    • 4.4.2 The convex formulation
    • 4.4.3 ADMM and Poisson solver
    • 4.4.4 Project: implement ADMM for optimal transport
• 5. A brief introduction to differential geometry
• 5.1 Defining surfaces and manifolds
• 5.2 Metrics on a manifold
• 5.3 Integration on manifolds
• 5.4 Differential operators on manifolds
• 5.5 Energy on manifolds
• 5.6 PDEs of interest
• 6. Laplacian on triangular mesh discretization of surfaces
• 6.1 Surfaces and triangular mesh representation
• 6.1.1 Barycentric coordinates in a triangle
• 6.1.2 Functions, vector fields, and operators on a triangle
• 6.1.3 Triangular meshes
• 6.2 Discrete differential operators on triangular meshes
• 6.2.1 Gradient on Triangle mesh
• 6.2.2 Discrete divergence
• 6.3 A finite element method for Laplacian on surface
• 6.3.1 Nodal basis, linear interpolation, and projection
• 6.3.2 Stiffness and mass matrices, and discrete Laplacian
• 6.3.3 * Random walk in two dimensions
• 6.4 Numerical PDEs on surfaces
• 6.4.1 Galerkin formulation for a surface Poisson problem
• 6.4.2 Numerical scheme for Poisson equation
• 6.4.3 Heat equation and the eigenvalue problem
• 6.5 *Error estimates of the surface finite element method
• 6.5.1 Projection, lift, and interpolation
• 6.5.2 Error estimates for the mean zero solution
• 7. Laplacian on point cloud representation of manifolds
• 7.1 Moving least square method for solving PDEs on manifolds represented by point clouds
• 7.1.1 Point cloud representation and local geometry
• 7.1.2 Moving least squares approximation of the manifold
• 7.1.3 Local polynomial approximation of functions
• 7.1.4 Discrete differential operators on point clouds
• 7.1.5 Solving PDEs on point clouds
• 7.2 Local mesh method on point clouds
• 7.2.1 Local mesh construction and differential operators
• 7.2.2 Finite element analogue
• 7.2.3 Solve equations on point clouds
7.3 Solving PDEs on incomplete-distance data
• 7.3.1 Problem setup and local coordinate reconstruction
• 7.3.2 Operator approximation from local reconstructions
• 7.3.3 Numerical examples
• 8. Applications of Laplacian on manifold-structured data
• 8.1 Image processing on surfaces
8.2 Computational optimal transport on manifolds
8.3 Shape analysis
• 8.3.1 Conformal parameterization for Genus-0 surfaces
• 8.3.2 Skeleton extraction from point clouds
• 8.3.3 Manifolds registration via Laplace-Beltrami eigen-maps
8.4 Committor function on point clouds
• Appendix A Linear algebra
• A.1 Eigenvalues and min-max principle
• A.2 Singular values and SVD
• A.3 Matrix norms
• A.4 Normal matrices
• Appendix B Iterative methods for solving linear systems
• B.1 Linear iterative methods
• B.2 Steepest descent
• B.3 The conjugate gradient method
• B.4 The preconditioned conjugate gradient method
Appendix C Splitting methods in convex minimization
• C.1 Indicator function and closed convex proper functions
• C.2 Proximal operator and Douglas-Rachford splitting
• C.3 Convex conjugate and Fenchel duality
• C.4 Douglas-Rachford splitting, ADMM and their equivalence
• Bibliography