Basic concepts

• Types of matrices appearing in numerical analysis:
  • Sparse matrix
    • Band matrix
    • Bidiagonal matrix
    • Tridiagonal matrix
    • Pentadiagonal matrix
    • Skyline matrix
  • Circulant matrix
  • Triangular matrix
  • Diagonally dominant matrix
  • Block matrix — matrix composed of smaller matrices
  • Stieltjes matrix — symmetric positive definite with non-positive off-diagonal entries
  • Hilbert matrix — example of a matrix which is extremely ill-conditioned (and thus difficult to handle)
  • Wilkinson matrix — example of a symmetric tridiagonal matrix with pairs of nearly, but not exactly, equal eigenvalues
  • Convergent matrix — square matrix whose successive powers approach the zero matrix
• Algorithms for matrix multiplication:
  • Strassen algorithm
  • Coppersmith–Winograd algorithm
  • Cannon's algorithm — a distributed algorithm, especially suitable for processors laid out in a 2d grid
  • Freivalds' algorithm — a randomized algorithm for checking the result of a multiplication
• Matrix decompositions:
  • LU decomposition — lower triangular times upper triangular
  • QR decomposition — orthogonal matrix times triangular matrix
    • RRQR factorization — rank-revealing QR factorization, can be used to compute rank of a matrix
  • Polar decomposition — unitary matrix times positive-semidefinite Hermitian matrix
  • Decompositions by similarity:
    • Eigendecomposition — decomposition in terms of eigenvectors and eigenvalues
    • Jordan normal form — bidiagonal matrix of a certain form; generalizes the eigendecomposition
      • Weyr canonical form — permutation of Jordan normal form
    • Jordan–Chevalley decomposition — sum of commuting nilpotent matrix and diagonalizable matrix
    • Schur decomposition — similarity transform bringing the matrix to a triangular matrix
  • Singular value decomposition — unitary matrix times diagonal matrix times unitary matrix
• Matrix splitting — expressing a given matrix as a sum or difference of matrices

Solving systems of linear equations

• Gaussian elimination
  • Row echelon form — matrix in which all entries below a nonzero entry are zero
  • Bareiss algorithm — variant which ensures that all entries remain integers if the initial matrix has integer entries
  • Tridiagonal matrix algorithm — simplified form of Gaussian elimination for tridiagonal matrices
• LU decomposition — write a matrix as a product of an upper- and a lower-triangular matrix
  • Crout matrix decomposition
  • LU reduction — a special parallelized version of a LU decomposition algorithm
• Block LU decomposition
• Cholesky decomposition — for solving a system with a positive definite matrix
  • Minimum degree algorithm
  • Symbolic Cholesky decomposition
• Iterative refinement — procedure to turn an inaccurate solution in a more accurate one
• Direct methods for sparse matrices:
  • Frontal solver — used in finite element methods
  • Nested dissection — for symmetric matrices, based on graph partitioning
• Levinson recursion — for Toeplitz matrices
• SPIKE algorithm — hybrid parallel solver for narrow-banded matrices
• Cyclic reduction — eliminate even or odd rows or columns, repeat
• Iterative methods:
  • Jacobi method
  • Gauss–Seidel method
    • Successive over-relaxation (SOR) — a technique to accelerate the Gauss–Seidel method
      • Symmetric successive over-relaxation (SSOR) — variant of SOR for symmetric matrices
    • Backfitting algorithm — iterative procedure used to fit a generalized additive model, often equivalent to Gauss–Seidel
  • Modified Richardson iteration
  • Conjugate gradient method (CG) — assumes that the matrix is positive definite
    • Derivation of the conjugate gradient method
    • Nonlinear conjugate gradient method — generalization for nonlinear optimization problems
  • Biconjugate gradient method (BiCG)
    • Biconjugate gradient stabilized method (BiCGSTAB) — variant of BiCG with better convergence
  • Conjugate residual method — similar to CG but only assumed that the matrix is symmetric
  • Generalized minimal residual method (GMRES) — based on the Arnoldi iteration
  • Chebyshev iteration — avoids inner products but needs bounds on the spectrum
  • Stone's method (SIP — Strongly Implicit Procedure) — uses an incomplete LU decomposition
  • Kaczmarz method
  • Preconditioner
    • Incomplete Cholesky factorization — sparse approximation to the Cholesky factorization
    • Incomplete LU factorization — sparse approximation to the LU factorization
  • Uzawa iteration — for saddle node problems
• Underdetermined and overdetermined systems (systems that have no or more than one solution):
  • Numerical computation of null space — find all solutions of an underdetermined system
  • Moore–Penrose pseudoinverse — for finding solution with smallest 2-norm (for underdetermined systems) or smallest residual
  • Sparse approximation — for finding the sparsest solution (i.e., the solution with as many zeros as possible)

Eigenvalue algorithms

Eigenvalue algorithm — a numerical algorithm for locating the eigenvalues of a matrix

