 List of numerical analysis topics

This is a list of numerical analysis topics, by Wikipedia page.
General
 Iterative method
 Rate of convergence — the speed at which a convergent sequence approaches its limit
 Series acceleration — methods to accelerate the speed of convergence of a series
 Aitken's deltasquared process — most useful for linearly converging sequences
 Minimum polynomial extrapolation — for vector sequences
 Richardson extrapolation
 Shanks transformation — similar to Aitken's deltasquared process, but applied to the partial sums
 Van Wijngaarden transformation — for accelerating the convergence of an alternating series
 Level set method
 Level set (data structures) — data structures for representing level sets
 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
 Collocation method — discretizes a continuous equation by requiring it only to hold at certain points
 Difference quotient
 Complexity:
 Computational complexity of mathematical operations
 Smoothed analysis — measuring the expected performance of algorithms under slight random perturbations of worstcase inputs
 Symbolicnumeric computation — combination of symbolic and numeric methods
 ABS methods
 Cultural aspects:
 International Workshops on Lattice QCD and Numerical Analysis
 Hundreddollar, Hundreddigit Challenge problems — list of ten problems proposed by Nick Trefethen in 2002
Error
 Approximation
 Approximation error
 Arithmetic precision
 Condition number
 Discretization error
 Floating point number
 Guard digit — extra precision introduced during a computation to reduce roundoff error
 Arbitraryprecision arithmetic
 Truncation — rounding a floatingpoint number by discarding all digits after a certain digit
 Interval arithmetic — represent every number by two floatingpoint numbers guaranteed to have the unknown number between them
 See also: Interval boundary element method, Interval finite element
 Loss of significance
 Numerical error
 Numerical stability
 Error propagation:
 Relative difference — the relative difference between x and y is x − y / max(x, y)
 Roundoff error
 Stochastic rounding
 Significant figures
 False precision — giving more significant figures than appropriate
 Truncation error — error committed by doing only a finite numbers of steps
 Wellposed problem
 Affine arithmetic
Elementary and special functions
 Summation:
 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önhageStrassen
 Exponentiation:
 Polynomials:
 Horner scheme
 Estrin's scheme — modification of the Horner scheme with more possibilities for parallellization
 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
 Alpha max plus beta min algorithm — approximates (x^{2} + y^{2})^{1/2}
 Fast inverse square root — calculates 1 / √x using details of the IEEE floatingpoint system
 Elementary functions (exponential, logarithm, trigonometric functions):
 Generating trigonometric tables
 CORDIC — shiftandadd algorithm using a table of arc tangents
 BKM algorithm — shiftandadd 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
 Gal's accurate tables — table of function values with unequal spacing to reduce roundoff error
 Spigot algorithm — algorithms that can compute individual digits of a real number
 Approximations of π:
 Liu Hui's pi algorithm — first algorithm that can compute π to arbitrary precision
 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
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
 Circulant matrix
 Triangular matrix
 Diagonally dominant matrix
 Stieltjes matrix — symmetric positive definite with nonpositive offdiagonal entries
 Hilbert matrix — example of a matrix which is extremely illconditioned (and thus difficult to handle)
 Wilkinson matrix — example of a symmetric tridiagonal matrix with pairs of nearly, but not exactly, equal eigenvalues
 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
 Freivald's 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
 Polar decomposition — unitary matrix times positivesemidefinite 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
 Jordan–Chevalley decomposition — sum of commuting nilpotent matrix and diagonalizable matrix
 Schur decomposition — similarity transform bringing the matrix to a triangular matrix
