List of numerical analysis topics

General

• Validated numerics
• Iterative method
• Rate of convergence — the speed at which a convergent sequence approaches its limit
• *Order of accuracy — rate at which numerical solution of differential equation converges to exact solution
• Series acceleration — methods to accelerate the speed of convergence of a series
• *Aitken's delta-squared process — most useful for linearly converging sequences
• *Minimum polynomial extrapolation — for vector sequences
• *Richardson extrapolation
• *Shanks transformation — similar to Aitken's delta-squared process, but applied to the partial sums
• *Van Wijngaarden transformation — for accelerating the convergence of an alternating series
• Abramowitz and Stegun — book containing formulas and tables of many special functions
• *Digital Library of Mathematical Functions — successor of book by Abramowitz and Stegun
• Curse of dimensionality
• Local convergence and global convergence — whether you need a good initial guess to get convergence
• Superconvergence
• Discretization
• Difference quotient
• Complexity:
• *Computational complexity of mathematical operations
• *Smoothed analysis — measuring the expected performance of algorithms under slight random perturbations of worst-case inputs
• Symbolic-numeric computation — combination of symbolic and numeric methods
• Cultural and historical aspects:
• *History of numerical solution of differential equations using computers
• *Hundred-dollar, Hundred-digit Challenge problems — list of ten problems proposed by Nick Trefethen in 2002
• *International Workshops on Lattice QCD and Numerical Analysis
• *Timeline of numerical analysis after 1945
• General classes of methods:
• *Collocation method — discretizes a continuous equation by requiring it only to hold at certain points
• *Level-set method
• **Level set — data structures for representing level sets
• *Sinc numerical methods — methods based on the sinc function, sinc = sin / x
• *ABS methods

  Error

• Approximation
• Approximation error
• Condition number
• Discretization error
• Floating point number
• *Guard digit — extra precision introduced during a computation to reduce round-off error
• *Truncation — rounding a floating-point number by discarding all digits after a certain digit
• *Round-off error
• **Numeric precision in Microsoft Excel
• *Arbitrary-precision arithmetic
• Interval arithmetic — represent every number by two floating-point numbers guaranteed to have the unknown number between them
• *Interval contractor — maps interval to subinterval which still contains the unknown exact answer
• *Interval propagation — contracting interval domains without removing any value consistent with the constraints
• **See also: Interval boundary element method, Interval finite element
• Loss of significance
• Numerical error
• Numerical stability
• Error propagation:
• *Propagation of uncertainty
• **List of uncertainty propagation software
• *Significance arithmetic
• * Residual
• Relative change and difference — the relative difference between x and y is |x − y| / max
• Significant figures
• *False precision — giving more significant figures than appropriate
• Truncation error — error committed by doing only a finite numbers of steps
• Well-posed problem
• Affine arithmetic

  Elementary and special functions