• Power iteration
• Inverse iteration
• Rayleigh quotient iteration
• Arnoldi iteration — based on Krylov subspaces
• Lanczos algorithm — Arnoldi, specialized for positive-definite matrices
  • Block Lanczos algorithm — for when matrix is over a finite field
• QR algorithm
• Jacobi eigenvalue algorithm — select a small submatrix which can be diagonalized exactly, and repeat
  • Jacobi rotation — the building block, almost a Givens rotation
  • Jacobi method for complex Hermitian matrices
• Divide-and-conquer eigenvalue algorithm
• Folded spectrum method
• LOBPCG — Locally Optimal Block Preconditioned Conjugate Gradient Method
• Eigenvalue perturbation — stability of eigenvalues under perturbations of the matrix

Other concepts and algorithms

• Orthogonalization algorithms:
  • Gram–Schmidt process
  • Householder transformation
    • Householder operator — analogue of Householder transformation for general inner product spaces
  • Givens rotation
• Krylov subspace
• Block matrix pseudoinverse
• Bidiagonalization
• Cuthill–McKee algorithm — permutes rows/columns in sparse matrix to yield a narrow band matrix
• In-place matrix transposition — computing the transpose of a matrix without using much additional storage
• Pivot element — entry in a matrix on which the algorithm concentrates
• Matrix-free methods — methods that only access the matrix by evaluating matrix-vector products

Polynomial interpolation

Polynomial interpolation — interpolation by polynomials

• Linear interpolation
• Runge's phenomenon
• Vandermonde matrix
• Chebyshev polynomials
• Chebyshev nodes
• Lebesgue constants
• Different forms for the interpolant:
  • Newton polynomial
    • Divided differences
    • Neville's algorithm — for evaluating the interpolant; based on the Newton form
  • Lagrange polynomial
  • Bernstein polynomial — especially useful for approximation
  • Brahmagupta's interpolation formula — seventh-century formula for quadratic interpolation
• Extensions to multiple dimensions:
  • Bilinear interpolation
  • Trilinear interpolation
  • Bicubic interpolation
  • Tricubic interpolation
  • Padua points — set of points in R² with unique polynomial interpolant and minimal growth of Lebesgue constant
• Hermite interpolation
• Birkhoff interpolation
• Abel–Goncharov interpolation

Spline interpolation

Spline interpolation — interpolation by piecewise polynomials

• Spline (mathematics) — the piecewise polynomials used as interpolants
• Perfect spline — polynomial spline of degree m whose mth derivate is ±1
• Cubic Hermite spline
  • Centripetal Catmull–Rom spline — special case of cubic Hermite splines without self-intersections or cusps
• Monotone cubic interpolation
• Hermite spline
• Bézier curve
  • De Casteljau's algorithm
  • composite Bézier curve
  • Generalizations to more dimensions:
    • Bézier triangle — maps a triangle to R³
    • Bézier surface — maps a square to R³
• B-spline
  • Box spline — multivariate generalization of B-splines
  • Truncated power function
  • De Boor's algorithm — generalizes De Casteljau's algorithm
• Non-uniform rational B-spline (NURBS)
  • T-spline — can be thought of as a NURBS surface for which a row of control points is allowed to terminate
• Kochanek–Bartels spline
• Coons patch — type of manifold parametrization used to smoothly join other surfaces together
• M-spline — a non-negative spline
• I-spline — a monotone spline, defined in terms of M-splines
• Smoothing spline — a spline fitted smoothly to noisy data
• Blossom (functional) — a unique, affine, symmetric map associated to a polynomial or spline
• See also: List of numerical computational geometry topics

Trigonometric interpolation

Trigonometric interpolation — interpolation by trigonometric polynomials

• Discrete Fourier transform — can be viewed as trigonometric interpolation at equidistant points
  • Relations between Fourier transforms and Fourier series
• Fast Fourier transform (FFT) — a fast method for computing the discrete Fourier transform
  • Bluestein's FFT algorithm
  • Bruun's FFT algorithm
  • Cooley–Tukey FFT algorithm
  • Split-radix FFT algorithm — variant of Cooley–Tukey that uses a blend of radices 2 and 4
  • Goertzel algorithm
  • Prime-factor FFT algorithm
  • Rader's FFT algorithm
  • Bit-reversal permutation — particular permutation of vectors with 2^m entries used in many FFTs.
  • Butterfly diagram
  • Twiddle factor — the trigonometric constant coefficients that are multiplied by the data
  • Cyclotomic fast Fourier transform — for FFT over finite fields
  • Methods for computing discrete convolutions with finite impulse response filters using the FFT:
    • Overlap–add method
    • Overlap–save method
• Sigma approximation
• Dirichlet kernel — convolving any function with the Dirichlet kernel yields its trigonometric interpolant
• Gibbs phenomenon

Other interpolants

• Simple rational approximation
  • Polynomial and rational function modeling — comparison of polynomial and rational interpolation
• Wavelet
  • Continuous wavelet
  • Transfer matrix
  • See also: List of functional analysis topics, List of wavelet-related transforms
