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

**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