## Saturday, 18 June 2011

### 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.