• Inverse distance weighting
• Radial basis function (RBF) — a function of the form ƒ(x) = φ(|x−x₀|)
  • Polyharmonic spline — a commonly used radial basis function
  • Thin plate spline — a specific polyharmonic spline: r² log r
  • Hierarchical RBF
• Subdivision surface — constructed by recursively subdividing a piecewise linear interpolant
  • Catmull–Clark subdivision surface
  • Doo–Sabin subdivision surface
  • Loop subdivision surface
• Slerp (spherical linear interpolation) — interpolation between two points on a sphere
  • Generalized quaternion interpolation — generalizes slerp for interpolation between more than two quaternions
• Irrational base discrete weighted transform
• Nevanlinna–Pick interpolation — interpolation by analytic functions in the unit disc subject to a bound
  • Pick matrix — the Nevanlinna–Pick interpolation has a solution if this matrix is positive semi-definite
• Multivariate interpolation — the function being interpolated depends on more than one variable
  • Barnes interpolation — method for two-dimensional functions using Gaussians common in meteorology
  • Coons surface — combination of linear interpolation and bilinear interpolation
  • Lanczos resampling — based on convolution with a sinc function
  • Natural neighbor interpolation
  • Nearest neighbor value interpolation
  • PDE surface
  • Transfinite interpolation — constructs function on planar domain given its values on the boundary
  • Trend surface analysis — based on low-order polynomials of spatial coordinates; uses scattered observations
  • Method based on polynomials are listed under Polynomial interpolation

Approximation theory

Approximation theory

• Orders of approximation
• Lebesgue's lemma
• Curve fitting
  • Vector field reconstruction
• Modulus of continuity — measures smoothness of a function
• Least squares (function approximation) — minimizes the error in the L²-norm
• Minimax approximation algorithm — minimizes the maximum error over an interval (the L^∞-norm)
  • Equioscillation theorem — characterizes the best approximation in the L^∞-norm
• Unisolvent point set — function from given function space is determined uniquely by values on such a set of points
• Stone–Weierstrass theorem — continuous functions can be approximated uniformly by polynomials, or certain other function spaces
• Approximation by polynomials:
  • Linear approximation
  • Bernstein polynomial — basis of polynomials useful for approximating a function
  • Bernstein's constant — error when approximating |x| by a polynomial
  • Remez algorithm — for constructing the best polynomial approximation in the L^∞-norm
  • Bernstein's inequality (mathematical analysis) — bound on maximum of derivative of polynomial in unit disk
  • Mergelyan's theorem — generalization of Stone–Weierstrass theorem for polynomials
  • Müntz–Szász theorem — variant of Stone–Weierstrass theorem for polynomials if some coefficients have to be zero
  • Bramble–Hilbert lemma — upper bound on L^p error of polynomial approximation in multiple dimensions
  • Discrete Chebyshev polynomials — polynomials orthogonal with respect to a discrete measure
  • Favard's theorem — polynomials satisfying suitable 3-term recurrence relations are orthogonal polynomials
• Approximation by Fourier series / trigonometric polynomials:
  • Jackson's inequality — upper bound for best approximation by a trigonometric polynomial
    • Bernstein's theorem (approximation theory) — a converse to Jackson's inequality
  • Fejér's theorem — Cesàro means of partial sums of Fourier series converge uniformly for continuous periodic functions
  • Erdős–Turán inequality — bounds distance between probability and Lebesgue measure in terms of Fourier coefficients
• Different approximations:
  • Moving least squares
  • Padé approximant
    • Padé table — table of Padé approximants
  • Hartogs–Rosenthal theorem — continuous functions can be approximated uniformly by rational functions on a set of Lebesgue measure zero
  • Szász–Mirakyan operator — approximation by e⁻ⁿ x^k on a semi-infinite interval
  • Szász–Mirakjan–Kantorovich operator
  • Baskakov operator — generalize Bernstein polynomials, Szász–Mirakyan operators, and Lupas operators
  • Favard operator — approximation by sums of Gaussians
• Surrogate model — application: replacing a function that is hard to evaluate by a simpler function
• Constructive function theory — field that studies connection between degree of approximation and smoothness
• Universal differential equation — differential–algebraic equation whose solutions can approximate any continuous function
• Fekete problem — find N points on a sphere that minimize some kind of energy
• Carleman's condition — condition guaranteeing that a measure is uniquely determined by its moments
• Krein's condition — condition that exponential sums are dense in weighted L² space
• Lethargy theorem — about distance of points in a metric space from members of a sequence of subspaces
• Wirtinger's representation and projection theorem
• Journals:
  • Constructive Approximation
  • Journal of Approximation Theory

Miscellaneous

• Extrapolation
  • Linear predictive analysis — linear extrapolation
• Unisolvent functions — functions for which the interpolation problem has a unique solution
• Regression analysis
  • Isotonic regression
• Curve-fitting compaction
• Interpolation (computer graphics)

Basic concepts

• Active set
• Candidate solution
• Constraint (mathematics)
  • Constrained optimization — studies optimization problems with constraints
  • Binary constraint — a constraint that involves exactly two variables
