|
Further information: Computational mathematics See also: Combinatorial algorithms and Computational science Abstract algebra Further information: Abstract Algebra Chien search: a recursive algorithm for determining roots of polynomials defined over a finite field Schreier–Sims algorithm: computing a base and strong generating set (BSGS) of a permutation group Todd–Coxeter algorithm: Procedure for generating cosets. Computer algebra Further information: Computer algebra Buchberger's algorithm: finds a Gröbner basis Cantor–Zassenhaus algorithm: factor polynomials over finite fields Faugère F4 algorithm: finds a Gröbner basis (also mentions the F5 algorithm) Gosper's algorithm: find sums of hypergeometric terms that are themselves hypergeometric terms Knuth–Bendix completion algorithm: for rewriting rule systems Multivariate division algorithm: for polynomials in several indeterminates Pollard's kangaroo algorithm (also known as Pollard's lambda algorithm ): an algorithm for solving the discrete logarithm problem Polynomial long division: an algorithm for dividing a polynomial by another polynomial of the same or lower degree Risch algorithm: an algorithm for the calculus operation of indefinite integration (i.e. finding antiderivatives) Geometry Main page: Geometric algorithms Further information: Computational geometry Closest pair problem: find the pair of points (from a set of points) with the smallest distance between them Collision detection algorithms: check for the collision or intersection of two given solids Cone algorithm: identify surface points Convex hull algorithms: determining the convex hull of a set of points Graham scan QuickHull Gift wrapping algorithm or Jarvis march Chan's algorithm Kirkpatrick–Seidel algorithm Euclidean Distance Transform - Computes the distance between every point in a grid and a discrete collection of points. Geometric hashing: a method for efficiently finding two-dimensional objects represented by discrete points that have undergone an affine transformation Gilbert–Johnson–Keerthi distance algorithm: determining the smallest distance between two convex shapes. Jump-and-Walk algorithm: an algorithm for point location in triangulations Laplacian smoothing: an algorithm to smooth a polygonal mesh Line segment intersection: finding whether lines intersect, usually with a sweep line algorithm Bentley–Ottmann algorithm Shamos–Hoey algorithm Minimum bounding box algorithms: find the oriented minimum bounding box enclosing a set of points Nearest neighbor search: find the nearest point or points to a query point Point in polygon algorithms: tests whether a given point lies within a given polygon Point set registration algorithms: finds the transformation between two point sets to optimally align them. Rotating calipers: determine all antipodal pairs of points and vertices on a convex polygon or convex hull. Shoelace algorithm: determine the area of a polygon whose vertices are described by ordered pairs in the plane Triangulation Delaunay triangulation Ruppert's algorithm (also known as Delaunay refinement): create quality Delaunay triangulations Chew's second algorithm: create quality constrained Delaunay triangulations Marching triangles: reconstruct two-dimensional surface geometry from an unstructured point cloud Polygon triangulation algorithms: decompose a polygon into a set of triangles Voronoi diagrams, geometric dual of Delaunay triangulation Bowyer–Watson algorithm: create voronoi diagram in any number of dimensions Fortune's Algorithm: create voronoi diagram Quasitriangulation Number theoretic algorithms Further information: Number theory Binary GCD algorithm: Efficient way of calculating GCD. Booth's multiplication algorithm Chakravala method: a cyclic algorithm to solve indeterminate quadratic equations, including Pell's equation Discrete logarithm: Baby-step giant-step Index calculus algorithm Pollard's rho algorithm for logarithms Pohlig–Hellman algorithm Euclidean algorithm: computes the greatest common divisor Extended Euclidean algorithm: Also solves the equation ax + by = c. Integer factorization: breaking an integer into its prime factors Congruence of squares Dixon's algorithm Fermat's factorization method General number field sieve Lenstra elliptic curve factorization Pollard's p − 1 algorithm Pollard's rho algorithm prime factorization algorithm Quadratic sieve Shor's algorithm Special number field sieve Trial division Multiplication algorithms: fast multiplication of two numbers Karatsuba algorithm Schönhage–Strassen algorithm Toom–Cook multiplication Odlyzko–Schönhage algorithm: calculates nontrivial zeroes of the Riemann zeta function Primality tests: determining whether a given number is prime AKS primality test Baillie-PSW primality test Fermat primality test Lucas primality test Miller–Rabin primality test Sieve of Atkin Sieve of Eratosthenes Sieve of Sundaram Numerical algorithms Further information: Numerical analysis and List of numerical analysis topics Differential equation solving Further information: Differential equation Euler method Backward Euler method Trapezoidal rule (differential_equations) Linear multistep methods Runge–Kutta methods Euler integration Multigrid methods (MG methods), a group of algorithms for solving differential equations using a hierarchy of discretizations Partial differential equation: Finite difference method Crank-Nicolson method for diffusion equations Lax-Wendroff for wave equations Verlet integration (French pronunciation: [vɛʁˈlɛ]): integrate Newton's equations of motion Elementary and special functions Further information: Special functions Computation of π: Borwein's algorithm: an algorithm to calculate the value of 1/π Gauss–Legendre algorithm: computes the digits of pi Bailey–Borwein–Plouffe formula: (BBP formula) a spigot algorithm for the computation of the nth binary digit of π Hyperbolic and Trigonometric Functions: BKM algorithm: compute elementary functions using a table of logarithms CORDIC: compute hyperbolic and trigonometric functions using a table of arctangents Exponentiation: Addition-chain exponentiation exponentiation by positive integer powers that requires a minimal number of multiplications Exponentiating by squaring: an algorithm used for the fast computation of large integer powers of a number Montgomery reduction: an algorithm that allows modular arithmetic to be performed efficiently when the modulus is large Multiplication algorithms: fast multiplication of two numbers Booth's multiplication algorithm: a multiplication algorithm that multiplies two signed binary numbers in two's complement notation Fürer's algorithm: an integer multiplication algorithm for very large numbers possessing a very low asymptotic complexity Karatsuba algorithm: an efficient procedure for multiplying large numbers Schönhage–Strassen algorithm: an asymptotically fast multiplication algorithm for large integers Toom–Cook multiplication: (Toom3) a multiplication algorithm for large integers Rounding functions: the classic ways to round numbers Spigot algorithm: A way to compute the value of a mathematical constant without knowing preceding digits Square and Nth root of a number: Alpha max plus beta min algorithm: an approximation of the square-root of the sum of two squares Methods of computing square roots nth root algorithm Shifting nth-root algorithm: digit by digit root extraction Summation: Binary splitting: a divide and conquer technique which speeds up the numerical evaluation of many types of series with rational terms Kahan summation algorithm: a more accurate method of summing floating-point numbers Geometric Filtered back-projection: efficiently compute the inverse 2-dimensional Radon transform. Level set method (LSM): a numerical technique for tracking interfaces and shapes Interpolation and extrapolation Further information: Interpolation and Extrapolation Birkhoff interpolation: an extension of polynomial interpolation Cubic interpolation Hermite interpolation Linear interpolation: a method of curve fitting using linear polynomials Monotone cubic interpolation: a variant of cubic interpolation that preserves monotonicity of the data set being interpolated. Multivariate interpolation Bicubic interpolation, a generalization of cubic interpolation to two dimensions Bilinear interpolation: an extension of linear interpolation for interpolating functions of two variables on a regular grid Lanczos resampling ("Lanzosh"): a multivariate interpolation method used to compute new values for any digitally sampled data Nearest-neighbor interpolation Tricubic interpolation, a generalization of cubic interpolation to three dimensions Pareto interpolation: a method of estimating the median and other properties of a population that follows a Pareto distribution. Polynomial interpolation Neville's algorithm Spline interpolation: Reduces error with Runge's phenomenon. De Boor algorithm: B-splines De Casteljau's algorithm: Bézier splines Trigonometric interpolation Linear algebra Further information: Numerical linear algebra Eigenvalue algorithms Arnoldi iteration Inverse iteration Jacobi method Lanczos iteration Power iteration QR algorithm Rayleigh quotient iteration Gram–Schmidt process: orthogonalizes a set of vectors Matrix multiplication Cannon's algorithm: a distributed algorithm for matrix multiplication especially suitable for computers laid out in an N × N mesh Coppersmith–Winograd algorithm: square matrix multiplication Freivalds' algorithm: a randomized algorithm used to verify matrix multiplication Strassen algorithm: faster matrix multiplication Solving systems of linear equations Biconjugate gradient method: solves systems of linear equations Conjugate gradient: an algorithm for the numerical solution of particular systems of linear equations Gaussian elimination Gauss–Jordan elimination: solves systems of linear equations Gauss–Seidel method: solves systems of linear equations iteratively Levinson recursion: solves equation involving a Toeplitz matrix Stone's method: also known as the strongly implicit procedure or SIP, is an algorithm for solving a sparse linear system of equations Successive over-relaxation (SOR): method used to speed up convergence of the Gauss–Seidel method Tridiagonal matrix algorithm (Thomas algorithm): solves systems of tridiagonal equations Sparse matrix algorithms Cuthill–McKee algorithm: reduce the bandwidth of sparse symmetric matrices Minimum degree algorithm: permute the rows and columns of a symmetric sparse matrix before applying the Cholesky decomposition Symbolic Cholesky decomposition: Efficient way of storing sparse matrix Monte Carlo Further information: Monte Carlo method Gibbs sampling: generate a sequence of samples from the joint probability distribution of two or more random variables Metropolis–Hastings algorithm: used to generate a sequence of samples from the probability distribution of one or more variables Wang and Landau algorithm: an extension of Metropolis–Hastings algorithm sampling Numerical integration Further information: Numerical integration MISER algorithm: Monte Carlo simulation, numerical integration Root finding Main article: Root-finding algorithm Bisection method False position method: approximates roots of a function Newton's method: finds zeros of functions with calculus Halley's method: uses first and second derivatives Secant method: 2-point, 1-sided False position method and Illinois method: 2-point, bracketing Ridder's method: 3-point, exponential scaling Muller's method: 3-point, quadratic intepolation Optimization algorithms Main article: Mathematical optimization Alpha-beta pruning: search to reduce number of nodes in minimax algorithm Branch and bound Bruss algorithm: see odds algorithm Chain matrix multiplication Combinatorial optimization: optimization problems where the set of feasible solutions is discrete Greedy randomized adaptive search procedure (GRASP): successive constructions of a greedy randomized solution and subsequent iterative improvements of it through a local search Hungarian method: a combinatorial optimization algorithm which solves the assignment problem in polynomial time Constraint satisfaction General algorithms for the constraint satisfaction AC-3 algorithm Difference map algorithm Min conflicts algorithm Chaff algorithm: an algorithm for solving instances of the boolean satisfiability problem Davis–Putnam algorithm: check the validity of a first-order logic formula Davis–Putnam–Logemann–Loveland algorithm (DPLL): an algorithm for deciding the satisfiability of propositional logic formula in conjunctive normal form, i.e. for solving the CNF-SAT problem Exact cover problem Algorithm X: a nondeterministic algorithm Dancing Links: an efficient implementation of Algorithm X Cross-entropy method: a general Monte Carlo approach to combinatorial and continuous multi-extremal optimization and importance sampling Differential evolution Dynamic Programming: problems exhibiting the properties of overlapping subproblems and optimal substructure Ellipsoid method: is an algorithm for solving convex optimization problems Evolutionary computation: optimization inspired by biological mechanisms of evolution Evolution strategy Gene expression programming Genetic algorithms Fitness proportionate selection - also known as roulette-wheel selection Stochastic universal sampling Truncation selection Tournament selection Memetic algorithm Swarm intelligence Ant colony optimization Bees algorithm: a search algorithm which mimics the food foraging behavior of swarms of honey bees Particle swarm Gradient descent Harmony search (HS): a metaheuristic algorithm mimicking the improvisation process of musicians Interior point method Linear programming Benson's algorithm: an algorithm for solving linear vector optimization problems Dantzig–Wolfe decomposition: an algorithm for solving linear programming problems with special structure Delayed column generation Integer linear programming: solve linear programming problems where some or all the unknowns are restricted to integer values Branch and cut Cutting-plane method Karmarkar's algorithm: The first reasonably efficient algorithm that solves the linear programming problem in polynomial time. Simplex algorithm: An algorithm for solving linear programming problems Line search Local search: a metaheuristic for solving computationally hard optimization problems Random-restart hill climbing Tabu search Minimax used in game programming Nearest neighbor search (NNS): find closest points in a metric space Best Bin First: find an approximate solution to the Nearest neighbor search problem in very high dimensional spaces Newton's method in optimization Nonlinear optimization BFGS method: A nonlinear optimization algorithm Gauss–Newton algorithm: An algorithm for solving nonlinear least squares problems. Levenberg–Marquardt algorithm: An algorithm for solving nonlinear least squares problems. Nelder–Mead method (downhill simplex method): A nonlinear optimization algorithm Odds algorithm (Bruss algorithm) : Finds the optimal strategy to predict a last specific event in a random sequence event Simulated annealing Stochastic tunneling Subset sum algorithm |
About us|Jobs|Help|Disclaimer|Advertising services|Contact us|Sign in|Website map|Search|
GMT+8, 2015-9-11 22:04 , Processed in 0.127545 second(s), 16 queries .