• Unrestricted algorithm
• Summation:
• *Kahan summation algorithm
• *Pairwise summation — slightly worse than Kahan summation but cheaper
• *Binary splitting
• Multiplication:
• *Multiplication algorithm — general discussion, simple methods
• *Karatsuba algorithm — the first algorithm which is faster than straightforward multiplication
• *Toom–Cook multiplication — generalization of Karatsuba multiplication
• *Schönhage–Strassen algorithm — based on Fourier transform, asymptotically very fast
• *Fürer's algorithm — asymptotically slightly faster than Schönhage–Strassen
• Division algorithm — for computing quotient and/or remainder of two numbers
• *Long division
• *Restoring division
• *Non-restoring division
• *SRT division
• *Newton–Raphson division: uses Newton's method to find the reciprocal of D, and multiply that reciprocal by N to find the final quotient Q.
• *Goldschmidt division
• Exponentiation:
• *Exponentiation by squaring
• *Addition-chain exponentiation
• Multiplicative inverse Algorithms: for computing a number's multiplicative inverse.
• *Newton's method
• Polynomials:
• *Horner's method
• *Estrin's scheme — modification of the Horner scheme with more possibilities for parallelization
• *Clenshaw algorithm
• *De Casteljau's algorithm
• Square roots and other roots:
• *Integer square root
• *Methods of computing square roots
• *nth root algorithm
• *Shifting nth root algorithm — similar to long division
• *hypot — the function ^1/2
• *Alpha max plus beta min algorithm — approximates hypot
• *Fast inverse square root — calculates 1 / using details of the IEEE floating-point system
• Elementary functions :
• *Trigonometric tables — different methods for generating them
• *CORDIC — shift-and-add algorithm using a table of arc tangents
• *BKM algorithm — shift-and-add algorithm using a table of logarithms and complex numbers
• Gamma function:
• *Lanczos approximation
• *Spouge's approximation — modification of Stirling's approximation; easier to apply than Lanczos
• AGM method — computes arithmetic–geometric mean; related methods compute special functions
• FEE method — fast summation of series like the power series for e^x
• Gal's accurate tables — table of function values with unequal spacing to reduce round-off error
• Spigot algorithm — algorithms that can compute individual digits of a real number
• Approximations of :
• *Liu Hui's π algorithm — first algorithm that can compute π to arbitrary precision
• *Leibniz formula for π — alternating series with very slow convergence
• *Wallis product — infinite product converging slowly to π/2
• *Viète's formula — more complicated infinite product which converges faster
• *Gauss–Legendre algorithm — iteration which converges quadratically to π, based on arithmetic–geometric mean
• *Borwein's algorithm — iteration which converges quartically to 1/π, and other algorithms
• *Chudnovsky algorithm — fast algorithm that calculates a hypergeometric series
• *Bailey–Borwein–Plouffe formula — can be used to compute individual hexadecimal digits of π
• *Bellard's formula — faster version of Bailey–Borwein–Plouffe formula
• *List of formulae involving π

  Numerical linear algebra

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
• *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 — a technique to accelerate the Gauss–Seidel method
• ***Symmetric successive overrelaxation — 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 — 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
• **Biconjugate gradient stabilized method — variant of BiCG with better convergence
• *Conjugate residual method — similar to CG but only assumed that the matrix is symmetric
• *Generalized minimal residual method — based on the Arnoldi iteration
• *Chebyshev iteration — avoids inner products but needs bounds on the spectrum
• *Stone's method — 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 :
• *Numerical computation of null space — find all solutions of an underdetermined system
• *Moore–Penrose pseudoinverse — for finding solution with smallest 2-norm or smallest residual
• *Sparse approximation — for finding the sparsest solution

  Eigenvalue algorithms

• 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

  Interpolation and approximation

• Nearest-neighbor interpolation — takes the value of the nearest neighbor

  Polynomial interpolation

• Linear interpolation
• Runge's phenomenon
• Vandermonde matrix
• Chebyshev polynomials
• Chebyshev nodes
• Lebesgue constant
• 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 — 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
• *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 — a unique, affine, symmetric map associated to a polynomial or spline
• See also: List of numerical computational geometry topics

  Trigonometric interpolation

• Discrete Fourier transform — can be viewed as trigonometric interpolation at equidistant points
• *Relations between Fourier transforms and Fourier series
• Fast Fourier transform — 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 — a function of the form ƒ = φ
• *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 — 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

• Orders of approximation
• Lebesgue's lemma
• Curve fitting
• *Vector field reconstruction
• Modulus of continuity — measures smoothness of a function
• Least squares — minimizes the error in the L²-norm
• Minimax approximation algorithm — minimizes the maximum error over an interval
• *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 — 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 — 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

  Finding roots of nonlinear equations

• General methods:
• *Bisection method — simple and robust; linear convergence
• **Lehmer–Schur algorithm — variant for complex functions
• *Fixed-point iteration
• *Newton's method — based on linear approximation around the current iterate; quadratic convergence
• **Kantorovich theorem — gives a region around solution such that Newton's method converges
• **Newton fractal — indicates which initial condition converges to which root under Newton iteration
• **Quasi-Newton method — uses an approximation of the Jacobian:
• ***Broyden's method — uses a rank-one update for the Jacobian
• ***Symmetric rank-one — a symmetric rank-one update of the Jacobian
• ***Davidon–Fletcher–Powell formula — update of the Jacobian in which the matrix remains positive definite
• ***Broyden–Fletcher–Goldfarb–Shanno algorithm — rank-two update of the Jacobian in which the matrix remains positive definite
• ***Limited-memory BFGS method — truncated, matrix-free variant of BFGS method suitable for large problems
• **Steffensen's method — uses divided differences instead of the derivative
• *Secant method — based on linear interpolation at last two iterates
• *False position method — secant method with ideas from the bisection method
• *Muller's method — based on quadratic interpolation at last three iterates
• *Sidi's generalized secant method — higher-order variants of secant method
• *Inverse quadratic interpolation — similar to Muller's method, but interpolates the inverse
• *Brent's method — combines bisection method, secant method and inverse quadratic interpolation
• *Ridders' method — fits a linear function times an exponential to last two iterates and their midpoint
• *Halley's method — uses f, f' and f; achieves the cubic convergence
• *Householder's method — uses first d derivatives to achieve order d'' + 1; generalizes Newton's and Halley's method
• Methods for polynomials:
• *Aberth method
• *Bairstow's method
• *Durand–Kerner method
• *Graeffe's method
• *Jenkins–Traub algorithm — fast, reliable, and widely used
• *Laguerre's method
• *Splitting circle method
• Analysis:
• *Wilkinson's polynomial
• Numerical continuation — tracking a root as one parameter in the equation changes
• *Piecewise linear continuation

  Optimization

