Difference between revisions of "Algorithm classification"

From Algowiki
Jump to navigation Jump to search
[quality revision][quality revision]
 
(9 intermediate revisions by the same user not shown)
Line 1: Line 1:
# <div id="Vector operations">'''Vector operations'''</div>
+
__TOC__
## {{level|Pairwise summation}}
+
= Linear algebra problems =
### {{level|Pairwise summation of numbers}}
+
 
### {{level|Parallel prefix scan algorithm using pairwise summation}}
+
==Matrix and vector operations==
## {{level|Uniform norm of a vector: Real version, serial-parallel variant}}
+
===Vector operations===
## {{level|Dot product}}
+
# {{level|Pairwise summation}}
## {{level|The serial-parallel summation method}}
+
## {{level|Pairwise summation of numbers}}
# <div id="Matrix-vector operations">'''Matrix-vector operations'''</div>
+
## {{level|Parallel prefix scan algorithm using pairwise summation}}
## {{level|Dense matrix-vector multiplication}}
+
# {{level|Uniform norm of a vector: Real version, serial-parallel variant}}
# <div id="Matrix operations">'''Matrix operations'''</div>
+
# {{level|Dot product}}
## {{level|Dense matrix multiplication}}
+
# {{level|The serial-parallel summation method}}
# <div id="Matrix decompositions">'''Matrix decompositions'''</div>
+
=== Matrix-vector operations ===
## ''Triangular decompositions''
+
==== Multiplying a nonsingular matrix by a vector ====
### Gaussian elimination (finding the LU decomposition)
+
# {{level|Dense matrix-vector multiplication}}
### {{level|Gaussian elimination}}
+
==== Multiplying a matrix of special form by a vector ====
##### LU decomposition via Gaussian elimination  
+
# {{level|Fourier transform}}
##### Compact scheme for Gaussian elimination and its modifications  
+
## {{level|Fast Fourier transform for composite dimension}}
###### Compact scheme for Gaussian elimination: Dense matrix  
+
### {{level|Fast Fourier transform for powers-of-two}}
###### {{level|Compact scheme for Gaussian elimination and its modifications: Tridiagonal matrix}}
+
#### {{level|Cooley–Tukey Fast Fourier Transform, radix-2 case}}
####### {{level|Compact scheme for Gaussian elimination: Tridiagonal matrix, serial variant}}
+
#### {{level|Fast Fourier transform for even powers-of-two}}
####### {{level|Stone doubling algorithm for the LU decomposition of a tridiagonal matrix}}
+
### {{level|Fast Fourier transform for composite dimension with small prime divisors (2,3,5,7)}}
####### {{level|Serial-parallel algorithm for the LU decomposition of a tridiagonal matrix}}
+
## {{level|Fast Fourier transform for prime dimension}}
#### Gaussian elimination with pivoting  
+
===Matrix operations===
##### Gaussian elimination with column pivoting  
+
# {{level|Dense matrix multiplication}}
##### Gaussian elimination with row pivoting  
+
## {{level|Dense matrix multiplication (serial version for real matrices)}}
##### Gaussian elimination with diagonal pivoting  
+
## {{level|Strassen's algorithm}}
##### Gaussian elimination with complete pivoting  
+
 
### {{level|Cholesky method}}
+
==Matrix decompositions==
#### {{level|Cholesky decomposition}}
+
{{level|Matrix decomposition problem}}
### {{level|Available triangular decompositions for matrices of special form}}
+
# {{level|Triangular decompositions}}
## ''Unitary-triangular decompositions''
+
## {{level|Gaussian elimination (finding the LU decomposition)}}
### {{level|Givens method}}
+
### {{level|LU decomposition using Gaussian elimination without pivoting}}
### {{level|Householder method (reflection method) for the QR-decomposition of a matrix}}
+
#### {{level|LU decomposition via Gaussian elimination}}
## ''Unitary Hessenberg decompositions''
+
#### {{level|Gaussian elimination, compact scheme for tridiagonal matrices and its modifications}}
### {{level|Householder method (reflection method) for reducing a matrix to Hessenberg (bidiagonal) form}}
+
##### {{level|Compact scheme for Gaussian elimination: Dense matrix}}
### {{level|Givens method (rotation method) for reducing a matrix to Hessenberg (bidiagonal) form}}
+
##### {{level|Compact scheme for Gaussian elimination and its modifications: Tridiagonal matrix}}
## ''Unitary-diagonal decompositions''
+
###### {{level|Gaussian elimination, compact scheme for tridiagonal matrices, serial version}}
### {{level|Eigenvalue decomposition (finding eigenvalues and eigenvectors)}}
+
###### {{level|Stone doubling algorithm for the LU decomposition of a tridiagonal matrix}}
 +
