Numerical Methods
Algorithms that approximate mathematical results with computation.
Numerical methods solve equations, systems, transforms, and calculations where exact symbolic answers are not practical.
Bisection Method
Finds a root by repeatedly halving an interval that contains it.
Gaussian Elimination
Solves linear systems by eliminating variables row by row.
LU Decomposition
Factors a matrix into lower and upper triangular matrices.
Fast Fourier Transform
Computes the discrete Fourier transform efficiently by reusing symmetry and subproblem structure.
Conjugate Gradient
Solves large symmetric positive-definite linear systems with iterative search directions.
Fixed Point Iteration
Solves equations by repeatedly applying a function until the value stops changing.
Gauss-Seidel Method
Solves linear systems by updating variables immediately as new values are available.
Jacobi Method
Solves linear systems by repeatedly updating each variable from the previous iteration.
Secant Method
Finds roots using a line through two recent estimates.
Simpson's Rule
Approximates an integral by fitting parabolas over intervals.
Cholesky Decomposition
Factors a symmetric positive definite matrix into a triangular matrix and its transpose.
Eigenvalue Decomposition
Represents a matrix through directions that are only scaled by the matrix.
Broyden's Method
Solves nonlinear systems by updating an approximate Jacobian instead of recomputing it.
Romberg Integration
Improves trapezoidal integration estimates with extrapolation.
Monte Carlo Integration
Approximates integrals by averaging random samples.
Adaptive Quadrature
Numerically integrates by subdividing intervals where the error estimate is too high.
Multigrid Method
Solves grid-based systems faster by correcting error across coarse and fine grids.
QR Decomposition
Factors a matrix into an orthogonal matrix and an upper triangular matrix.
Singular Value Decomposition
Factors a matrix into singular vectors and singular values that reveal its main directions.
Power Iteration
Approximates the dominant eigenvector by repeatedly multiplying by a matrix.
Trapezoidal Rule
Approximates an integral by summing trapezoid areas under sampled function values.
Polynomial Interpolation
Finds a polynomial that passes through a set of sample points.
Lagrange Interpolation
Builds an interpolating polynomial as a weighted sum of basis polynomials.
Newton Interpolation
Builds an interpolating polynomial incrementally with divided differences.
Finite Volume Method
Solves conservation laws by balancing fluxes through control-volume boundaries.
Euler-Maruyama Method
Approximates stochastic differential equations with an Euler step plus random noise.
Runge-Kutta-Fehlberg
Solves ODEs with paired Runge-Kutta estimates used for adaptive step sizing.
Adams-Bashforth Method
Solves ODEs with an explicit multistep formula using previous derivative values.
Backward Differentiation Formula
Solves stiff ODEs with implicit multistep formulas based on backward differences.
Successive Over-Relaxation
Accelerates Gauss-Seidel iteration by over-relaxing each variable update.
Preconditioned Conjugate Gradient
Solves symmetric positive definite systems faster by applying a preconditioner.
Householder Transformation
Householder Transformation approximates a numerical solution with iterative or algebraic steps.
Givens Rotation
Givens Rotation approximates a numerical solution with iterative or algebraic steps.
Lanczos Algorithm
Lanczos Algorithm approximates a numerical solution with iterative or algebraic steps.
Arnoldi Iteration
Arnoldi Iteration approximates a numerical solution with iterative or algebraic steps.
Thomas Algorithm
Thomas Algorithm approximates a numerical solution with iterative or algebraic steps.
Richardson Iteration
Richardson Iteration approximates a numerical solution with iterative or algebraic steps.
Richardson Extrapolation
Richardson Extrapolation approximates a numerical solution with iterative or algebraic steps.
Neville's Algorithm
Neville's Algorithm approximates a numerical solution with iterative or algebraic steps.
Brent's Method
Brent's Method approximates a numerical solution with iterative or algebraic steps.
Bulirsch-Stoer Method
Bulirsch-Stoer Method approximates a numerical solution with iterative or algebraic steps.
Strassen Algorithm
Multiplies matrices by replacing eight block multiplications with seven recursive products.
Coppersmith-Winograd Algorithm
Coppersmith-Winograd Algorithm addresses matrix multiplication by using algebraic tensor techniques to reduce asymptotic multiplication exponents.
Blocked Matrix Multiplication
Blocked Matrix Multiplication uses multiplying matrix tiles to improve cache locality for matrix multiplication.
Winograd Matrix Multiplication
Winograd Matrix Multiplication addresses matrix multiplication by rearranging products to reduce scalar multiplications.
Karatsuba Multiplication
Karatsuba Multiplication uses splitting numbers and replacing one recursive multiplication with additions for integer multiplication.
Toom-Cook Multiplication
Toom-Cook Multiplication addresses integer multiplication by evaluating number polynomials at points and interpolating the product.
FFT-Based Integer Multiplication
FFT-Based Integer Multiplication addresses integer multiplication by convolving digit blocks with a fast Fourier transform.
Schoolbook Multiplication
Multiplies numbers by forming digit-by-digit partial products and adding them by place value.
Burnikel-Ziegler Division
Burnikel-Ziegler Division addresses large integer division by splitting operands into blocks for recursive division.
Knuth Division Algorithm
Knuth Division Algorithm uses normalizing divisor digits and estimating quotient digits for multi-precision division.
Euclidean Algorithm
Computes the greatest common divisor of two integers by repeatedly taking remainders.
Extended Euclidean Algorithm
Computes a greatest common divisor together with coefficients satisfying Bezout's identity.
Binary GCD
Binary GCD uses using shifts and subtraction instead of division for greatest common divisor.
Chinese Remainder Theorem Algorithm
Combines compatible congruences into one solution modulo the product of the moduli.
Exponentiation by Squaring
Computes powers efficiently by repeatedly squaring the base and using the exponent's binary digits.
Sieve of Eratosthenes
Finds all primes up to a limit by repeatedly crossing out multiples of each discovered prime.
Sieve of Atkin
Sieve of Atkin addresses prime generation by using modular quadratic forms to mark candidate primes.
Bareiss Algorithm
Bareiss Algorithm uses performing fraction-free Gaussian elimination to keep intermediate values exact for determinant computation.
Laplace Expansion
Laplace Expansion uses expanding a determinant into cofactors along a row or column for determinant computation.
Ryser Formula
Ryser Formula addresses permanent computation by summing signed products over subsets of matrix columns.
Berkowitz Algorithm
Berkowitz Algorithm addresses characteristic polynomial by building determinant coefficients without division.
Neville's Algorithm
Neville's Algorithm addresses polynomial interpolation by recursively combining nearby interpolation values.
Clenshaw Algorithm
Clenshaw Algorithm addresses polynomial series evaluation by evaluating recurrence-defined polynomial expansions backward.
Brent's Method
Brent's Method uses combining bisection, secant, and inverse quadratic interpolation steps for root finding.
Ridders' Method
Ridders' Method addresses root finding by using exponential interpolation inside a bracketing interval.
Steffensen's Method
Steffensen's Method addresses root finding by accelerating fixed-point iteration with a finite-difference correction.
GMRES
GMRES uses minimizing residuals over a growing Krylov subspace for linear system solving.
MINRES
MINRES addresses symmetric linear system solving by minimizing residuals for symmetric systems without requiring positive definiteness.
BiCGSTAB
BiCGSTAB addresses nonsymmetric linear system solving by combining bi-conjugate gradients with residual smoothing.
Householder QR
Householder QR addresses qr decomposition by reflecting columns to zero out subdiagonal entries.
Kahan Summation
Kahan Summation addresses floating-point summation by tracking lost low-order bits as a compensation term.
Aitken Delta-Squared Process
Aitken Delta-Squared Process addresses convergence acceleration by using three successive estimates to extrapolate a faster limit.
Cuthill-McKee Algorithm
Orders sparse matrix graph vertices to reduce matrix bandwidth.
Reverse Cuthill-McKee Algorithm
Reverses Cuthill-McKee ordering to improve sparse matrix bandwidth profiles.