Algorithm classification

1 Linear algebra problems

1.1 Matrix and vector operations

1.1.1 Vector operations

1.  Pairwise summation
   1.  Pairwise summation of numbers
   2.  Parallel prefix scan algorithm using pairwise summation
2.  Uniform norm of a vector: Real version, serial-parallel variant
3.  Dot product
4.  The serial-parallel summation method

1.1.2 Matrix-vector operations

1.1.2.1 Multiplying a nonsingular matrix by a vector

1.  Dense matrix-vector multiplication

1.1.2.2 Multiplying a matrix of special form by a vector

1. Fourier transform
   1. Fast Fourier transform for composite dimension
      1.  Fast Fourier transform for powers-of-two
         1.  Cooley–Tukey Fast Fourier Transform, radix-2 case
         2. Fast Fourier transform for even powers-of-two
      2. Fast Fourier transform for composite dimension with small prime divisors (2,3,5,7)
   2. Fast Fourier transform for prime dimension

1.1.3 Matrix operations

1.  Dense matrix multiplication
   1.  Dense matrix multiplication (serial version for real matrices)
   2. Strassen's algorithm

1.2 Matrix decompositions

 Matrix decomposition problem

1.  Triangular decompositions
   1.  Gaussian elimination (finding the LU decomposition)
      1.  LU decomposition using Gaussian elimination without pivoting
         1.  LU decomposition via Gaussian elimination
         2.  Gaussian elimination, compact scheme for tridiagonal matrices and its modifications
            1. Compact scheme for Gaussian elimination: Dense matrix
            2.  Compact scheme for Gaussian elimination and its modifications: Tridiagonal matrix
               1.  Gaussian elimination, compact scheme for tridiagonal matrices, serial version
               2.  Stone doubling algorithm for the LU decomposition of a tridiagonal matrix
               3.  Serial-parallel algorithm for the LU decomposition of a tridiagonal matrix
      2.  LU decomposition using Gaussian elimination with pivoting
         1.  Gaussian elimination with column pivoting
         2.  Gaussian elimination with row pivoting
         3.  Gaussian elimination with diagonal pivoting
         4.  Gaussian elimination with complete pivoting
   2.  Cholesky method
      1.  Cholesky decomposition
2. Available triangular decompositions for matrices of special form
3.  Unitary-triangular factorizations
   1.  QR decomposition of dense nonsingular matrices
      1.  Givens (rotations) method for the QR decomposition of a matrix
         1.  Givens method
      2.  Householder (reflections) method for the QR decomposition of a matrix
         1.  Householder (reflections) method for the QR decomposition of a square matrix, real point-wise version
      3.  Orthogonalization method
         1.  Classical orthogonalization method
         2.  Orthogonalization method with reorthogonalization
      4.  Triangular decomposition of a Gram matrix
   2.  QR decomposition methods for dense Hessenberg matrices
      1.  Givens (rotations) method for the QR decomposition of a (real) Hessenberg matrix
      2.  Householder (reflections) method for the QR decomposition of a (real) Hessenberg matrix
4.  Reducing matrices to compact forms
   1.  Unitary reductions to Hessenberg form
      1.  Householder (reflections) method for reducing of a matrix to Hessenberg form
         1.  Classical point-wise Householder (reflections) method for reducing a matrix to Hessenberg form
      2. Givens (rotations) method for reducing a matrix to Hessenberg form
         1. Classical point-wise Givens (rotations) method for reducing a matrix to Hessenberg form
   2.  Unitary reductions to tridiagonal form
      1. Householder (reflections) method for reducing to tridiagonal form
         1.  Householder (reflections) method for reducing a symmetric matrix to tridiagonal form
         2.  Householder (reflections) method for reducing a complex Hermitian matrix to symmetric tridiagonal form
      2. Givens (rotations) reduction to tridiagonal form
   3.  Eigenvalue decomposition (finding eigenvalues and eigenvectors)
5. Unitary non-similarity reductions to compact forms
   1. Unitary reduction to bidiagonal form
      1.  Householder (reflections) reduction of a matrix to bidiagonal form
      2. Givens (rotations) reduction of a matrix to bidiagonal form
   2. Singular value decomposition
      1.  Singular value decomposition (finding singular values and singular vectors)
         1. Methods for calculating singular values of bidiagonal matrices
            1. The dqds algorithm for calculating singular values of bidiagonal matrices
               1.  One step of the dqds algorithm