Solving systems of linear equations
 Gaussian elimination
 Row echelon form — matrix in which all entries below a nonzero entry are zero
 Gauss–Jordan elimination — variant in which the entries below the pivot are also zeroed
 Montante's method — 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 lowertriangular 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
 Frontal solver — for sparse matrices; used in finite element methods
 Levinson recursion — for Toeplitz matrices
 SPIKE algorithm — hybrid parallel solver for narrowbanded matrices
 Iterative methods:
 Jacobi method
 Gauss–Seidel method
 Successive overrelaxation (SOR) — a technique to accelerate the Gauss–Seidel method
 Modified Richardson iteration
 Conjugate gradient method (CG) — assumes that the matrix is positive definite
 Nonlinear conjugate gradient method — generalization for nonlinear optimization problems
 Biconjugate gradient method (BiCG)
 Generalized minimal residual method (GMRES) — based on the Arnoldi iteration
 Stone's method (SIP  Srongly 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
 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 2norm (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 positivedefinite matrices
 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
 Divideandconquer eigenvalue algorithm
 Folded spectrum method
 LOBPCG  Locally Optimal Block Preconditioned Conjugate Gradient Method
Other concepts and algorithms
 Orthogonalization algorithms:
 Krylov subspace
 Block matrix pseudoinverse
 Bidiagonalization
 Inplace matrix transposition — computing the transpose of a matrix without using much additional storage
 Pivot element — entry in a matrix on which the algorithm concentrates
 Matrixfree methods — methods that only access the matrix by evaluating matrixvector products
Interpolation
 Nearestneighbor 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
 Newton polynomial
 Extensions to multiple dimensions:
 Bilinear interpolation
 Trilinear interpolation
 Bicubic interpolation
 Tricubic interpolation
 Padua points — set of points in R^{2} with unique polynomial interpolant and minimal growth of Lebesgue constant
 Hermite interpolation
 Birkhoff 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
 Monotone cubic interpolation
 Hermite spline
 Cardinal spline
 Bézier spline
 Smoothing spline
 Generalizations to more dimensions:
 Bézier triangle — maps a triangle to R^{3}
 Bézier surface — maps a square to R^{3}
 Generalizations to more dimensions:
 Bspline
 Truncated power function
 De Boor's algorithm — generalizes De Casteljau's algorithm
 Nonuniform rational Bspline (NURBS)
 Kochanek–Bartels spline
 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
 Fast Fourier transform — a fast method for computing the discrete Fourier transform
 Bluestein's FFT algorithm
 Bruun's FFT algorithm
 Cooley–Tukey FFT algorithm
 Splitradix FFT algorithm — variant of Cooley–Tukey that uses a blend of radices 2 and 4
 Goertzel algorithm
 Primefactor FFT algorithm
 Rader's FFT algorithm
 Butterfly diagram
 Twiddle factor — the trigonometric constant coefficients that are multiplied by the data
 Methods for computing discrete convolutions with finite impulse response filters using the FFT:
 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
 Inverse distance weighting
 Cascade algorithm — iterative algorithm to compute wavelets
 Radial basis function (RBF) — a function of the form ƒ(x) = φ(x−x_{0})
 Polyharmonic spline — a commonly used radial basis function
 Thin plate spline — a specific polyharmonic spline: r^{2} log r
 Radial basis function network — neural network using radial basis functions as activation functions
 Hierarchical RBF
 Subdivision surface — constructed by recursively subdividing a piecewise linear interpolant
 Slerp
 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 semidefinite
 Pareto interpolation
 Multivariate interpolation — the function being interpolated depends on more than one variable
 Barnes interpolation — method for twodimensional functions using Gaussians common in meteorology
 Lanczos resampling — based on convolution with a sinc function
 Natural neighbor interpolation
 PDE surface
 Method based on polynomials are listed under Polynomial interpolation
Approximation theory
 Orders of approximation
 Lebesgue's lemma
 Curve fitting
 Modulus of continuity — measures smoothness of a function
 Minimax approximation algorithm — minimizes the maximum error over an interval (the L^{∞}norm)
 Approximation by polynomials:
 Linear approximation
 Bernstein polynomial — basis of polynomials useful for approximating a function
 Remez algorithm — for constructing the best polynomial approximation in the L^{∞}norm
 Bramble–Hilbert lemma — upper bound on L^{p} error of polynomial approximation in multiple dimensions
 Bernstein's constant — error when approximating x by a polynomial
 Surrogate model — application: replacing a function that is hard to evaluate by a simpler function
 Jackson's inequality — upper bound for best approximation by a trigonometric polynomial
 Different approximations:
 Moving least squares
 Padé approximant
 Padé table — table of Padé approximants
 Szász–Mirakyan operator — approximation by e^{−n} x^{k} on a semiinfinite 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
Miscellaneous
 Extrapolation
 Linear predictive analysis — linear extrapolation
 Unisolvent functions — functions for which the interpolation problem has a unique solution
 Regression analysis
 Curvefitting compaction
 Interpolation (computer programming) — interpolation in the context of computer graphics
Finding roots of nonlinear equations
 See #Numerical linear algebra for linear equations
Rootfinding algorithm — algorithms for solving the equation f(x) = 0
 General methods:
 Bisection method — simple and robust; linear convergence
 LehmerSchur algorithm — variant for complex functions
 Fixed point iteration
 Newton's method — based on linear approximation around the current iterate; quadratic convergence
 Newton fractal
 QuasiNewton method — uses an approximation of the Jacobian:
 Broyden's method — uses a rankone update for the Jacobian
 SR1 formula — a symmetric (but not necessarily positive definite) rankone update of the Jacobian
 DavidonFletcherPowell formula — update of the Jacobian in which the matrix remains positive definite
 BFGS method — ranktwo update of the Jacobian in which the matrix remains positive definite
 LBFGS method — truncated, matrixfree 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
 Müller's method — based on quadratic interpolation at last three iterates
 Inverse quadratic interpolation — similar to Müller'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
 Bisection method — simple and robust; linear convergence
 Methods for polynomials:
 Aberth method
 Bairstow's method
 Durand–Kerner method
 Graeffe's method
 JenkinsTraub algorithm — fast, reliable, and widely used
 Laguerre's method
 Splitting circle method
 Analysis:
 Numerical continuation — tracking a root as one parameters in the equation changes
Optimization
Optimization (mathematics) — algorithm for finding maxima or minima of a given function
Basic concepts
 Active set
 Candidate solution
 Constraint (mathematics)
 Corner solution
 Fitness function — (esp. in genetic algorithms) an approximation to the objective function that is easier to evaluate
 Fitness approximation
 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
 Interior point method
 Delayed column generation
 kapproximation of khitting set — algorithm for specific LP problems (to find a weighted hitting set)
 Simplex algorithm
 Linear complementarity problem
 Decompositions:
 Benders' decomposition
 Dantzig–Wolfe decomposition
 Fourier–Motzkin elimination
 Hilbert basis (linear programming) — set of integer vectors in a convex cone which generate all integer vectors in the cone
Nonlinear programming
Nonlinear programming — the most general optimization problem in the usual framework
 Special cases of nonlinear programming:
 Quadratic programming
 Linear least squares
 Frank–Wolfe algorithm
 Sequential Minimal Optimization — breaks up large QP problems into a series of smallest possible QP problems
 Bilinear program
 Convex optimization
 Linear matrix inequality
 Conic optimization
 Semidefinite programming
 Secondorder cone programming
 Quadratic programming (see above)
 Bregman method — rowaction method for strictly convex optimization problems
 Subgradient method — extension of steepest descent for problems with a nondifferentiable objective function
 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
 Linearfractional programming — objective is ratio of linear functions, constraints are linear
 Least squares — the objective function is a sum of squares
 Nonlinear least squares
 Gauss–Newton algorithm
 Generalized Gauss–Newton method — for constrained nonlinear leastsquares problems
 Levenberg–Marquardt algorithm
 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
 Quadratic programming
 General algorithms:
 Concepts:
 Descent direction
 Guess value — the initial guess for a solution with which an algorithm starts
 Line search
 Gradient descent
 Successive linear programming (SLP) — replace problem by a linear 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
 NelderMead method
 Rosenbrock methods — derivativefree method, similar to Nelder–Mead but with guaranteed convergence
 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
 Least absolute deviations
 Nearest neighbor search
 Concepts:
Uncertainty and randomness
 Approaches to deal with uncertainty:
 Random optimization algorithms:
 Simulated annealing
 Adaptive simulated annealing — variant in which the algorithm parameters are adjusted during the computation.
 Great Deluge algorithm
 Evolutionary algorithm, Evolution strategy
 Memetic algorithm
 Particle swarm optimization
 Cooperative optimization
 Repulsive particle swarm optimization
 Stochastic tunneling
 Harmony search — mimicks the improvisation process of musicians
 see also the section Monte Carlo method
 Simulated annealing
Theoretical aspects
 Convex analysis
 Duality:
 Dual problem, Shadow price
 Dual cone and polar cone
 Fenchel's duality theorem — relates minimization problems with maximization problems of convex conjugates
 Farkas' lemma
 Karush–Kuhn–Tucker conditions
 Lagrange multipliers
 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
 Mixed complementarity problem
 Danskin's theorem — used in the analysis of minimax problems
 No free lunch in search and optimization
 Relaxation technique (mathematics)
 Lagrangian relaxation
 Linear programming relaxation — ignoring the integrality constraints in a linear programming problem
 Selfconcordant 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
 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
 Inventory control problem
 Jobshop problem
 Linear programming decoding
 Multidisciplinary design optimization
 Paper bag problem
 Process optimization
 Stigler diet
 Stress majorization
 Trajectory optimization
 Wing shape optimization
Miscellaneous
 Combinatorial optimization
 Dynamic programming
 Bellman equation
 Hamilton–Jacobi–Bellman equation — continuoustime 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
 Global optimization:
 Bilevel program — problem in which one problem is embedded in another
 Multilevel programming — problem in which a series of problems is embedded in each other
 Infinitedimensional optimization
 Optimal control
 Pontryagin's minimum principle — infinitedimensional version of Lagrange multipliers
 DNSS point — initial state for certain optimal control problems with multiple optimal solutions
 Shape optimization, Topology optimization — optimization over a set of regions
 Topological derivative — derivative with respect to changing in the shape
 Generalized semiinfinite programming — finite number of variables, infinite number of constraints
 Optimal control
 Optimal substructure
 Algorithmic concepts:
 Famous test functions for optimization:
 Rosenbrock function — twodimensional function with a bananashaped valley
 Himmelblau's function — twodimensional with four local minima, defined by f(x,y) = (x^{2} + y − 11)^{2} + (x + y^{2} − 7)^{2}
 Shekel function — multimodal and multidimensional
 Mathematical Programming Society
Numerical quadrature (integration)
Numerical integration — the numerical evaluation of an integral
 Rectangle method — firstorder method, based on (piecewise) constant approximation
 Trapezoidal rule — secondorder method, based on (piecewise) linear approximation
 Simpson's rule — fourthorder method, based on (piecewise) quadratic approximation
 Newton–Cotes formulas
 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 − x^{2})^{±1/2} on [−1, 1]
 Gauss–Hermite quadrature — extension of Gaussian quadrature for integrals with weight exp(−x^{2}) 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^{2}) on [0, ∞]
 Gauss–Kronrod quadrature formula — nested rule based on Gaussian quadrature
 GaussKronrod rules
 Tanhsinh 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
 Tintegration — a nonstandard method
 Lebedev quadrature — uses a grid on a sphere with octahedral symmetry
 Sparse grid
 Numerical differentiation
 Euler–Maclaurin formula