###### {{level|Serial-parallel algorithm for the LU decomposition of a tridiagonal matrix}}
 +
### {{level|LU decomposition using Gaussian elimination with pivoting}}
 +
#### {{level|Gaussian elimination with column pivoting}}
 +
#### {{level|Gaussian elimination with row pivoting}}
 +
#### {{level|Gaussian elimination with diagonal pivoting}}
 +
#### {{level|Gaussian elimination with complete pivoting}}
 +
## {{level|Cholesky method}}
 +
### {{level|Cholesky decomposition}}
 +
# {{level|Available triangular decompositions for matrices of special form}}
 +
# {{level|Unitary-triangular factorizations}}
 +
## {{level|QR decomposition of dense nonsingular matrices}}
 +
### {{level|Givens (rotations) method for the QR decomposition of a matrix}}
 +
#### {{level|Givens method}}
 +
### {{level|Householder (reflections) method for the QR decomposition of a matrix}}
 +
#### {{level|Householder (reflections) method for the QR decomposition of a square matrix, real point-wise version}}
 +
### {{level|Orthogonalization method}}
 +
#### {{level|Classical orthogonalization method}}
 +
#### {{level|Orthogonalization method with reorthogonalization}}
 +
### {{level|Triangular decomposition of a Gram matrix}}
 +
## {{level|QR decomposition methods for dense Hessenberg matrices}}
 +
### {{level|Givens (rotations) method for the QR decomposition of a (real) Hessenberg matrix}}
 +
### {{level|Householder (reflections) method for the QR decomposition of a (real) Hessenberg matrix}}
 +
# {{level|Reducing matrices to compact forms}}
 +
## {{level|Unitary reductions to Hessenberg form}}
 +
### {{level|Householder (reflections) method for reducing of a matrix to Hessenberg form}}
 +
#### {{level|Classical point-wise Householder (reflections) method for reducing a matrix to Hessenberg form}}
 +
### {{level|Givens (rotations) method for reducing a matrix to Hessenberg form}}
 +
#### {{level|Classical point-wise Givens (rotations) method for reducing a matrix to Hessenberg form}}
 +
## {{level|Unitary reductions to tridiagonal form}}
 +
### {{level|Householder (reflections) method for reducing to tridiagonal form}}
 +
#### {{level|Householder (reflections) method for reducing a symmetric matrix to tridiagonal form}}
 +
#### {{level|Householder (reflections) method for reducing a complex Hermitian matrix to symmetric tridiagonal form}}
 +
### {{level|Givens (rotations) reduction to tridiagonal form}}
 +
## {{level|Eigenvalue decomposition (finding eigenvalues and eigenvectors)}}
 +
# {{level|Unitary non-similarity reductions to compact forms}}
 +
## {{level|Unitary reduction to bidiagonal form}}
 +
### {{level|Householder (reflections) reduction of a matrix to bidiagonal form}}
 +
### {{level|Givens (rotations) reduction of a matrix to bidiagonal form}}
 +
## {{level|Singular value decomposition}}
 
### {{level|Singular value decomposition (finding singular values and singular vectors)}}
 
### {{level|Singular value decomposition (finding singular values and singular vectors)}}
# <div id="Solving systems of linear algebraic equations">'''Solving systems of linear algebraic equations'''</div>
+
#### {{level|Methods for calculating singular values of bidiagonal matrices}}
## ''Direct methods''
+
##### {{level|The dqds algorithm for calculating singular values of bidiagonal matrices}}
### {{level|Linpack benchmark)}}
+
###### {{level|One step of the dqds algorithm}}
### ''Matrices of a special form''
+
 