1.3 Solving systems of linear algebraic equations

1. Direct methods
   1.  Linpack benchmark
   2. Matrices of a special form
      1. Triangular matrices
         1.  Forward substitution
         2.  Backward substitution
         3. Bidiagonal matrices
            1. Forward and backward substitution for bidiagonal matrices
            2.  Stone doubling algorithm for solving bidiagonal SLAEs
            3. Serial-parallel variant of the backward substitution
      2.  Methods for solving tridiagonal SLAEs
         1. Methods based on the conventional LU decomposition
            1.  Thomas algorithm
               1.  Thomas algorithm, pointwise version
               2.  Repeated Thomas algorithm, pointwise version
            2.  Stone doubling algorithm
               1. Stone doubling algorithm for the LU decomposition of tridiagonal matrices
               2.  Stone doubling algorithm for solving bidiagonal SLAEs
            3.  Serial-parallel method for solving tridiagonal matrices based on the LU decomposition and backward substitutions
         2. Other methods
            1. Reduction method
               1. Complete reduction method
               2. Reduction method repeated for a new right-hand side
            2. Two-sided Thomas algorithm
               1.  Two-sided Thomas algorithm, pointwise version
               2.  Repeated two-sided Thomas algorithm, pointwise version
            3. Cyclic reduction
               1.  Complete cyclic reduction
               2. Cyclic reduction repeated for a new right-hand side
            4. Bordering method
      3. Methods for solving block triangular matrices
         1. Block forward substitution (real version)
         2. Block backward substitution (real version)
         3. Methods for solving block bidiagonal matrices
            1. Forward and backward substitution for block bidiagonal matrices
            2. Stone doubling algorithm for solving block bidiagonal matrices
            3. Serial-parallel variant of the block backward substitution for solving block bidiagonal matrices
      4. Methods for solving block tridiagonal matrices
         1. Methods based on the conventional LU decomposition
            1.  Block Thomas algorithm
            2. Serial-parallel method for solving block systems of linear algebraic equations based on the LU decomposition and backward substitutions
         2. Other methods
            1.  Two-sided Thomas algorithm, block variant
            2. Block cyclic reduction
            3. Block bordering method
   3. Solving systems of linear algebraic equations with coefficient matrices of special form whose inverses are known
2. Iterative methods for solving systems of linear algebraic equations
   1.  High Performance Conjugate Gradient (HPCG) benchmark
   2.  Biconjugate gradient stabilized method (BiCGStab)
   3.  Kaczmarz's algorithm

1.4 Solving eigenvalue problems

1.  Eigenvalue decomposition (finding eigenvalues and eigenvectors)
   1.  QR algorithm
      1.  QR algorithm as implemented in SCALAPACK
         1.  Classical point-wise Householder (reflections) method for reducing a matrix to Hessenberg form
         2.  Hessenberg QR algorithm as implemented in SCALAPACK
      2.  Symmetric QR algorithm as implemented in SCALAPACK
         1.  Householder (reflections) method for reducing a symmetric matrix to tridiagonal form
         2. Symmetric tridiagonal QR algorithm as implemented in SCALAPACK
      3.  QR algorithm for complex Hermitian matrices as implemented in SCALAPACK
         1.  Householder (reflections) method for reducing a complex Hermitian matrix to symmetric tridiagonal form
         2. Symmetric tridiagonal QR algorithm as implemented in SCALAPACK
   2.  The Jacobi (rotations) method for solving the symmetric eigenvalue problem
      1.  The classical Jacobi (rotations) method with pivoting for symmetric matrices
      2.  Serial Jacobi (rotations) method for symmetric matrices
      3.  Serial Jacobi (rotations) method with thresholds for symmetric matrices
   3. Lanczos algorithm
      1.  Lanczos algorithm in exact algorithm (without reorthogonalization)
2. Partial eigenvalue problem
   1. Method of bisection