• Corner solution
• Feasible region — contains all solutions that satisfy the constraints but may not be optimal
• Global optimum and Local optimum
• Maxima and minima
• Slack variable
• Continuous optimization
• Discrete optimization

Linear programming

Linear programming (also treats integer programming) — objective function and constraints are linear

• Algorithms for linear programming:
  • Simplex algorithm
    • Bland's rule — rule to avoid cycling in the simplex method
    • Klee–Minty cube — perturbed (hyper)cube; simplex method has exponential complexity on such a domain
    • Criss-cross algorithm — similar to the simplex algorithm
    • Big M method — variation of simplex algorithm for problems with both "less than" and "greater than" constraints
  • Interior point method
    • Ellipsoid method
    • Karmarkar's algorithm
    • Mehrotra predictor–corrector method
  • Column generation
  • k-approximation of k-hitting set — algorithm for specific LP problems (to find a weighted hitting set)
• Linear complementarity problem
• Decompositions:
  • Benders' decomposition
  • Dantzig–Wolfe decomposition
  • Theory of two-level planning
  • Variable splitting
• Basic solution (linear programming) — solution at vertex of feasible region
• Fourier–Motzkin elimination
• Hilbert basis (linear programming) — set of integer vectors in a convex cone which generate all integer vectors in the cone
• LP-type problem
• Linear inequality
• Vertex enumeration problem — list all vertices of the feasible set

Convex optimization

Convex optimization

• Quadratic programming
  • Linear least squares (mathematics)
  • Total least squares
  • Frank–Wolfe algorithm
  • Sequential minimal optimization — breaks up large QP problems into a series of smallest possible QP problems
  • Bilinear program
• Basis pursuit — minimize L₁-norm of vector subject to linear constraints
  • Basis pursuit denoising (BPDN) — regularized version of basis pursuit
    • In-crowd algorithm — algorithm for solving basis pursuit denoising
• Linear matrix inequality
• Conic optimization
  • Semidefinite programming
  • Second-order cone programming
  • Sum-of-squares optimization
  • Quadratic programming (see above)
• Bregman method — row-action method for strictly convex optimization problems
• Proximal gradient method — use splitting of objective function in sum of possible non-differentiable pieces
• Subgradient method — extension of steepest descent for problems with a non-differentiable objective function
• Biconvex optimization — generalization where objective function and constraint set can be biconvex

Nonlinear programming

Nonlinear programming — the most general optimization problem in the usual framework

• Special cases of nonlinear programming:
  • See Linear programming and Convex optimization above
  • Geometric programming — problems involving signomials or posynomials
    • Signomial — similar to polynomials, but exponents need not be integers
    • Posynomial — a signomial with positive coefficients
  • Quadratically constrained quadratic program
  • Linear-fractional programming — objective is ratio of linear functions, constraints are linear
    • Fractional programming — objective is ratio of nonlinear functions, constraints are linear
  • Nonlinear complementarity problem (NCP) — find x such that x ≥ 0, f(x) ≥ 0 and x^T f(x) = 0
  • Least squares — the objective function is a sum of squares
    • Non-linear least squares
    • Gauss–Newton algorithm
      • BHHH algorithm — variant of Gauss–Newton in econometrics
      • Generalized Gauss–Newton method — for constrained nonlinear least-squares problems
    • Levenberg–Marquardt algorithm
    • Iteratively reweighted least squares (IRLS) — solves a weighted least-squares problem at every iteration
    • Partial least squares — statistical techniques similar to principal components analysis
      • Non-linear iterative partial least squares (NIPLS)
  • Mathematical programming with equilibrium constraints — constraints include variational inequalities or complementarities
  • Univariate optimization:
    • Golden section search
    • Successive parabolic interpolation — based on quadratic interpolation through the last three iterates
• General algorithms:
  • Concepts:
    • Descent direction
    • Guess value — the initial guess for a solution with which an algorithm starts
    • Line search
      • Backtracking line search
      • Wolfe conditions
  • Gradient method — method that uses the gradient as the search direction
    • Gradient descent
      • Stochastic gradient descent
    • Landweber iteration — mainly used for ill-posed problems
  • Successive linear programming (SLP) — replace problem by a linear programming problem, solve that, and repeat
  • Sequential quadratic programming (SQP) — replace problem by a quadratic programming problem, solve that, and repeat
  • Newton's method in optimization
    • See also under Newton algorithm in the section Finding roots of nonlinear equations
  • Nonlinear conjugate gradient method
  • Derivative-free methods
    • Coordinate descent — move in one of the coordinate directions
      • Adaptive coordinate descent — adapt coordinate directions to objective function
      • Random coordinate descent — randomized version
    • Nelder–Mead method
    • Pattern search (optimization)
    • Powell's method — based on conjugate gradient descent
    • Rosenbrock methods — derivative-free method, similar to Nelder–Mead but with guaranteed convergence
  • Augmented Lagrangian method — replaces constrained problems by unconstrained problems with a term added to the objective function
  • Ternary search
  • Tabu search
  • Guided Local Search — modification of search algorithms which builds up penalties during a search
  • Reactive search optimization (RSO) — the algorithm adapts its parameters automatically
  • MM algorithm — majorize-minimization, a wide framework of methods
  • Least absolute deviations
    • Expectation–maximization algorithm
      • Ordered subset expectation maximization
  • Nearest neighbor search
  • Space mapping — uses "coarse" (ideal or low-fidelity) and "fine" (practical or high-fidelity) models