#### ''Triangular matrices''
+
==Solving systems of linear algebraic equations==
##### {{level|Forward substitution}}
+
# {{level|Direct methods}}
##### {{level|Backward substitution}}
+
## {{level|Linpack benchmark}}
#### ''Bidiagonal matrices''
+
## {{level|Matrices of a special form}}
###### {{level|Forward and backward substitution for bidiagonal matrices}}
+
### {{level|Triangular matrices}}
###### {{level|Stone doubling algorithm for solving bidiagonal matrices}}
+
#### {{level|Forward substitution}}
###### {{level|Serial-parallel variant of the backward substitution}}
+
#### {{level|Backward substitution}}
#### {{level|Methods for solving tridiagonal SLAEs}}
+
#### {{level|Bidiagonal matrices}}
##### ''Methods based on the conventional LU decomposition''
+
##### {{level|Forward and backward substitution for bidiagonal matrices}}
###### ''Thomas algorithm''
+
##### {{level|Stone doubling algorithm for solving bidiagonal SLAEs}}
####### {{level|Thomas algorithm, pointwise version}}
+
##### {{level|Serial-parallel variant of the backward substitution}}
####### {{level|Repeated Thomas algorithm, pointwise version|Thomas algorithm repeated for a new right-hand side: Classical scheme}}
+
### {{level|Methods for solving tridiagonal SLAEs}}
###### {{level|Stone doubling algorithm}}
+
#### {{level|Methods based on the conventional LU decomposition}}
###### {{level|Serial-parallel method for solving tridiagonal matrices based on the LU decomposition and backward substitutions}}
+
##### {{level|Thomas algorithm}}
##### Other methods  
+
###### {{level|Thomas algorithm, pointwise version}}
###### {{level|Reduction method}}
+
###### {{level|Repeated Thomas algorithm, pointwise version}}
####### {{level|Complete reduction method}}
+
##### {{level|Stone doubling algorithm}}
####### {{level|Reduction method repeated for a new right-hand side}}
+
###### {{level|Stone doubling algorithm for the LU decomposition of tridiagonal matrices}}
###### Two-sided Thomas algorithm  
+
###### {{level|Stone doubling algorithm for solving bidiagonal SLAEs}}
####### {{level|Two-sided Thomas algorithm, pointwise version|Classical two-sided scheme}}
+
##### {{level|Serial-parallel method for solving tridiagonal matrices based on the LU decomposition and backward substitutions}}
####### {{level|Repeated two-sided Thomas algorithm, pointwise version|Thomas algorithm repeated for a new right-hand side: Two-sided scheme }}
+
#### Other methods
###### {{level|Cyclic reduction}}
+
##### {{level|Reduction method}}
####### {{level|Complete cyclic reduction}}
+
###### {{level|Complete reduction method}}
####### {{level|Cyclic reduction repeated for a new right-hand side}}
+
###### {{level|Reduction method repeated for a new right-hand side}}
###### {{level|Bordering method}}
+
##### {{level|Two-sided Thomas algorithm }}
#### Methods for solving block triangular matrices  
+
###### {{level|Two-sided Thomas algorithm, pointwise version}}
##### {{level|Block forward substitution (real version)|Block forward substitution}}
+
###### {{level|Repeated two-sided Thomas algorithm, pointwise version}}
##### {{level|Block backward substitution (real version))|Block backward substitution}}
+
##### {{level|Cyclic reduction}}
##### Methods for solving block bidiagonal matrices  
+
###### {{level|Complete cyclic reduction}}
###### {{level|Forward and backward substitution for block bidiagonal matrices}}
+
###### {{level|Cyclic reduction repeated for a new right-hand side}}
###### {{level|Stone doubling algorithm for solving block bidiagonal matrices}}
+
##### {{level|Bordering method}}
###### {{level|Serial-parallel variant of the block backward substitution for solving block bidiagonal matrices}}
+
### Methods for solving block triangular matrices  
#### {{level|Methods for solving block tridiagonal matrices}}
+
#### {{level|Block forward substitution (real version)}}
##### Methods based on the conventional LU decomposition  
+
#### {{level|Block backward substitution (real version)}}
###### {{level|Block Thomas algorithm}}
+
#### Methods for solving block bidiagonal matrices
###### {{level|Serial-parallel method for solving block systems of linear algebraic equations based on the LU decomposition and backward substitutions}}
+
##### {{level|Forward and backward substitution for block bidiagonal matrices}}
##### Other methods  
+
##### {{level|Stone doubling algorithm for solving block bidiagonal matrices}}
###### {{level|Two-sided Thomas algorithm, block variant}}
+
##### {{level|Serial-parallel variant of the block backward substitution for solving block bidiagonal matrices}}
###### {{level|Block cyclic reduction}}
+
### {{level|Methods for solving block tridiagonal matrices}}
###### {{level|Block bordering method}}
+
#### Methods based on the conventional LU decomposition
### {{level|Solving systems of linear algebraic equations with coefficient matrices of special form whose inverses are known}}
+
##### {{level|Block Thomas algorithm}}
## ''Iterative methods for solving systems of linear algebraic equations''
+
##### {{level|Serial-parallel method for solving block systems of linear algebraic equations based on the LU decomposition and backward substitutions}}
### {{level|High Performance Conjugate Gradient (HPCG) benchmark}}
+
#### Other methods
# <div id="Solving eigenvalue problems">'''Solving eigenvalue problems'''</div>
+
##### {{level|Two-sided Thomas algorithm, block variant}}
## {{level|Eigenvalue decomposition (finding eigenvalues and eigenvectors)}}
+
##### {{level|Block cyclic reduction}}
### {{level|QR algorithm}}
+
##### {{level|Block bordering method}}
### {{level|Givens method (rotation method) for solving the symmetric eigenvalue problem}}
+
## {{level|Solving systems of linear algebraic equations with coefficient matrices of special form whose inverses are known}}
## {{level|Singular value decomposition (finding singular values and singular vectors)}}
+
# Iterative methods for solving systems of linear algebraic equations
# <div id="Computer benchmarks">'''Computer benchmarks'''</div>
 
 
## {{level|High Performance Conjugate Gradient (HPCG) benchmark}}
 