Basic concepts

• Active set
• Candidate solution
• Constraint
• *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

• Algorithms for linear programming:
• *Simplex algorithm
• **Bland's rule — rule to avoid cycling in the simplex method
• **Klee–Minty cube — perturbed 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
• Linear complementarity problem
• Decompositions:
• *Benders' decomposition
• *Dantzig–Wolfe decomposition
• *Theory of two-level planning
• *Variable splitting
• Basic solution — solution at vertex of feasible region
• Fourier–Motzkin elimination
• Hilbert basis — 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

• Quadratic programming
• *Linear least squares
• *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 — 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
• 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

• 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 — find x such that x ≥ 0, f ≥ 0 and x^T f = 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 — 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
• *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 — replace problem by a linear programming problem, solve that, and repeat
• *Sequential quadratic programming — 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
• **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 — 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" and "fine" models

  Optimal control and infinite-dimensional optimization

• Pontryagin's minimum principle — infinite-dimensional version of Lagrange multipliers
• *Costate equations — equation for the "Lagrange multipliers" in Pontryagin's minimum principle
• *Hamiltonian — 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 — 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
• *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

• 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 — uses an evolutionary algorithm for every agent
• **Simultaneous perturbation stochastic approximation
• *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 ≥ tf + f for t ∈
• *Pseudoconvex function — function f such that ∇f · ≥ 0 implies f ≥ f
• *Quasiconvex function — function f such that f ≤ max, f) for t ∈
• *Subderivative
• *Geodesic convexity — convexity for functions defined on a Riemannian manifold
• Duality
• *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 — 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 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 — 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
• *Rastrigin function — two-dimensional function with many local minima
• *Shekel function — multimodal and multidimensional
• Mathematical Optimization Society

  Numerical quadrature (integration)

• Rectangle method — first-order method, based on constant approximation
• Trapezoidal rule — second-order method, based on linear approximation
• Simpson's rule — fourth-order method, based on quadratic approximation
• *Adaptive Simpson's method
• Boole's rule — sixth-order method, based on the values at five equidistant points
• Newton–Cotes formulas — generalizes the above methods
• Romberg's method — Richardson extrapolation applied to trapezium rule
• Gaussian quadrature — highest possible degree with given number of points
• *Chebyshev–Gauss quadrature — extension of Gaussian quadrature for integrals with weight on
• *Gauss–Hermite quadrature — extension of Gaussian quadrature for integrals with weight exp on
• *Gauss–Jacobi quadrature — extension of Gaussian quadrature for integrals with weight ^{α β} on
• *Gauss–Laguerre quadrature — extension of Gaussian quadrature for integrals with weight exp on
• *Gauss–Kronrod quadrature formula — nested rule based on Gaussian quadrature
• *Gauss–Kronrod rules
• Tanh-sinh quadrature — variant of Gaussian quadrature which works well with singularities at the end points
• Clenshaw–Curtis quadrature — based on expanding the integrand in terms of Chebyshev polynomials
• Adaptive quadrature — adapting the subintervals in which the integration interval is divided depending on the integrand
• Monte Carlo integration — takes random samples of the integrand
• *See also #Monte Carlo method
• Quantized state systems method — based on the idea of state quantization
• Lebedev quadrature — uses a grid on a sphere with octahedral symmetry
• Sparse grid
• Coopmans approximation
• Numerical differentiation — for fractional-order integrals
• *Numerical smoothing and differentiation
• *Adjoint state method — approximates gradient of a function in an optimization problem
• Euler–Maclaurin formula

  Numerical methods for ordinary differential equations