Numerical ordinary differential equations
Numerical 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
 Runge–Kutta methods — one of the two main classes of methods for initialvalue problems
 Midpoint method — a secondorder method with two stages
 Heun's method — either a secondorder method with two stages, or a thirdorder method with three stages
 Bogacki–Shampine method — a thirdorder method with four stages (FSAL) and an embedded fourthorder method
 Cash–Karp method — a fifthorder method with six stages and an embedded fourthorder method
 Dormand–Prince method — a fifthorder method with seven stages (FSAL) and an embedded fourthorder method
 Runge–Kutta–Fehlberg method — a fifthorder method with six stages and an embedded fourthorder method
 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 initialvalue problems
 Backward differentiation formula — implicit methods of order 2 to 6; especially suitable for stiff equations
 Numerov's method — fourthorder method for equations of the form y'' = f(t,y)
 Bulirsch–Stoer algorithm — combines the midpoint method with Richardson extrapolation to attain arbitrary order
 Methods designed for the solution of ODEs from classical physics:
 Newmarkbeta method — based on the extended meanvalue theorem
 Verlet integration — a popular secondorder method
 Leapfrog integration — another name for Verlet integration
 Beeman's algorithm — a twostep 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
 Semiimplicit Euler method — variant of Euler method which is symplectic when applied to separable Hamiltonians
 Symplectic integrator — a method for the solution of Hamilton's equations that preserves the symplectic structure
 Adaptive stepsize — automatically changing the step size when that seems advantageous
 Stiff equation — roughly, an ODE for which the unstable methods needs a very short step size, but stable methods do not
 Methods for solving twopoint 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 differentialalgebraic equations (DAEs), i.e., ODEs with constraints:
 Constraint algorithm — for solving Newton's equations with constraints
 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
 Bidirectional delay line
 Partial element equivalent circuit
 History of numerical solution of differential equations using computers
 Truncation error (numerical integration) — local and global truncation errors, and their relationships
