Short description: none

This is a list of numerical analysis topics.

## Contents

* 1 General
* 2 Error
* 3 Elementary and special functions
* 4 Numerical linear algebra
* 4.1 Basic concepts
* 4.2 Solving systems of linear equations
* 4.3 Eigenvalue algorithms
* 4.4 Other concepts and algorithms
* 5 Interpolation and approximation
* 5.1 Polynomial interpolation
* 5.2 Spline interpolation
* 5.3 Trigonometric interpolation
* 5.4 Other interpolants
* 5.5 Approximation theory
* 5.6 Miscellaneous
* 6 Finding roots of nonlinear equations
* 7 Optimization
* 7.1 Basic concepts
* 7.2 Linear programming
* 7.3 Convex optimization
* 7.4 Nonlinear programming
* 7.5 Optimal control and infinite-dimensional optimization
* 7.6 Uncertainty and randomness
* 7.7 Theoretical aspects
* 7.8 Applications
* 7.9 Miscellaneous
* 8 Numerical quadrature (integration)
* 9 Numerical methods for ordinary differential equations
* 10 Numerical methods for partial differential equations
* 10.1 Finite difference methods
* 10.2 Finite element methods, gradient discretisation methods
* 10.3 Other methods
* 10.4 Techniques for improving these methods
* 10.5 Grids and meshes
* 10.6 Analysis
* 11 Monte Carlo method
* 12 Applications
* 13 Software
* 14 Journals
* 15 Researchers

## 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) — data structures for representing level sets
* Sinc numerical methods — methods based on the sinc function, sinc(x) = sin(x) / x
* ABS methods

## Error

Error analysis (mathematics)

* Approximation
* Approximation error
* Catastrophic cancellation
* 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 (numerical analysis)
* Relative change and difference — the relative difference between x and y is |x − y| / max(|x|, |y|)
* Significant figures
* False precision — giving more significant figures than appropriate
* Sterbenz lemma
* 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
* 2Sum
* 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 (reciprocal).
* 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 (x2 \+ y2)1/2
* Alpha max plus beta min algorithm — approximates hypot(x,y)
* Fast inverse square root — calculates 1 / √x using details of the IEEE floating-point system
* Elementary functions (exponential, logarithm, trigonometric 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 E-function Evaluation) — fast summation of series like the power series for ex
* 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

Numerical linear algebra — study of numerical algorithms for linear algebra problems

### 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

## Interpolation and approximation

Interpolation — construct a function going through some given data points

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

### Polynomial interpolation

Polynomial interpolation — interpolation by polynomials

* Linear interpolation
* Runge's phenomenon
* Vandermonde matrix
* Chebyshev polynomials
* Chebyshev nodes
* Lebesgue constant (interpolation)
* 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 R2 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 R3
* Bézier surface — maps a square to R3
* 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 2m 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−x0|)
* Polyharmonic spline — a commonly used radial basis function
* Thin plate spline — a specific polyharmonic spline: r2 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 L2-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 Lp 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−n xk 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 L2 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)

## Finding roots of nonlinear equations

See #Numerical linear algebra for linear equations

Root-finding algorithm — algorithms for solving the equation f(x) = 0

* 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 (but not necessarily positive definite) 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

Mathematical optimization — algorithm for finding maxima or minima of a given function

### 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 L1-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 xT 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 [math]\displaystyle{ f(x, y) = (x^2+y-11)^2 + (x+y^2-7)^2 }[/math]
* Rastrigin function — two-dimensional function with many local minima
* Shekel function — multimodal and multidimensional
* Mathematical Optimization Society

## Numerical quadrature (integration)

Numerical integration — the numerical evaluation of an integral

* Rectangle method — first-order method, based on (piecewise) constant approximation
* Trapezoidal rule — second-order method, based on (piecewise) linear approximation
* Simpson's rule — fourth-order method, based on (piecewise) 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 (1 − x2)±1/2 on [−1, 1]
* Gauss–Hermite quadrature — extension of Gaussian quadrature for integrals with weight exp(−x2) on [−∞, ∞]
* Gauss–Jacobi quadrature — extension of Gaussian quadrature for integrals with weight (1 − x)α (1 + x)β on [−1, 1]
* Gauss–Laguerre quadrature — extension of Gaussian quadrature for integrals with weight exp(−x) on [0, ∞]
* 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 (QSS) — 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

Numerical methods for ordinary differential equations — the numerical solution of ordinary differential equations (ODEs)

* 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 (FSAL) 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 (FSAL) 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 [math]\displaystyle{ y'' = f(t,y) }[/math]
* 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 (IVPs):
* Bi-directional delay line
* Partial element equivalent circuit
* Methods for solving two-point boundary value problems (BVPs):
* 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 (DAEs), 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 (SDEs):
* Euler–Maruyama method — generalization of the Euler method for SDEs
* Milstein method — a method with strong order one
* Runge–Kutta method (SDE) — 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 (numerical integration) — local and global truncation errors, and their relationships
* Lady Windermere's Fan (mathematics) — 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

Numerical partial differential equations — the numerical solution of partial differential equations (PDEs)

### 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

## 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 (CFD)
* 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 (CMHD) — 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 (DDAM) — for evaluating effect of underwater explosions on equipment
* Computational chemistry
* Cell lists
* Coupled cluster
* Density functional theory
* DIIS — direct inversion in (or of) the iterative subspace
* Computational sociology
* Computational statistics

## Software

For a large list of software, see the list of numerical-analysis software.

## Journals

* Acta Numerica
* Mathematics of Computation (published by the American Mathematical Society)
* 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