• Euler method — the most basic method for solving an ODE
• Explicit and implicit methods — implicit methods need to solve an equation at every step
• Backward Euler method — implicit variant of the Euler method
• Trapezoidal rule — second-order implicit method
• Runge–Kutta methods — one of the two main classes of methods for initial-value problems
• *Midpoint method — a second-order method with two stages
• *Heun's method — either a second-order method with two stages, or a third-order method with three stages
• *Bogacki–Shampine method — a third-order method with four stages and an embedded fourth-order method
• *Cash–Karp method — a fifth-order method with six stages and an embedded fourth-order method
• *Dormand–Prince method — a fifth-order method with seven stages and an embedded fourth-order method
• *Runge–Kutta–Fehlberg method — a fifth-order method with six stages and an embedded fourth-order method
• *Gauss–Legendre method — family of A-stable method with optimal order based on Gaussian quadrature
• *Butcher group — algebraic formalism involving rooted trees for analysing Runge–Kutta methods
• *List of Runge–Kutta methods
• Linear multistep method — the other main class of methods for initial-value problems
• *Backward differentiation formula — implicit methods of order 2 to 6; especially suitable for stiff equations
• *Numerov's method — fourth-order method for equations of the form
• *Predictor–corrector method — uses one method to approximate solution and another one to increase accuracy
• General linear methods — a class of methods encapsulating linear multistep and Runge-Kutta methods
• Bulirsch–Stoer algorithm — combines the midpoint method with Richardson extrapolation to attain arbitrary order
• Exponential integrator — based on splitting ODE in a linear part, which is solved exactly, and a nonlinear part
• Methods designed for the solution of ODEs from classical physics:
• *Newmark-beta method — based on the extended mean-value theorem
• *Verlet integration — a popular second-order method
• *Leapfrog integration — another name for Verlet integration
• *Beeman's algorithm — a two-step method extending the Verlet method
• *Dynamic relaxation
• Geometric integrator — a method that preserves some geometric structure of the equation
• *Symplectic integrator — a method for the solution of Hamilton's equations that preserves the symplectic structure
• **Variational integrator — symplectic integrators derived using the underlying variational principle
• **Semi-implicit Euler method — variant of Euler method which is symplectic when applied to separable Hamiltonians
• *Energy drift — phenomenon that energy, which should be conserved, drifts away due to numerical errors
• Other methods for initial value problems :
• *Bi-directional delay line
• *Partial element equivalent circuit
• Methods for solving two-point boundary value problems :
• *Shooting method
• *Direct multiple shooting method — divides interval in several subintervals and applies the shooting method on each subinterval
• Methods for solving differential-algebraic equations, i.e., ODEs with constraints:
• *Constraint algorithm — for solving Newton's equations with constraints
• *Pantelides algorithm — for reducing the index of a DEA
• Methods for solving stochastic differential equations :
• *Euler–Maruyama method — generalization of the Euler method for SDEs
• *Milstein method — a method with strong order one
• *Runge–Kutta method — generalization of the family of Runge–Kutta methods for SDEs
• Methods for solving integral equations:
• *Nyström method — replaces the integral with a quadrature rule
• Analysis:
• *Truncation error — local and global truncation errors, and their relationships
• **Lady Windermere's Fan — telescopic identity relating local and global truncation errors
• Stiff equation — roughly, an ODE for which unstable methods need a very short step size, but stable methods do not
• *L-stability — method is A-stable and stability function vanishes at infinity
• Adaptive stepsize — automatically changing the step size when that seems advantageous
• Parareal -- a parallel-in-time integration algorithm

  Numerical methods for partial differential equations

Finite difference methods

• 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 — 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 — 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 — 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 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 — 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 — simple test for the quality of a finite element
• MAFELAP — 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 — 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 in order to avoid spurious oscillations
• *Riemann solver — a solver for Riemann problems
• *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 — represents solution as linear combination of fundamental solutions
• *Variants of MFS with source points on the physical boundary:
• **Boundary knot method
• **Boundary particle method
• **Regularized meshless method
• **Singular boundary method
• 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 — 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 — 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 — preconditioner for symmetric positive definite matrices
• *Balancing domain decomposition by constraints — further development of BDD
• *Finite element tearing and interconnect
• *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 — 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 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

  [Monte Carlo method]