Optimal control and infinite-dimensional optimization

Optimal control

• Pontryagin's minimum principle — infinite-dimensional version of Lagrange multipliers
  • Costate equations — equation for the "Lagrange multipliers" in Pontryagin's minimum principle
  • Hamiltonian (control theory) — minimum principle says that this function should be minimized
• Types of problems:
  • Linear-quadratic regulator — system dynamics is a linear differential equation, objective is quadratic
  • Linear-quadratic-Gaussian control (LQG) — system dynamics is a linear SDE with additive noise, objective is quadratic
    • Optimal projection equations — method for reducing dimension of LQG control problem
• Algebraic Riccati equation — matrix equation occurring in many optimal control problems
• Bang–bang control — control that switches abruptly between two states
• Covector mapping principle
• Differential dynamic programming — uses locally-quadratic models of the dynamics and cost functions
• DNSS point — initial state for certain optimal control problems with multiple optimal solutions
• Legendre–Clebsch condition — second-order condition for solution of optimal control problem
• Pseudospectral optimal control
  • Bellman pseudospectral method — based on Bellman's principle of optimality
  • Chebyshev pseudospectral method — uses Chebyshev polynomials (of the first kind)
  • Flat pseudospectral method — combines Ross–Fahroo pseudospectral method with differential flatness
  • Gauss pseudospectral method — uses collocation at the Legendre–Gauss points
  • Legendre pseudospectral method — uses Legendre polynomials
  • Pseudospectral knotting method — generalization of pseudospectral methods in optimal control
  • Ross–Fahroo pseudospectral method — class of pseudospectral method including Chebyshev, Legendre and knotting
• Ross–Fahroo lemma — condition to make discretization and duality operations commute
• Ross' π lemma — there is fundamental time constant within which a control solution must be computed for controllability and stability
• Sethi model — optimal control problem modelling advertising

Infinite-dimensional optimization

• Semi-infinite programming — infinite number of variables and finite number of constraints, or other way around
• Shape optimization, Topology optimization — optimization over a set of regions
  • Topological derivative — derivative with respect to changing in the shape
• Generalized semi-infinite programming — finite number of variables, infinite number of constraints

Uncertainty and randomness

• Approaches to deal with uncertainty:
  • Markov decision process
  • Partially observable Markov decision process
  • Robust optimization
    • Wald's maximin model
  • Scenario optimization — constraints are uncertain
  • Stochastic approximation
  • Stochastic optimization
  • Stochastic programming
  • Stochastic gradient descent
• Random optimization algorithms:
  • Random search — choose a point randomly in ball around current iterate
  • Simulated annealing
    • Adaptive simulated annealing — variant in which the algorithm parameters are adjusted during the computation.
    • Great Deluge algorithm
    • Mean field annealing — deterministic variant of simulated annealing
  • Bayesian optimization — treats objective function as a random function and places a prior over it
  • Evolutionary algorithm
    • Differential evolution
    • Evolutionary programming
    • Genetic algorithm, Genetic programming
      • Genetic algorithms in economics
    • MCACEA (Multiple Coordinated Agents Coevolution Evolutionary Algorithm) — uses an evolutionary algorithm for every agent
    • Simultaneous perturbation stochastic approximation (SPSA)
  • Luus–Jaakola
  • Particle swarm optimization
  • Stochastic tunneling
  • Harmony search — mimicks the improvisation process of musicians
  • see also the section Monte Carlo method

Theoretical aspects

• Convex analysis — function f such that f(tx + (1 − t)y) ≥ tf(x) + (1 − t)f(y) for t ∈ [0,1]
  • Pseudoconvex function — function f such that ∇f · (y − x) ≥ 0 implies f(y) ≥ f(x)
  • Quasiconvex function — function f such that f(tx + (1 − t)y) ≤ max(f(x), f(y)) for t ∈ [0,1]
  • Subderivative
  • Geodesic convexity — convexity for functions defined on a Riemannian manifold
• Duality (optimization)
  • Weak duality — dual solution gives a bound on the primal solution
  • Strong duality — primal and dual solutions are equivalent
  • Shadow price
  • Dual cone and polar cone
  • Duality gap — difference between primal and dual solution
  • Fenchel's duality theorem — relates minimization problems with maximization problems of convex conjugates
  • Perturbation function — any function which relates to primal and dual problems
  • Slater's condition — sufficient condition for strong duality to hold in a convex optimization problem
  • Total dual integrality — concept of duality for integer linear programming
  • Wolfe duality — for when objective function and constraints are differentiable
• Farkas' lemma
• Karush–Kuhn–Tucker conditions (KKT) — sufficient conditions for a solution to be optimal
  • Fritz John conditions — variant of KKT conditions
