Saturday, 18 June 2011

Mathematics

Algebra

  • Buchberger's algorithm. Finds a Gräbner basis.
  • Extended Euclidean algorithm. Solves the equation ax+by= c.
  • Fourier transform multiplication. For very big numbers, computing the fast Fourier transforms for two numbers, and multiplying the two results entry by entry.
  • Gram-Schmidt process. Orthogonalizes a set of vectors.
  • Gauss-Jordan elimination. Solves systems of linear equations.
  • Karatsuba multiplication. Recursive algorithm efficient for big numbers. Derived from the Toom-Cook method.
  • Knuth-Bendix completion. For rewriting rule systems.
  • Multivariate division. For polynomials in several indeterminates.
  • Risch algorithm. Translates indefinite integral to algebraic problem.
  • Toom-Cook (Toom3). Splits each number to be multiplied into multiple parts.

Eigenvalue algorithm

Algorithms to find the Eigenvalue and/or Eigenvector of a matrix.
  • QR algorithm. A popular method based on the QR decomposition.
  • Inverse iteration. Iterative eigenvalue algorithm.
  • Rayleigh quotient iteration. Extends the principle of the inverse iteration by using the Rayleigh quotient to obtain increasingly accurate eigenvalue estimates.
  • Arnoldi iteration. Compute the eigenvalues of the orthogonal projection of A onto the Krylov subspace.
  • Lanczos iteration. Method to find a zero vector in the process of the quadratic sieve.
  • Jacobi method. Numerical procedure for the calculation of all eigenvalues and eigenvectors of a real symmetric. matrix
  • Bisection.
  • Divide-and-conquer. Apply to real symmetric matrices.
Eigenvector algorithms
  • Richardson eigenvector algorithm.
  • Max-Plus. Eigenvector algorithm for nonlinear H 1 control.
  • Abrams and Lloyd eigenvector algorithm.

Arithmetic

  • Binary GCD algorithm. Efficient way of calculating greatest common divisor.
  • Booth's multiplication. Multiply two signed numbers in two's complement notation.
  • Euclidean algorithm. Computes the greatest common divisor.
  • Binary multiplication (Peasant or Egyptian multiplication). Decomposes the larger multiplicand into a sum of powers of two and creates a table of doublings of the second multiplicand.

Discrete logarithm in group theory

  • Baby-step giant-step. This is a series of well defined steps to compute the discrete logarithm.
  • Pollard's rho algorithm for logarithms. Analogous to Pollard's rho algorithm for integer factorization but solves the discrete logarithm problem.
  • Pohlig-Hellman algorithm. Solves the problem for a multiplicative group whose order is a smooth integer. Based on the Chinese remainder theorem and runs in polynomial time.
  • Index calculus algorithm. Best known algorithm for certain groups, as the multiplicative group modulo m.

Integer factorization

Breaking an integer into its prime factors . Also named prime factorization.
  • Fermat's factorization method. A representation of an odd integer as the difference of two squares.
  • Trial division. The simplest of the integer factorization algorithms. Try to divide the integer n by every prime number.
  • Lenstra elliptic curve factorization or elliptic curve factorization method (ECM). Fast, sub-exponential running time, employs elliptic curves.
  • Pollard's rho . Variation of Pollard's p-1 that is effective at splitting composite numbers with small factors.
  • Pollard's p-1. A special-purpose algorithm, that is only suitable for integers with specific types of factors.
  • Congruence of squares. Finding a congruence of squares modulo n is a mean to to factor the integer n.
  • Quadratic sieve. Uses the idea of Dixon's method. It is a general-purpose algorithm that is simpler than the number field sieve and the fastest for integers under 100 decimal digits.
  • Dixon's factorization method. General-purpose integer factorization algorithm.
  • Special number field sieve. Special-purpose algorithm ideal for Fermat numbers.
  • General number field sieve (GNS). Derived from special number field sieve. Efficient algorithm known for factoring big integers. Uses steps to factor the integer.

Prime test

Determining whether a given number is prime.
  • AKS primality test (Agrawal-Kayal-Saxena). The first published algorithm to be simultaneously polynomial, deterministic, and unconditional. Generalization of Fermat's theorem, extended to polynomials.
  • Fermat primality test. Rely on an equality or set of equalities that hold true for prime values, and then see whether or not they hold for the number to test.
  • Miller-Rabin primality test. Similar to the Fermat primality test. Unconditional probabilistic algorithm.
  • Sieve of Eratosthenes. Ancient algorithm for finding all prime numbers up to a specified integer.
  • Sieve of Atkin. Optimized version of the sieve of Eratosthenes.
  • Solovay-Strassen primality test. Same principle as the Fermat test.

Numerical

  • Fibonacci. Calculating the sequence of Fibonacci.
  • Biconjugate gradient method. Solves systems of linear equations.
  • Dancing Links. Finds all solutions to the exact cover problem.
  • De Boor algorithm. Computes splines.
  • De Casteljau's algorithm. Computes Bezier curves.
  • False position method. Approximates roots of a function.
  • Gauss-Legendre. Computes the digits of pi.
  • Kahan summation. A more accurate method of summing floating-point numbers.
  • MISER. Monte Carlo simulation, numerical integration.
  • Newton's method. Finds zeros of functions with calculus.
  • Rounding functions. The classic ways to round numbers.
  • Secant method. Approximates roots of a function.
  • Shifting nth-root. Digit by digit root extraction.
  • Square root. Approximates the square root of a number.
  • Borwein's algorithm. Calculates the value of 1/e.
  • Metropolis-Hastings. Generate a sequence of samples from the probability distribution of one or more variables.

0 comments:

Post a comment