Numerical 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
 Difference operator — the numerator of a finite difference
 Discrete Laplace operator — finitedifference approximation of the Laplace operator
 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
 Noncompact stencil — any stencil that is not compact
 Fivepoint stencil — twodimensional stencil consisting of a point and its four immediate neighbours on a rectangular grid
 Stencil codes — computer codes that update array elements according to some fixed pattern, called stencils
 Finite difference methods for heat equation and related PDEs:
 FTCS scheme (forwardtime centralspace) — firstorder explicit
 Crank–Nicolson method — secondorder implicit
 Finite difference methods for hyperbolic PDEs like the wave equation:
 Lax–Friedrichs method — firstorder explicit
 Lax–Wendroff method — secondorder explicit
 MacCormack method — secondorder explicit
 Upwind scheme
 Alternating direction implicit method (ADI) — update using the flow in xdirection and then using flow in ydirection
 Specific applications:
 Finite difference methods for option pricing
 Finitedifference timedomain method — a finitedifference method for electrodynamics
Finite element methods
Finite element method — based on a discretization of the space of solutions
 Finite element method in structural mechanics — a physical approach to finite element methods
 Engineering treatment of the finite element method — an explanation of finite elements geared towards engineers
 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
 RayleighRitz method — a finite element method based on variational principles
 Spectral element method — highorder finite element methods
 hpFEM — variant in which both the size and the order of the elements are automatically adapted
 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
 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 finiteelement 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
 Multiplepoint constraint (MPC)
 List of finite element software packages
 NAFEMS — notforprofit organisation that sets and maintains standards in computeraided engineering analysis
 Multiphase topology optimisation — technique based on finite elements for determining optimal composition of a mixture
 Interval finite element