## {{level|High Performance Conjugate Gradient (HPCG) benchmark}}
## {{level|Linpack benchmark}}
+
## {{level|Biconjugate gradient stabilized method (BiCGStab)}}
# <div id="Fourier transform">'''Fourier transform'''</div>
+
## {{level|Kaczmarz's algorithm}}
## {{level|Cooley–Tukey Fast Fourier Transform, radix-2 case}}
+
 
# <div id="Algebra of polynomials">'''Algebra of polynomials'''</div>
+
==Solving eigenvalue problems==
## {{level|Horners method}}
+
# {{level|Eigenvalue decomposition (finding eigenvalues and eigenvectors)}}
# <div id="Numerical quadrature">'''Numerical quadrature'''</div>
+
## {{level|QR algorithm}}
## {{level|Cubature rules}}
+
### {{level|QR algorithm as implemented in SCALAPACK}}
## {{level|Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)}}
+
#### {{level|Classical point-wise Householder (reflections) method for reducing a matrix to Hessenberg form}}
### [[Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Rectangle rule|Rectangle rule]]
+
#### {{level|Hessenberg QR algorithm as implemented in SCALAPACK}}
### [[Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Trapezoidal rule|Trapezoid rule]]
+
### {{level|Symmetric QR algorithm as implemented in SCALAPACK}}
### [[Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Simpson rule|Simpson rule]]
+
#### {{level|Householder (reflections) method for reducing a symmetric matrix to tridiagonal form}}
### [[Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Gaussian rule|Gauss rule]]
+
#### {{level|Symmetric tridiagonal QR algorithm as implemented in SCALAPACK}}
# <div id="Graph algorithms">'''Graph algorithms'''</div>
+
### {{level|QR algorithm for complex Hermitian matrices as implemented in SCALAPACK}}
## Graph traversal
+
#### {{level|Householder (reflections) method for reducing a complex Hermitian matrix to symmetric tridiagonal form}}
### {{level|Breadth-first search (BFS)}}
+
#### {{level|Symmetric tridiagonal QR algorithm as implemented in SCALAPACK}}
### {{level|Depth-first search (DFS)}}
+
## {{level|The Jacobi (rotations) method for solving the symmetric eigenvalue problem}}
## {{level|Single Source Shortest Path (SSSP)}}
+
### {{level|The classical Jacobi (rotations) method with pivoting for symmetric matrices}}
### {{level|Breadth-first search (BFS)}} (for unweighted graphs)
+
### {{level|Serial Jacobi (rotations) method for symmetric matrices}}
### {{level|Dijkstra's algorithm}}
+
### {{level|Serial Jacobi (rotations) method with thresholds for symmetric matrices}}
### {{level|Bellman-Ford algorithm}}
+
## {{level|Lanczos algorithm}}
### {{level|Δ-stepping algorithm}}
+
### {{level|Lanczos algorithm in exact algorithm (without reorthogonalization)}}
## {{level|All Pairs Shortest Path (APSP)}}
+
# {{level|Partial eigenvalue problem}}
### {{level|Johnson's algorithm}}
+
## {{level|Method of bisection}}
### {{level|Floyd-Warshall algorithm}}
+
# {{level|Singular value decomposition (finding singular values and singular vectors)}}
## {{level|Transitive closure of a directed graph}}
+
## {{level|Jacobi (rotations) method for finding singular values}}
### {{level|Purdom's algorithm}}
+
### {{level|Serial Jacobi (rotations) method for finding singular values}}
## {{level|Longest shortest path}}
+
### {{level|Jacobi method with a special choice of rotations for finding singular values}}
## {{level|Construction of the minimum spanning tree (MST)}}
+
## {{level|QR algorithm as applied to singular value decomposition алгоритм}}
### {{level|Boruvka's akgorithm}}
+
 