• Variants of the Monte Carlo method:
• *Direct simulation Monte Carlo
• *Quasi-Monte Carlo method
• *Markov chain Monte Carlo
• **Metropolis–Hastings algorithm
• ***Multiple-try Metropolis — modification which allows larger step sizes
• ***Wang and Landau algorithm — extension of Metropolis Monte Carlo
• ***Equation of State Calculations by Fast Computing Machines — 1953 article proposing the Metropolis Monte Carlo algorithm
• ***Multicanonical ensemble — sampling technique that uses Metropolis–Hastings to compute integrals
• **Gibbs sampling
• **Coupling from the past
• **Reversible-jump Markov chain Monte Carlo
• *Dynamic Monte Carlo method
• **Kinetic Monte Carlo
• **Gillespie algorithm
• *Particle filter
• **Auxiliary particle filter
• *Reverse Monte Carlo
• *Demon algorithm
• Pseudo-random number sampling
• *Inverse transform sampling — general and straightforward method but computationally expensive
• *Rejection sampling — sample from a simpler distribution but reject some of the samples
• **Ziggurat algorithm — uses a pre-computed table covering the probability distribution with rectangular segments
• *For sampling from a normal distribution:
• **Box–Muller transform
• **Marsaglia polar method
• *Convolution random number generator — generates a random variable as a sum of other random variables
• *Indexed search
• Variance reduction techniques:
• *Antithetic variates
• *Control variates
• *Importance sampling
• *Stratified sampling
• *VEGAS algorithm
• Low-discrepancy sequence
• *Constructions of low-discrepancy sequences
• Event generator
• Parallel tempering
• Umbrella sampling — improves sampling in physical systems with significant energy barriers
• Hybrid Monte Carlo
• Ensemble Kalman filter — recursive filter suitable for problems with a large number of variables
• Transition path sampling
• Walk-on-spheres method — to generate exit-points of Brownian motion from bounded domains
• Applications:
• *Ensemble forecasting — produce multiple numerical predictions from slightly initial conditions or parameters
• *Bond fluctuation model — for simulating the conformation and dynamics of polymer systems
• *Iterated filtering
• *Metropolis light transport
• *Monte Carlo localization — estimates the position and orientation of a robot
• *Monte Carlo methods for electron transport
• *Monte Carlo method for photon transport
• *Monte Carlo methods in finance
• **Monte Carlo methods for option pricing
• **Quasi-Monte Carlo methods in finance
• *Monte Carlo molecular modeling
• **Path integral molecular dynamics — incorporates Feynman path integrals
• *Quantum Monte Carlo
• **Diffusion Monte Carlo — uses a Green function to solve the Schrödinger equation
• **Gaussian quantum Monte Carlo
• **Path integral Monte Carlo
• **Reptation Monte Carlo
• **Variational Monte Carlo
• *Methods for simulating the Ising model:
• **Swendsen–Wang algorithm — entire sample is divided into equal-spin clusters
• **Wolff algorithm — improvement of the Swendsen–Wang algorithm
• **Metropolis–Hastings algorithm
• *Auxiliary field Monte Carlo — computes averages of operators in many-body quantum mechanical problems
• *Cross-entropy method — for multi-extremal optimization and importance sampling
• Also see the list of statistics topics

  Applications

• Computational physics
• *Computational electromagnetics
• *Computational fluid dynamics
• **Numerical methods in fluid mechanics
• **Large eddy simulation
• **Smoothed-particle hydrodynamics
• **Aeroacoustic analogy — used in numerical aeroacoustics to reduce sound sources to simple emitter types
• **Stochastic Eulerian Lagrangian method — uses Eulerian description for fluids and Lagrangian for structures
• **Explicit algebraic stress model
• *Computational magnetohydrodynamics — studies electrically conducting fluids
• *Climate model
• *Numerical weather prediction
• **Geodesic grid
• *Celestial mechanics
• **Numerical model of the Solar System
• *Quantum jump method — used for simulating open quantum systems, operates on wave function
• *Dynamic design analysis method — for evaluating effect of underwater explosions on equipment
• Computational chemistry
• *Cell lists
• *Coupled cluster
• *Density functional theory
• *DIIS — direct inversion in the iterative subspace
• Computational sociology
• Computational statistics

  Software

Journals

• Acta Numerica
• Mathematics of Computation
• Journal of Computational and Applied Mathematics
• BIT Numerical Mathematics
• Numerische Mathematik
• Journals from the Society for Industrial and Applied Mathematics
• * SIAM Journal on Numerical Analysis
• * SIAM Journal on Scientific Computing

  Researchers

• Cleve Moler
• Gene H. Golub
• James H. Wilkinson
• Margaret H. Wright
• Nicholas J. Higham
• Nick Trefethen
• Peter Lax
• Richard S. Varga
• Ulrich W. Kulisch
• Vladik Kreinovich