Other methods
 Spectral method — based on the Fourier transformation
 Method of lines — reduces the PDE to a large system of ordinary differential equations
 Boundary element method — based on transforming the PDE to an integral equation on the boundary of the domain
 Interval boundary element method — a version using interval arithmetics
 Analytic element method — similar to the boundary element method, but the integral equation is evaluated analytically
 Finite volume method — based on dividing the domain in many small domains; popular in computational fluid dynamics
 Godunov's scheme — firstorder conservative scheme for fluid flow, based on piecewise constant approximation
 MUSCL scheme — secondorder 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)
 Discrete element method — a method in which the elements can move freely relative to each other
 Meshfree methods — does not use a mesh, but uses a particle view of the field
 Methods designed for problems from electromagnetics:
 Finitedifference timedomain method — a finitedifference method
 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
 Particleincell — used especially in fluid dynamics
 Highresolution scheme
 Shock capturing methods
 Splitstep method
 Fast marching method
 Lattice Boltzmann methods — for the solution of the NavierStokes equations
 Roe solver — for the solution of the Euler equation
 Relaxation 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
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 (BDD) — preconditioner for symmetric positive definite matrices
 Balancing domain decomposition by constraints (BDDC) — further development of BDD
 Finite element tearing and interconnect (FETI)
 FETIDP — 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 particleparticle interactions
Miscellaneous
 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
 Numerical resistivity — the same, with resistivity instead of diffusion
 Weak formulation — a functionalanalytic 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
 Grids and meshes:
 Mesh generation
 Geodesic grid — isotropic grid on a sphere
 Spatial twist continuum — dual representation of a mesh consisting of hexahedra
 Perfectly matched layer — artificial absorbing layer for wave equations, used to implement absorbing boundary conditions
Monte Carlo method
 Variants of the Monte Carlo method:
 Direct simulation Monte Carlo
 QuasiMonte Carlo method
 Markov chain Monte Carlo
 Metropolis–Hastings algorithm
 Multipletry 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
 Gibbs sampling
 Coupling from the past
 Metropolis–Hastings algorithm
 Dynamic Monte Carlo method
 Particle filter
 Reverse Monte Carlo
 Demon algorithm
 Sampling methods:
 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 precomputed 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
 Lowdiscrepancy sequence
 Constructions of lowdiscrepancy sequences
 Illustration of a lowdiscrepancy sequence
 Event generator
 Parallel tempering
 Umbrella sampling — improves sampling in physical systems with significant energy barriers
 Variance reduction techniques:
 Ensemble Kalman filter — recursive filter suitable for problems with a large number of variables
 Applications:
 Bond fluctuation model — for simulating the conformation and dynamics of polymer systems
 Metropolis light transport
 Monte Carlo method for photon transport
 Monte Carlo methods in finance
 Monte Carlo molecular modeling
 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 equalspin clusters
 Wolff algorithm — improvement of the Swendsen–Wang algorithm
 Auxiliary field Monte Carlo — computes averages of operators in manybody quantum mechanical problems
 Crossentropy method — for multiextremal optimization and importance sampling
 Also see the list of statistics topics
Applications
 Computational physics
 Computational electromagnetics
 Computational fluid dynamics (CFD)
 Large eddy simulation
 Smoothedparticle hydrodynamics
 Acoustic analogy — used in numerical aeroacoustics to reduce sound sources to simple emitter types
 Computational magnetohydrodynamics (CMHD) — studies electrically conducting fluids
 Climate model
 Numerical weather prediction
 Celestial mechanics
 Multiphysics Methods Group — program at Idaho National Laboratory studying simulations of nuclear reactors
 Computational chemistry
 Cell lists
 Coupled cluster
 Density functional theory
 Selfconsistent field method
 Computational statistics
Software
For software, see the list of numerical analysis software.
Categories: Numerical analysis
 Mathematicsrelated lists
 Outlines
Wikimedia Foundation. 2010.