3.  Singular value decomposition (finding singular values and singular vectors)
   1.  Jacobi (rotations) method for finding singular values
      1. Serial Jacobi (rotations) method for finding singular values
      2. Jacobi method with a special choice of rotations for finding singular values
   2. QR algorithm as applied to singular value decomposition алгоритм

1.5 Algebra of polynomials

1.  Horners method

2 Algorithms on lists and arrays

2.1 Search algorithms

1. Linear search: Finding an item in an arbitrary list, [math]O(n)[/math]
2.  Binary search: Finding the position of a target value within a sorted array, [math]O(\log(n))[/math]

2.2 Sorting algorithms

1. Binary tree sort
2. Bubble sort
3. Merge sort (serial and parallel variants)

2.3 Graph algorithms

1. Graph traversal
   1.  Breadth-first search (BFS)
   2.  Depth-first search (DFS)
2.  Single Source Shortest Path (SSSP)
   1.  Breadth-first search (BFS) (for unweighted graphs)
   2.  Dijkstra's algorithm
   3.  Bellman-Ford algorithm
   4.  Δ-stepping algorithm
3.  All Pairs Shortest Path (APSP)
   1.  Johnson's algorithm
   2.  Floyd-Warshall algorithm
4.  Transitive closure of a directed graph
   1.  Purdom's algorithm
5.  Longest shortest path
6.  Construction of the minimum spanning tree (MST)
   1.  Boruvka's algorithm
   2.  Kruskal's algorithm
   3.  Prim's algorithm
   4.  GHS algorithm
7.  Search for isomorphic subgraphs
   1.  Ullman's algorithm
   2.  VF2 algorithm
8.  Graph connectivity
   1.  Shiloach-Vishkin algorithm for finding the connected components
   2.  Disjoint set union
   3.  Tarjan's strongly connected components algorithm
   4.  DCSC algorithm for finding the strongly connected components
   5.  Tarjan's biconnected components algorithm
   6.  Tarjan-Vishkin biconnected components algorithm
   7.  Tarjan's algorithm for finding the bridges of a graph
   8.  Vertex connectivity of a graph
   9.  Gabow's edge connectivity algorithm
9.  Finding maximal flow in a transportation network
   1.  Ford–Fulkerson algorithm
   2.  Preflow-Push algorithm
10.  Finding minimal-cost flow in a transportation network
11.  Assignment problem
    1.  Hungarian algorithm
    2.  Auction algorithm
    3.  Hopcroft–Karp algorithm
12. Betweenness centrality algorithm

3 Computational geometry

1. Finding the diameter of a point set
2. Finding the convex hull of a point set
3. Delaunay triangulation
4. Voronoi diagram
5. Point-in-polygon problem
6. Convex polygon intersection
7. Star-shaped polygon intersection

3.1 Computer graphics

1. Line drawing algorithms: Approximating a line segment on discrete graphical media
2. Determining visible parts of a three-dimensional scene
3. Ray tracing: Rendering realistic images
4. Global illumination: Regarding direct illumination and reflection from other objects

4 Computer analysis and modeling

4.1 Computer benchmarks

1.  High Performance Conjugate Gradient (HPCG) benchmark
2.  Linpack benchmark

4.2 Algorithms of quantum system simulation

1. Algorithms of quantum computation simulation
   1.  Single-qubit transform of a state vector
   2.  Two-qubit transform of a state vector
   3. Quantum Fourier transform simulation

4.3 Machine learning algorithms

1.  k-means clustering

4.3.1 Neural networks

1. Pattern recognition
   1. Text recognition
   2. Speech recognition
   3.  Face recognition

5 Miscellaneous applied problems

5.1 Optimization algorithms

1. Linear programming
2. Simplex algorithm
3. Branch and bound method
4. Genetic algorithms
5. Ant colony algorithms
6. Hybrid algorithms
7.  Stochastic dual dynamic programming (SDDP)

5.2 Solving systems of nonlinear equations

1.  Newton's method for systems of nonlinear equations

5.3 Numerical quadrature

1.  Cubature rules
2.  Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)
   1. Rectangle rule
   2. Trapezoid rule
   3. Simpson rule
   4. Gauss rule

5.4 Algorithms for solving equations of mathematical physics

1.  Poisson equation, solving with DFT

6 Cryptographic algorithms

1.  Meet-in-the-middle attack