### {{level|Kruskal's algorithm}}
+
==Algebra of polynomials==
### {{level|Prim's algorithm}}
+
# {{level|Horners method}}
### {{level|GHS algorithm}}
+
 
## {{level|Search for isomorphic subgraphs}}
+
= Algorithms on lists and arrays =
### {{level|Ullman's algorithm}}
+
 
### {{level|VF2 algorithm}}
+
==Search algorithms==
## {{level|Graph connectivity}}
+
# {{level|Linear search: Finding an item in an arbitrary list|Linear search}}, <math>O(n)</math>
### {{level|Shiloach-Vishkin algorithm for finding the connected components}}
+
# {{level|Binary search: Finding the position of a target value within a sorted array}}, <math>O(\log(n))</math>
### {{level|Disjoint set union}}
+
 
### {{level|Tarjan's strongly connected components algorithm}}
+
==Sorting algorithms==
### {{level|DCSC algorithm for finding the strongly connected components}}
+
# {{level|Binary tree sort}}
### {{level|Tarjan's biconnected components algorithm}}
+
# {{level|Bubble sort}}
### {{level|Tarjan-Vishkin biconnected components algorithm}}
+
# {{level|Merge sort (serial and parallel variants)}}
### {{level|Tarjan's algorithm for finding the bridges of a graph}}
+
 