• Lagrange multiplier
  • Lagrange multipliers on Banach spaces
• Semi-continuity
• Complementarity theory — study of problems with constraints of the form ⟨u, v⟩ = 0
  • Mixed complementarity problem
    • Mixed linear complementarity problem
    • Lemke's algorithm — method for solving (mixed) linear complementarity problems
• Danskin's theorem — used in the analysis of minimax problems
• Maximum theorem — the maximum and maximizer are continuous as function of parameters, under some conditions
• No free lunch in search and optimization
• Relaxation (approximation) — approximating a given problem by an easier problem by relaxing some constraints
  • Lagrangian relaxation
  • Linear programming relaxation — ignoring the integrality constraints in a linear programming problem
• Self-concordant function
• Reduced cost — cost for increasing a variable by a small amount
• Hardness of approximation — computational complexity of getting an approximate solution

Applications

• In geometry:
  • Geometric median — the point minimizing the sum of distances to a given set of points
  • Chebyshev center — the centre of the smallest ball containing a given set of points
• In statistics:
  • Iterated conditional modes — maximizing joint probability of Markov random field
  • Response surface methodology — used in the design of experiments
• Automatic label placement
• Compressed sensing — reconstruct a signal from knowledge that it is sparse or compressible
• Cutting stock problem
• Demand optimization
• Destination dispatch — an optimization technique for dispatching elevators
• Energy minimization
• Entropy maximization
• Highly optimized tolerance
• Hyperparameter optimization
• Inventory control problem
  • Newsvendor model
  • Extended newsvendor model
  • Assemble-to-order system
• Linear programming decoding
• Linear search problem — find a point on a line by moving along the line
• Low-rank approximation — find best approximation, constraint is that rank of some matrix is smaller than a given number
• Meta-optimization — optimization of the parameters in an optimization method
• Multidisciplinary design optimization
• Optimal computing budget allocation — maximize the overall simulation efficiency for finding an optimal decision
• Paper bag problem
• Process optimization
• Recursive economics — individuals make a series of two-period optimization decisions over time.
• Stigler diet
• Space allocation problem
• Stress majorization
• Trajectory optimization
• Transportation theory
• Wing-shape optimization

Miscellaneous

• Combinatorial optimization
• Dynamic programming
  • Bellman equation
  • Hamilton–Jacobi–Bellman equation — continuous-time analogue of Bellman equation
  • Backward induction — solving dynamic programming problems by reasoning backwards in time
  • Optimal stopping — choosing the optimal time to take a particular action
    • Odds algorithm
    • Robbins' problem
• Global optimization:
  • BRST algorithm
  • MCS algorithm
• Multi-objective optimization — there are multiple conflicting objectives
  • Benson's algorithm — for linear vector optimization problems
• Bilevel optimization — studies problems in which one problem is embedded in another
• Optimal substructure
• Dykstra's projection algorithm — finds a point in intersection of two convex sets
• Algorithmic concepts:
  • Barrier function
  • Penalty method
  • Trust region
• Test functions for optimization:
  • Rosenbrock function — two-dimensional function with a banana-shaped valley
  • Himmelblau's function — two-dimensional with four local minima, defined by ${\displaystyle f(x,y)=(x^{2}+y-11)^{2}+(x+y^{2}-7)^{2}}$
  • Rastrigin function — two-dimensional function with many local minima
  • Shekel function — multimodal and multidimensional
• Mathematical Optimization Society

Finite difference methods

Finite difference method — based on approximating differential operators with difference operators

• Finite difference — the discrete analogue of a differential operator
  • Finite difference coefficient — table of coefficients of finite-difference approximations to derivatives
  • Discrete Laplace operator — finite-difference approximation of the Laplace operator
    • Eigenvalues and eigenvectors of the second derivative — includes eigenvalues of discrete Laplace operator
    • Kronecker sum of discrete Laplacians — used for Laplace operator in multiple dimensions
  • Discrete Poisson equation — discrete analogue of the Poisson equation using the discrete Laplace operator
• Stencil (numerical analysis) — the geometric arrangements of grid points affected by a basic step of the algorithm
  • Compact stencil — stencil which only uses a few grid points, usually only the immediate and diagonal neighbours
    • Higher-order compact finite difference scheme
  • Non-compact stencil — any stencil that is not compact
  • Five-point stencil — two-dimensional stencil consisting of a point and its four immediate neighbours on a rectangular grid
• Finite difference methods for heat equation and related PDEs:
  • FTCS scheme (forward-time central-space) — first-order explicit
  • Crank–Nicolson method — second-order implicit
• Finite difference methods for hyperbolic PDEs like the wave equation:
  • Lax–Friedrichs method — first-order explicit
  • Lax–Wendroff method — second-order explicit
  • MacCormack method — second-order explicit
  • Upwind scheme
    • Upwind differencing scheme for convection — first-order scheme for convection–diffusion problems
  • Lax–Wendroff theorem — conservative scheme for hyperbolic system of conservation laws converges to the weak solution
