List Of Numerical Analysis Topics

This is a 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) — 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
** ''n''th root algorithm
** Shifting ''n''th root algorithm — similar to long division
**hypot — the function (''x''² + ''y''²)^1/2
** Alpha max plus beta min algorithm — approximates hypot(x,y)
** Fast inverse square root — calculates 1 / 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 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

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 R² with unique polynomial interpolant and minimal growth of Lebesgue constant
*Hermite interpolation
* Birkhoff interpolation
* Abel–Goncharov interpolation

Spline interpolation

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

Trigonometric interpolation

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

Other interpolants

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

Approximation theory

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

Miscellaneous

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

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 L₁-norm of vector subject to linear constraints
**Basis pursuit denoising (BPDN) — regularized version of basis pursuit
*** In-crowd algorithm — algorithm for solving basis pursuit denoising
*Linear matrix inequality
* Conic optimization
**Semidefinite programming
**Second-order cone programming
** Sum-of-squares optimization
**Quadratic programming (see above)
*Bregman method — row-action method for strictly convex optimization problems
*Proximal gradient method — use splitting of objective function in sum of possible non-differentiable pieces
* Subgradient method — extension of steepest descent for problems with a non-differentiable objective function
* Biconvex optimization — generalization where objective function and constraint set can be biconvex

Nonlinear programming

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

Optimal control and infinite-dimensional optimization

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

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

Uncertainty and randomness

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

Theoretical aspects

*Convex analysis — function ''f'' such that ''f''(''tx'' + (1 − ''t'')''y'') ≥ ''tf''(''x'') + (1 − ''t'')''f''(''y'') for ''t'' ∈ ,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'' ∈ ,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 $f(x, y) = (x^2+y-11)^2 + (x+y^2-7)^2$
** Rastrigin function — two-dimensional function with many local minima
** Shekel function — multimodal and multidimensional
*Mathematical Optimization Society — 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 {{nowrap, (1 − ''x''²)^±1/2 on ��1, 1**Gauss–Hermite quadrature — extension of Gaussian quadrature for integrals with weight exp(−''x''²) 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 , ∞** 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 $y'' = f(t,y)$
**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:
**Mimesis (mathematics), 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
**BDDC, Balancing domain decomposition by constraints (BDDC) — further development of BDD
**FETI, 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 (numerical analysis), 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 Higham, Nicholas J. Higham
*Nick Trefethen
*Peter Lax
*Richard S. Varga
*Ulrich W. Kulisch
*Vladik Kreinovich

Numerical analysis, *Topics
Mathematics-related lists, Numerical analysis topics
Outlines of mathematics and logic, Numerical analysis
Wikipedia outlines, Numerical analysis
Lists of topics, Numerical analysis