### {{level|Vertex connectivity of a graph}}
+
==Graph algorithms==
### {{level|Gabow's edge connectivity algorithm}}
+
# Graph traversal
## {{level|Finding maximal flow in a transportation network}}
+
## {{level|Breadth-first search (BFS)}}
### {{level|Ford–Fulkerson algorithm}}
+
## {{level|Depth-first search (DFS)}}
### {{level|Preflow-Push algorithm}}
+
# {{level|Single Source Shortest Path (SSSP)}}
## {{level|Finding minimal-cost flow in a transportation network}}
+
## {{level|Breadth-first search (BFS)}} (for unweighted graphs)
## {{level|Assignment problem}}
+
## {{level|Dijkstra's algorithm}}
### {{level|Hungarian algorithm}}
+
## {{level|Bellman-Ford algorithm}}
### {{level|Auction algorithm}}
+
## {{level|Δ-stepping algorithm}}
### {{level|Hopcroft–Karp algorithm}}
+
# {{level|All Pairs Shortest Path (APSP)}}
## {{level|Betweenness centrality algorithm|Finding the betweenness centrality of vertices}}
+
## {{level|Johnson's algorithm}}
# <div id="Search algorithms">'''Search algorithms'''</div>
+
## {{level|Floyd-Warshall algorithm}}
## {{level|Binary search: Finding the position of a target value within a sorted array}}, <math>O(log(n))</math>
+
# {{level|Transitive closure of a directed graph}}
# <div id="Sorting algorithms">'''Sorting algorithms'''</div>
+
## {{level|Purdom's algorithm}}
## {{level|Binary tree sort}}
+
# {{level|Longest shortest path}}
## {{level|Bubble sort}}
+
# {{level|Construction of the minimum spanning tree (MST)}}
## {{level|Merge sort (serial and parallel variants)}}
+
## {{level|Boruvka's algorithm}}
# <div id="Computational geometry">'''Computational geometry'''</div>
+
## {{level|Kruskal's algorithm}}
## {{level|Finding the diameter of a point set}}
+
## {{level|Prim's algorithm}}
## {{level|Finding the convex hull of a point set}}
+
## {{level|GHS algorithm}}
## {{level|Delaunay triangulation}}
+
# {{level|Search for isomorphic subgraphs}}
## {{level|Voronoi diagram}}
+
## {{level|Ullman's algorithm}}
## {{level|Point-in-polygon problem}}
+
## {{level|VF2 algorithm}}
## {{level|Convex polygon intersection}} - complexity <math>O(n_1 + n_2)</math>
+
# {{level|Graph connectivity}}
## {{level|Star-shaped polygon intersection}} - complexity <math>O(n_1 * n_2)</math>
+
## {{level|Shiloach-Vishkin algorithm for finding the connected components}}
# <div id="Computer graphics">'''Computer graphics'''</div>
+
## {{level|Disjoint set union}}
## {{level|Line drawing algorithms: Approximating a line segment on discrete graphical media}}
+
## {{level|Tarjan's strongly connected components algorithm}}
## {{level|Determining visible parts of a three-dimensional scene}}
+
## {{level|DCSC algorithm for finding the strongly connected components}}
## {{level|Ray tracing: Rendering realistic images}}
+
## {{level|Tarjan's biconnected components algorithm}}
## {{level|Global illumination: Regarding direct illumination and reflection from other objects}}
+
## {{level|Tarjan-Vishkin biconnected components algorithm}}
# <div id="Cryptographic algorithms">'''Cryptographic algorithms'''</div>
+
## {{level|Tarjan's algorithm for finding the bridges of a graph}}
# <div id="Neural networks">'''Neural networks'''</div>
+
## {{level|Vertex connectivity of a graph}}
# <div id="Optimization algorithms">'''Optimization algorithms'''</div>
+
## {{level|Gabow's edge connectivity algorithm}}
## {{level|Linear programming}}
+
# {{level|Finding maximal flow in a transportation network}}
## {{level|Simplex algorithm}}
+
## {{level|Ford–Fulkerson algorithm}}
## {{level|Branch and bound method (serial and parallel variants)}}
+
## {{level|Preflow-Push algorithm}}
## {{level|Genetic algorithms}}
+
# {{level|Finding minimal-cost flow in a transportation network}}
## {{level|Ant colony algorithms}}
+
# {{level|Assignment problem}}
## {{level|Hybrid algorithms}}
+
## {{level|Hungarian algorithm}}
## {{level|Finding extrema of a function}}
+
## {{level|Auction algorithm}}
# <div id="Game theory algorithms">'''Game theory algorithms'''</div>
+
## {{level|Hopcroft–Karp algorithm}}
# <div id="Algorithms of quantum system simulation">'''Algorithms of quantum system simulation'''</div>
+
# {{level|Betweenness centrality algorithm}}
## ''Algorithms of quantum computation simulation''
+
 
### {{level|Single-qubit transform of a state vector}}
+
=Computational geometry=
### {{level|Two-qubit transform of a state vector}}
+
# {{level|Finding the diameter of a point set}}
### {{level|Quantum Fourier transform simulation}}
+
# {{level|Finding the convex hull of a point set}}
# <div id="Algorithms for solving equations of mathematical physics">'''Algorithms for solving equations of mathematical physics'''</div>
+
# {{level|Delaunay triangulation}}
## {{level|Poisson equation, solving with DFT}}
+
# {{level|Voronoi diagram}}
# <div id="Other algorithms">'''Other algorithms'''</div>
+
# {{level|Point-in-polygon problem}}
 +
# {{level|Convex polygon intersection}}  
 +
# {{level|Star-shaped polygon intersection}}
 +
 
 +
==Computer graphics==
 +
# {{level|Line drawing algorithms: Approximating a line segment on discrete graphical media}}
 +
# {{level|Determining visible parts of a three-dimensional scene}}
 +
# {{level|Ray tracing: Rendering realistic images}}
 +
# {{level|Global illumination: Regarding direct illumination and reflection from other objects}}
 +
 
 +
=Computer analysis and modeling=
 +
 
 +
==Computer benchmarks==
 +
# {{level|High Performance Conjugate Gradient (HPCG) benchmark}}
 +