• Alternating direction implicit method (ADI) — update using the flow in x-direction and then using flow in y-direction
• Nonstandard finite difference scheme
• Specific applications:
  • Finite difference methods for option pricing
  • Finite-difference time-domain method — a finite-difference method for electrodynamics

Finite element methods, gradient discretisation methods

Finite element method — based on a discretization of the space of solutions gradient discretisation method — based on both the discretization of the solution and of its gradient

• Finite element method in structural mechanics — a physical approach to finite element methods
• Galerkin method — a finite element method in which the residual is orthogonal to the finite element space
  • Discontinuous Galerkin method — a Galerkin method in which the approximate solution is not continuous
• Rayleigh–Ritz method — a finite element method based on variational principles
• Spectral element method — high-order finite element methods
• hp-FEM — variant in which both the size and the order of the elements are automatically adapted
• Examples of finite elements:
  • Bilinear quadrilateral element — also known as the Q4 element
  • Constant strain triangle element (CST) — also known as the T3 element
  • Quadratic quadrilateral element — also known as the Q8 element
  • Barsoum elements
• Direct stiffness method — a particular implementation of the finite element method, often used in structural analysis
• Trefftz method
• Finite element updating
• Extended finite element method — puts functions tailored to the problem in the approximation space
• Functionally graded elements — elements for describing functionally graded materials
• Superelement — particular grouping of finite elements, employed as a single element
• Interval finite element method — combination of finite elements with interval arithmetic
• Discrete exterior calculus — discrete form of the exterior calculus of differential geometry
• Modal analysis using FEM — solution of eigenvalue problems to find natural vibrations
• Céa's lemma — solution in the finite-element space is an almost best approximation in that space of the true solution
• Patch test (finite elements) — simple test for the quality of a finite element
• MAFELAP (MAthematics of Finite ELements and APplications) — international conference held at Brunel University
• NAFEMS — not-for-profit organisation that sets and maintains standards in computer-aided engineering analysis
• Multiphase topology optimisation — technique based on finite elements for determining optimal composition of a mixture
• Interval finite element
• Applied element method — for simulation of cracks and structural collapse
• Wood–Armer method — structural analysis method based on finite elements used to design reinforcement for concrete slabs
• Isogeometric analysis — integrates finite elements into conventional NURBS-based CAD design tools
• Loubignac iteration
• Stiffness matrix — finite-dimensional analogue of differential operator
• Combination with meshfree methods:
  • Weakened weak form — form of a PDE that is weaker than the standard weak form
  • G space — functional space used in formulating the weakened weak form
  • Smoothed finite element method
• Variational multiscale method
• List of finite element software packages

Other methods

• Spectral method — based on the Fourier transformation
  • Pseudo-spectral method
• Method of lines — reduces the PDE to a large system of ordinary differential equations
• Boundary element method (BEM) — based on transforming the PDE to an integral equation on the boundary of the domain
  • Interval boundary element method — a version using interval arithmetics
• Analytic element method — similar to the boundary element method, but the integral equation is evaluated analytically
• Finite volume method — based on dividing the domain in many small domains; popular in computational fluid dynamics
  • Godunov's scheme — first-order conservative scheme for fluid flow, based on piecewise constant approximation
  • MUSCL scheme — second-order variant of Godunov's scheme
  • AUSM — advection upstream splitting method
  • Flux limiter — limits spatial derivatives (fluxes) in order to avoid spurious oscillations
  • Riemann solver — a solver for Riemann problems (a conservation law with piecewise constant data)
  • Properties of discretization schemes — finite volume methods can be conservative, bounded, etc.
• Discrete element method — a method in which the elements can move freely relative to each other
  • Extended discrete element method — adds properties such as strain to each particle
  • Movable cellular automaton — combination of cellular automata with discrete elements
• Meshfree methods — does not use a mesh, but uses a particle view of the field
  • Discrete least squares meshless method — based on minimization of weighted summation of the squared residual
  • Diffuse element method
  • Finite pointset method — represent continuum by a point cloud
  • Moving Particle Semi-implicit Method
  • Method of fundamental solutions (MFS) — represents solution as linear combination of fundamental solutions
  • Variants of MFS with source points on the physical boundary:
    • Boundary knot method (BKM)
    • Boundary particle method (BPM)
    • Regularized meshless method (RMM)
    • Singular boundary method (SBM)
• Methods designed for problems from electromagnetics:
  • Finite-difference time-domain method — a finite-difference method
  • Rigorous coupled-wave analysis — semi-analytical Fourier-space method based on Floquet's theorem
  • Transmission-line matrix method (TLM) — based on analogy between electromagnetic field and mesh of transmission lines
  • Uniform theory of diffraction — specifically designed for scattering problems
• Particle-in-cell — used especially in fluid dynamics
  • Multiphase particle-in-cell method — considers solid particles as both numerical particles and fluid
• High-resolution scheme
• Shock capturing method
• Vorticity confinement — for vortex-dominated flows in fluid dynamics, similar to shock capturing
• Split-step method
• Fast marching method
• Orthogonal collocation
• Lattice Boltzmann methods — for the solution of the Navier-Stokes equations
• Roe solver — for the solution of the Euler equation
• Relaxation (iterative method) — a method for solving elliptic PDEs by converting them to evolution equations
• Broad classes of methods:
  • Mimetic methods — methods that respect in some sense the structure of the original problem
  • Multiphysics — models consisting of various submodels with different physics
  • Immersed boundary method — for simulating elastic structures immersed within fluids
• Multisymplectic integrator — extension of symplectic integrators, which are for ODEs
• Stretched grid method — for problems solution that can be related to an elastic grid behavior.

Techniques for improving these methods

• Multigrid method — uses a hierarchy of nested meshes to speed up the methods
• Domain decomposition methods — divides the domain in a few subdomains and solves the PDE on these subdomains
  • Additive Schwarz method
  • Abstract additive Schwarz method — abstract version of additive Schwarz without reference to geometric information
  • Balancing domain decomposition method (BDD) — preconditioner for symmetric positive definite matrices
  • Balancing domain decomposition by constraints (BDDC) — further development of BDD
  • Finite element tearing and interconnect (FETI)
  • FETI-DP — further development of FETI
  • Fictitious domain method — preconditioner constructed with a structured mesh on a fictitious domain of simple shape
  • Mortar methods — meshes on subdomain do not mesh
  • Neumann–Dirichlet method — combines Neumann problem on one subdomain with Dirichlet problem on other subdomain
  • Neumann–Neumann methods — domain decomposition methods that use Neumann problems on the subdomains
  • Poincaré–Steklov operator — maps tangential electric field onto the equivalent electric current
  • Schur complement method — early and basic method on subdomains that do not overlap
  • Schwarz alternating method — early and basic method on subdomains that overlap
• Coarse space — variant of the problem which uses a discretization with fewer degrees of freedom
• Adaptive mesh refinement — uses the computed solution to refine the mesh only where necessary
• Fast multipole method — hierarchical method for evaluating particle-particle interactions
• Perfectly matched layer — artificial absorbing layer for wave equations, used to implement absorbing boundary conditions

Grids and meshes

• Grid classification / Types of mesh:
  • Polygon mesh — consists of polygons in 2D or 3D
  • Triangle mesh — consists of triangles in 2D or 3D
    • Triangulation (geometry) — subdivision of given region in triangles, or higher-dimensional analogue
    • Nonobtuse mesh — mesh in which all angles are less than or equal to 90°
    • Point-set triangulation — triangle mesh such that given set of point are all a vertex of a triangle
    • Polygon triangulation — triangle mesh inside a polygon
    • Delaunay triangulation — triangulation such that no vertex is inside the circumcentre of a triangle
    • Constrained Delaunay triangulation — generalization of the Delaunay triangulation that forces certain required segments into the triangulation
    • Pitteway triangulation — for any point, triangle containing it has nearest neighbour of the point as a vertex
    • Minimum-weight triangulation — triangulation of minimum total edge length
    • Kinetic triangulation — a triangulation that moves over time
    • Triangulated irregular network
    • Quasi-triangulation — subdivision into simplices, where vertices are not points but arbitrary sloped line segments
  • Volume mesh — consists of three-dimensional shapes
  • Regular grid — consists of congruent parallelograms, or higher-dimensional analogue
  • Unstructured grid
  • Geodesic grid — isotropic grid on a sphere
• Mesh generation
  • Image-based meshing — automatic procedure of generating meshes from 3D image data
  • Marching cubes — extracts a polygon mesh from a scalar field
  • Parallel mesh generation
  • Ruppert's algorithm — creates quality Delauney triangularization from piecewise linear data
• Subdivisions:
• Apollonian network — undirected graph formed by recursively subdividing a triangle
• Barycentric subdivision — standard way of dividing arbitrary convex polygons into triangles, or the higher-dimensional analogue
• Improving an existing mesh:
  • Chew's second algorithm — improves Delauney triangularization by refining poor-quality triangles
  • Laplacian smoothing — improves polynomial meshes by moving the vertices
• Jump-and-Walk algorithm — for finding triangle in a mesh containing a given point
• Spatial twist continuum — dual representation of a mesh consisting of hexahedra
• Pseudotriangle — simply connected region between any three mutually tangent convex sets
• Simplicial complex — all vertices, line segments, triangles, tetrahedra, ..., making up a mesh

Analysis

• Lax equivalence theorem — a consistent method is convergent if and only if it is stable
• Courant–Friedrichs–Lewy condition — stability condition for hyperbolic PDEs
• Von Neumann stability analysis — all Fourier components of the error should be stable
• Numerical diffusion — diffusion introduced by the numerical method, above to that which is naturally present
  • False diffusion
• Numerical dispersion
• Numerical resistivity — the same, with resistivity instead of diffusion
• Weak formulation — a functional-analytic reformulation of the PDE necessary for some methods
• Total variation diminishing — property of schemes that do not introduce spurious oscillations
• Godunov's theorem — linear monotone schemes can only be of first order
• Motz's problem — benchmark problem for singularity problems