# {{level|Linpack benchmark}}
 +
 
 +
==Algorithms of quantum system simulation==
 +
# {{level|Algorithms of quantum computation simulation}}
 +
## {{level|Single-qubit transform of a state vector}}
 +
## {{level|Two-qubit transform of a state vector}}
 +
## {{level|Quantum Fourier transform simulation}}
 +
 
 +
==Machine learning algorithms==
 +
# {{level|k-means clustering}}
 +
 
 +
===Neural networks===
 +
# {{level|Pattern recognition}}
 +
## {{level|Text recognition}}
 +
## {{level|Speech recognition}}
 +
## {{level|Face recognition}}
 +
 
 +
===Game theory algorithms===
 +
 
 +
= Miscellaneous applied problems =
 +
 
 +
==Optimization algorithms==
 +
# {{level|Linear programming}}
 +
# {{level|Simplex algorithm}}
 +
# {{level|Branch and bound method}}
 +
# {{level|Genetic algorithms}}
 +
# {{level|Ant colony algorithms}}
 +
# {{level|Hybrid algorithms}}
 +
# {{level|Stochastic dual dynamic programming (SDDP)}}
 +
 
 +
==Solving systems of nonlinear equations==
 +
# {{level|Newton's method for systems of nonlinear equations}}
 +
 
 +
==Numerical quadrature==
 +
# {{level|Cubature rules}}
 +
# {{level|Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)}}
 +
## {{level|Rectangle rule}}
 +
## {{level|Trapezoid rule}}
 +
## {{level|Simpson rule}}
 +
## {{level|Gauss rule}}
 +
 
 +
==Algorithms for solving equations of mathematical physics==
 +
# {{level|Poisson equation, solving with DFT}}
 +
 
 +
=Cryptographic algorithms=
 +
# {{level|Meet-in-the-middle attack}}
 +
 
 +
=Other algorithms=
  
 
[[Ru:Классификация алгоритмов]]
 
[[Ru:Классификация алгоритмов]]

Latest revision as of 13:06, 15 March 2018

1 Linear algebra problems

1.1 Matrix and vector operations

1.1.1 Vector operations

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

1.1.2 Matrix-vector operations

1.1.2.1 Multiplying a nonsingular matrix by a vector

  1. Algorithm level 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. Method level Fast Fourier transform for powers-of-two
        1. Algorithm level 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. Problem level Dense matrix multiplication
    1. Algorithm level Dense matrix multiplication (serial version for real matrices)
    2. Strassen's algorithm

1.2 Matrix decompositions

Problem level Matrix decomposition problem

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

1.3 Solving systems of linear algebraic equations

  1. Direct methods
    1. Algorithm level Linpack benchmark
    2. Matrices of a special form
      1. Triangular matrices
        1. Algorithm level Forward substitution
        2. Algorithm level Backward substitution
        3. Bidiagonal matrices
          1. Forward and backward substitution for bidiagonal matrices
          2. Algorithm level Stone doubling algorithm for solving bidiagonal SLAEs
          3. Serial-parallel variant of the backward substitution
      2. Problem level Methods for solving tridiagonal SLAEs
        1. Methods based on the conventional LU decomposition
          1. Method level Thomas algorithm
            1. Algorithm level Thomas algorithm, pointwise version
            2. Algorithm level Repeated Thomas algorithm, pointwise version
          2. Method level Stone doubling algorithm
            1. Stone doubling algorithm for the LU decomposition of tridiagonal matrices
            2. Algorithm level Stone doubling algorithm for solving bidiagonal SLAEs
          3. Method level 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. Algorithm level Two-sided Thomas algorithm, pointwise version
            2. Algorithm level Repeated two-sided Thomas algorithm, pointwise version
          3. Cyclic reduction
            1. Algorithm level 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. Algorithm level 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. Algorithm level 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. Algorithm level High Performance Conjugate Gradient (HPCG) benchmark
    2. Algorithm level Biconjugate gradient stabilized method (BiCGStab)
    3. Algorithm level Kaczmarz's algorithm

1.4 Solving eigenvalue problems

  1. Problem level Eigenvalue decomposition (finding eigenvalues and eigenvectors)
    1. Method level QR algorithm
      1. Algorithm level QR algorithm as implemented in SCALAPACK
        1. Algorithm level Classical point-wise Householder (reflections) method for reducing a matrix to Hessenberg form
        2. Algorithm level Hessenberg QR algorithm as implemented in SCALAPACK
      2. Algorithm level Symmetric QR algorithm as implemented in SCALAPACK
        1. Algorithm level Householder (reflections) method for reducing a symmetric matrix to tridiagonal form
        2. Symmetric tridiagonal QR algorithm as implemented in SCALAPACK
      3. Algorithm level QR algorithm for complex Hermitian matrices as implemented in SCALAPACK
        1. Algorithm level Householder (reflections) method for reducing a complex Hermitian matrix to symmetric tridiagonal form
        2. Symmetric tridiagonal QR algorithm as implemented in SCALAPACK
    2. Method level The Jacobi (rotations) method for solving the symmetric eigenvalue problem
      1. Algorithm level The classical Jacobi (rotations) method with pivoting for symmetric matrices
      2. Algorithm level Serial Jacobi (rotations) method for symmetric matrices
      3. Algorithm level Serial Jacobi (rotations) method with thresholds for symmetric matrices
    3. Lanczos algorithm
      1. Algorithm level Lanczos algorithm in exact algorithm (without reorthogonalization)
  2. Partial eigenvalue problem
    1. Method of bisection
  3. Problem level Singular value decomposition (finding singular values and singular vectors)
    1. Method level 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. Algorithm level 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. Algorithm level 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. Algorithm level Breadth-first search (BFS)
    2. Algorithm level Depth-first search (DFS)
  2. Problem level Single Source Shortest Path (SSSP)
    1. Algorithm level Breadth-first search (BFS) (for unweighted graphs)
    2. Algorithm level Dijkstra's algorithm
    3. Algorithm level Bellman-Ford algorithm
    4. Algorithm level Δ-stepping algorithm
  3. Problem level All Pairs Shortest Path (APSP)
    1. Algorithm level Johnson's algorithm
    2. Algorithm level Floyd-Warshall algorithm
  4. Problem level Transitive closure of a directed graph
    1. Algorithm level Purdom's algorithm
  5. Algorithm level Longest shortest path
  6. Problem level Construction of the minimum spanning tree (MST)
    1. Algorithm level Boruvka's algorithm
    2. Algorithm level Kruskal's algorithm
    3. Algorithm level Prim's algorithm
    4. Algorithm level GHS algorithm
  7. Problem level Search for isomorphic subgraphs
    1. Algorithm level Ullman's algorithm
    2. Algorithm level VF2 algorithm
  8. Problem level Graph connectivity
    1. Algorithm level Shiloach-Vishkin algorithm for finding the connected components
    2. Algorithm level Disjoint set union
    3. Algorithm level Tarjan's strongly connected components algorithm
    4. Algorithm level DCSC algorithm for finding the strongly connected components
    5. Algorithm level Tarjan's biconnected components algorithm
    6. Algorithm level Tarjan-Vishkin biconnected components algorithm
    7. Algorithm level Tarjan's algorithm for finding the bridges of a graph
    8. Algorithm level Vertex connectivity of a graph
    9. Algorithm level Gabow's edge connectivity algorithm
  9. Problem level Finding maximal flow in a transportation network
    1. Algorithm level Ford–Fulkerson algorithm
    2. Algorithm level Preflow-Push algorithm
  10. Problem level Finding minimal-cost flow in a transportation network
  11. Problem level Assignment problem
    1. Algorithm level Hungarian algorithm
    2. Algorithm level Auction algorithm
    3. Algorithm level 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. Algorithm level High Performance Conjugate Gradient (HPCG) benchmark
  2. Algorithm level Linpack benchmark

4.2 Algorithms of quantum system simulation

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

4.3 Machine learning algorithms

  1. Algorithm level k-means clustering

4.3.1 Neural networks

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

4.3.2 Game theory algorithms

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. Algorithm level Stochastic dual dynamic programming (SDDP)

5.2 Solving systems of nonlinear equations

  1. Algorithm level Newton's method for systems of nonlinear equations

5.3 Numerical quadrature

  1. Algorithm level Cubature rules
  2. Algorithm level 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. Algorithm level Poisson equation, solving with DFT

6 Cryptographic algorithms

  1. Algorithm level Meet-in-the-middle attack

7 Other algorithms