Difference between revisions of "Algorithm classification"

From Algowiki
Jump to navigation Jump to search
[quality revision][quality revision]
(Add levels of classification.)
Line 1: Line 1:
 
# <div id="Vector operations">'''Vector operations'''</div>
 
# <div id="Vector operations">'''Vector operations'''</div>
 
## {{level|Pairwise summation}}
 
## {{level|Pairwise summation}}
 +
### {{level|Summing an array by pairwise summation}}
 +
### {{level|Finding partial sums of an array by pairwise summation}}
 +
## {{level|Uniform norm of a vector: Real version, serial-parallel variant}}
 
## {{level|Dot product}}
 
## {{level|Dot product}}
 +
## {{level|Serial-parallel summation method}}
 
# <div id="Matrix-vector operations">'''Matrix-vector operations'''</div>
 
# <div id="Matrix-vector operations">'''Matrix-vector operations'''</div>
 
## {{level|Dense matrix-vector multiplication}}
 
## {{level|Dense matrix-vector multiplication}}
 
# <div id="Matrix operations">'''Matrix operations'''</div>
 
# <div id="Matrix operations">'''Matrix operations'''</div>
 
## {{level|Dense matrix multiplication}}
 
## {{level|Dense matrix multiplication}}
−
# <div id="Matrix decomposition">'''Matrix decomposition'''</div>
+
# <div id="Matrix decompositions">'''Matrix decompositions'''</div>
−
## ''Triangular decomposition''
+
## ''Triangular decompositions''
 +
### Gaussian elimination (finding the LU decomposition)
 
### {{level|Gaussian elimination}}
 
### {{level|Gaussian elimination}}
 +
##### LU decomposition via Gaussian elimination
 +
##### Compact scheme for Gaussian elimination and its modifications
 +
###### Compact scheme for Gaussian elimination: Dense matrix
 +
###### {{level|Compact scheme for Gaussian elimination and its modifications: Tridiagonal matrix}}
 +
####### {{level|Compact scheme for Gaussian elimination: Tridiagonal matrix, serial variant}}
 +
####### {{level|Stone doubling algorithm for the LU decomposition of a tridiagonal matrix}}
 +
####### {{level|Serial-parallel algorithm for the LU decomposition of a tridiagonal matrix}}
 +
#### Gaussian elimination with pivoting
 +
##### Gaussian elimination with column pivoting
 +
##### Gaussian elimination with row pivoting
 +
##### Gaussian elimination with diagonal pivoting
 +
##### Gaussian elimination with complete pivoting
 
### {{level|Cholesky method}}
 
### {{level|Cholesky method}}
 
#### {{level|Cholesky decomposition}}
 
#### {{level|Cholesky decomposition}}
−
## ''Unitary-triangular decomposition''
+
### {{level|Available triangular decompositions for matrices of special form}}
 +
## ''Unitary-triangular decompositions''
 
### {{level|Givens method}}
 
### {{level|Givens method}}
−
## ''Decomposition into unitary and Hessenberg matrices''
+
### {{level|Householder method (reflection method) for the QR-decomposition of a matrix}}
−
## ''Decomposition into unitary and diagonal matrices''
+
## ''Unitary Hessenberg decompositions''
−
# <div id="Solution of linear equations systems">'''Solution of linear equations systems'''</div>
+
### {{level|Householder method (reflection method) for reducing a matrix to Hessenberg (bidiagonal) form}}
 +
### {{level|Givens method (rotation method) for reducing a matrix to Hessenberg (bidiagonal) form}}
 +
## ''Unitary-diagonal decompositions''
 +
### {{level|Eigenvalue decomposition (finding eigenvalues and eigenvectors)}}
 +
### {{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>
 
## ''Direct methods''
 
## ''Direct methods''
 
### ''Linpack benchmark''
 
### ''Linpack benchmark''
Line 22: Line 45:
 
##### {{level|Forward substitution}}
 
##### {{level|Forward substitution}}
 
##### {{level|Backward substitution}}
 
##### {{level|Backward substitution}}
 +
#### ''Bidiagonal matrices''
 +
###### {{level|Forward and backward substitution for bidiagonal matrices}}
 +
###### {{level|Stone doubling algorithm for solving bidiagonal matrices}}
 +
###### {{level|Serial-parallel variant of the backward substitution}}
 
#### ''Tridiagonal matrices''
 
#### ''Tridiagonal matrices''
−
##### ''LU decomposition''
+
##### ''Methods based on the conventional LU decomposition''
 
###### ''Thomas algorithm''
 
###### ''Thomas algorithm''
 
####### {{level|Thomas algorithm, pointwise version}}
 
####### {{level|Thomas algorithm, pointwise version}}
−
## ''Iterative methods''
+
####### {{level|Repeated Thomas algorithm, pointwise version|Thomas algorithm repeated for a new right-hand side: Classical scheme}}
 +
###### {{level|Stone doubling algorithm}}
 +
###### {{level|Serial-parallel method for solving tridiagonal matrices based on the LU decomposition and backward substitutions}}
 +
##### Other methods
 +
###### {{level|Reduction method}}
 +
####### {{level|Complete reduction method}}
 +
####### {{level|Reduction method repeated for a new right-hand side}}
 +
###### Two-sided Thomas algorithm
 +
####### {{level|Two-sided Thomas algorithm, pointwise version|Classical two-sided scheme}}
 +
####### {{level|Repeated two-sided Thomas algorithm, pointwise version|Thomas algorithm repeated for a new right-hand side: Two-sided scheme }}
 +
###### {{level|Cyclic reduction}}
 +
####### {{level|Complete cyclic reduction}}
 +
####### {{level|Cyclic reduction repeated for a new right-hand side}}
 +
###### {{level|Bordering method}}
 +
#### Methods for solving block triangular matrices
 +
##### {{level|Block forward substitution (real version)|Block forward substitution}}
 +
##### {{level|Block backward substitution (real version))|Block backward substitution}}
 +
##### Methods for solving block bidiagonal matrices
 +
###### {{level|Forward and backward substitution for block bidiagonal matrices}}
 +
###### {{level|Stone doubling algorithm for solving block bidiagonal matrices}}
 +
###### {{level|Serial-parallel variant of the block backward substitution for solving block bidiagonal matrices}}
 +
#### {{level|Methods for solving block tridiagonal matrices}}
 +
##### Methods based on the conventional LU decomposition
 +
###### {{level|Block Thomas algorithm}}
 +
###### {{level|Serial-parallel method for solving block systems of linear algebraic equations based on the LU decomposition and backward substitutions}}
 +
##### Other methods
 +
###### {{level|Two-sided Thomas algorithm, block variant}}
 +
###### {{level|Block cyclic reduction}}
 +
###### {{level|Block bordering method}}
 +
### {{level|Solving systems of linear algebraic equations with coefficient matrices of special form whose inverses are known}}
 +
## ''Iterative methods for solving systems of linear algebraic equations''
 +
### {{level|High Performance Conjugate Gradient (HPCG) benchmark}}
 +
# <div id="Solving eigenvalue problems">'''Solving eigenvalue problems'''</div>
 +
## {{level|Eigenvalue decomposition (finding eigenvalues and eigenvectors)}}
 +
### {{level|QR algorithm}}
 +
### {{level|Givens method (rotation method) for solving the symmetric eigenvalue problem}}
 +
## {{level|Singular value decomposition (finding singular values and singular vectors)}}
 
# <div id="Computer benchmarks">'''Computer benchmarks'''</div>
 
# <div id="Computer benchmarks">'''Computer benchmarks'''</div>
 +
## {{level|High Performance Conjugate Gradient (HPCG) benchmark}}
 +
## {{level|Linpack benchmark}}
 
# <div id="Fourier transform">'''Fourier transform'''</div>
 
# <div id="Fourier transform">'''Fourier transform'''</div>
 
## {{level|Cooley–Tukey Fast Fourier Transform, radix-2 case}}
 
## {{level|Cooley–Tukey Fast Fourier Transform, radix-2 case}}
 
# <div id="Algebra of polynomials">'''Algebra of polynomials'''</div>
 
# <div id="Algebra of polynomials">'''Algebra of polynomials'''</div>
 
## {{level|Horners method}}
 
## {{level|Horners method}}
−
# <div id="Numerical integration methods">'''Numerical integration methods'''</div>
+
# <div id="Numerical quadrature">'''Numerical quadrature'''</div>
 +
## {{level|Cubature rules}}
 +
## {{level|Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)}}
 +
### [[Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Rectangle rule|Rectangle rule]]
 +
### [[Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Trapezoid rule|Trapezoid rule]]
 +
### [[Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Simpson rule|Simpson rule]]
 +
### [[Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Gauss rule|Gauss rule]]
 
# <div id="Graph algorithms">'''Graph algorithms'''</div>
 
# <div id="Graph algorithms">'''Graph algorithms'''</div>
 +
## Traversing a graph
 +
### {{level|Breadth-first search (BFS)}}
 +
### {{level|Depth-first search (DFS)}}
 
## {{level|Single Source Shortest Path (SSSP)}}
 
## {{level|Single Source Shortest Path (SSSP)}}
 +
### {{level|Breadth-first search (BFS)}} (for unweighted graphs)
 +
### {{level|Dijkstra's algorithm}}
 +
### {{level|Bellman-Ford algorithm}}
 +
### {{level|Δ-stepping algorithm}}
 
## {{level|All Pairs Shortest Path (APSP)}}
 
## {{level|All Pairs Shortest Path (APSP)}}
 +
### {{level|Johnson's algorithm}}
 +
### {{level|Floyd-Warshall algorithm}}
 
## {{level|Transitive closure of a directed graph}}
 
## {{level|Transitive closure of a directed graph}}
 +
### {{level|Purdom's algorithm}}
 +
## {{level|Longest shortest path}}
 
## {{level|Construction of the minimum spanning tree (MST)}}
 
## {{level|Construction of the minimum spanning tree (MST)}}
 +
### {{level|Boruvka's akgorithm}}
 +
### {{level|Kruskal's algorithm}}
 +
### {{level|Prim's algorithm}}
 +
### {{level|GHS algorithm}}
 
## {{level|Search for isomorphic subgraphs}}
 
## {{level|Search for isomorphic subgraphs}}
 +
### {{level|Ullman's algorithm}}
 +
### {{level|VF2 algorithm}}
 
## {{level|Graph connectivity}}
 
## {{level|Graph connectivity}}
 +
### {{level|Shiloach-Vishkin algorithm for finding the connected components}}
 +
### {{level|Disjoint set union}}
 +
### {{level|Tarjan's strongly connected components algorithm}}
 +
### {{level|DCSC algorithm for finding the strongly connected components}}
 +
### {{level|Tarjan's biconnected components algorithm}}
 +
### {{level|Tarjan-Vishkin biconnected components algorithm}}
 +
### {{level|Tarjan's algorithm for finding the bridges of a graph}}
 +
### {{level|Vertex connectivity of a graph}}
 +
### {{level|Gabow's edge connectivity algorithm}}
 
## {{level|Finding maximal flow in a transportation network}}
 
## {{level|Finding maximal flow in a transportation network}}
 +
### {{level|Ford–Fulkerson algorithm}}
 +
### {{level|Preflow-Push algorithm}}
 +
## {{level|Finding minimal-cost flow in a transportation network}}
 
## {{level|Assignment problem}}
 
## {{level|Assignment problem}}
 +
### {{level|Hungarian algorithm}}
 +
### {{level|Auction algorithm}}
 +
### {{level|Hopcroft–Karp algorithm}}
 +
## {{level|Betweenness centrality algorithm|Finding the betweenness centrality of vertices}}
 
# <div id="Search algorithms">'''Search algorithms'''</div>
 
# <div id="Search algorithms">'''Search algorithms'''</div>
 +
## {{level|Binary search: Finding the position of a target value within a sorted array}}, <math>O(log(n))</math>
 
# <div id="Sorting algorithms">'''Sorting algorithms'''</div>
 
# <div id="Sorting algorithms">'''Sorting algorithms'''</div>
 +
## {{level|Binary tree sort}}
 +
## {{level|Bubble sort}}
 +
## {{level|Merge sort (serial and parallel variants)}}
 
# <div id="Computational geometry">'''Computational geometry'''</div>
 
# <div id="Computational geometry">'''Computational geometry'''</div>
 +
## {{level|Finding the diameter of a point set}}
 +
## {{level|Finding the convex hull of a point set}}
 +
## {{level|Delaunay triangulation}}
 +
## {{level|Voronoi diagram}}
 +
## {{level|Point-in-polygon problem}}
 +
## {{level|Convex polygon intersection}} - complexity <math>O(n_1 + n_2)</math>
 +
## {{level|Star-shaped polygon intersection}} - complexity <math>O(n_1 * n_2)</math>
 
# <div id="Computer graphics">'''Computer graphics'''</div>
 
# <div id="Computer graphics">'''Computer graphics'''</div>
 +
## {{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}}
 
# <div id="Cryptographic algorithms">'''Cryptographic algorithms'''</div>
 
# <div id="Cryptographic algorithms">'''Cryptographic algorithms'''</div>
 
# <div id="Neural networks">'''Neural networks'''</div>
 
# <div id="Neural networks">'''Neural networks'''</div>
 
# <div id="Optimization algorithms">'''Optimization algorithms'''</div>
 
# <div id="Optimization algorithms">'''Optimization algorithms'''</div>
 +
## {{level|Linear programming}}
 +
## {{level|Simplex algorithm}}
 +
## {{level|Branch and bound method (serial and parallel variants)}}
 +
## {{level|Genetic algorithms}}
 +
## {{level|Ant colony algorithms}}
 +
## {{level|Hybrid algorithms}}
 +
## {{level|Finding extrema of a function}}
 
# <div id="Game theory algorithms">'''Game theory algorithms'''</div>
 
# <div id="Game theory algorithms">'''Game theory algorithms'''</div>
 
# <div id="Algorithms of quantum system simulation">'''Algorithms of quantum system simulation'''</div>
 
# <div id="Algorithms of quantum system simulation">'''Algorithms of quantum system simulation'''</div>
 
## ''Algorithms of quantum computation simulation''
 
## ''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}}
 
# <div id="Algorithms for solving equations of mathematical physics">'''Algorithms for solving equations of mathematical physics'''</div>
 
# <div id="Algorithms for solving equations of mathematical physics">'''Algorithms for solving equations of mathematical physics'''</div>
 
## {{level|Poisson equation, solving with DFT}}
 
## {{level|Poisson equation, solving with DFT}}

Revision as of 15:51, 10 May 2016

  1. Vector operations
    1. Method level Pairwise summation
      1. Summing an array by pairwise summation
      2. Finding partial sums of an array by pairwise summation
    2. Algorithm level Uniform norm of a vector: Real version, serial-parallel variant
    3. Algorithm level Dot product
    4. Serial-parallel summation method
  2. Matrix-vector operations
    1. Algorithm level Dense matrix-vector multiplication
  3. Matrix operations
    1. Problem level Dense matrix multiplication
  4. Matrix decompositions
    1. Triangular decompositions
      1. Gaussian elimination (finding the LU decomposition)
      2. Gaussian elimination
          1. LU decomposition via Gaussian elimination
          2. Compact scheme for Gaussian elimination 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. Compact scheme for Gaussian elimination: Tridiagonal matrix, serial variant
              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. 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
      3. Method level Cholesky method
        1. Algorithm level Cholesky decomposition
      4. Available triangular decompositions for matrices of special form
    2. Unitary-triangular decompositions
      1. Algorithm level Givens method
      2. Householder method (reflection method) for the QR-decomposition of a matrix
    3. Unitary Hessenberg decompositions
      1. Householder method (reflection method) for reducing a matrix to Hessenberg (bidiagonal) form
      2. Givens method (rotation method) for reducing a matrix to Hessenberg (bidiagonal) form
    4. Unitary-diagonal decompositions
      1. Problem level Eigenvalue decomposition (finding eigenvalues and eigenvectors)
      2. Problem level Singular value decomposition (finding singular values and singular vectors)
  5. Solving systems of linear algebraic equations
    1. Direct methods
      1. Linpack benchmark
      2. Matrices of a special form
        1. Triangular matrices
          1. Algorithm level Forward substitution
          2. Algorithm level Backward substitution
        2. Bidiagonal matrices
            1. Forward and backward substitution for bidiagonal matrices
            2. Stone doubling algorithm for solving bidiagonal matrices
            3. Serial-parallel variant of the backward substitution
        3. Tridiagonal matrices
          1. Methods based on the conventional LU decomposition
            1. Thomas algorithm
              1. Algorithm level Thomas algorithm, pointwise version
              2. Algorithm level Repeated Thomas algorithm, pointwise version
            2. Method level Stone doubling algorithm
            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
        4. 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
        5. 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
  6. Solving eigenvalue problems
    1. Problem level Eigenvalue decomposition (finding eigenvalues and eigenvectors)
      1. Method level QR algorithm
      2. Givens method (rotation method) for solving the symmetric eigenvalue problem
    2. Problem level Singular value decomposition (finding singular values and singular vectors)
  7. Computer benchmarks
    1. Algorithm level High Performance Conjugate Gradient (HPCG) benchmark
    2. Algorithm level Linpack benchmark
  8. Fourier transform
    1. Algorithm level Cooley–Tukey Fast Fourier Transform, radix-2 case
  9. Algebra of polynomials
    1. Algorithm level Horners method
  10. 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
  11. Graph algorithms
    1. Traversing a graph
      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. Boruvka's akgorithm
      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
  12. Search algorithms
    1. Algorithm level Binary search: Finding the position of a target value within a sorted array, [math]O(log(n))[/math]
  13. Sorting algorithms
    1. Binary tree sort
    2. Bubble sort
    3. Merge sort (serial and parallel variants)
  14. 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 - complexity [math]O(n_1 + n_2)[/math]
    7. Star-shaped polygon intersection - complexity [math]O(n_1 * n_2)[/math]
  15. 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
  16. Cryptographic algorithms
  17. Neural networks
  18. Optimization algorithms
    1. Linear programming
    2. Simplex algorithm
    3. Branch and bound method (serial and parallel variants)
    4. Genetic algorithms
    5. Ant colony algorithms
    6. Hybrid algorithms
    7. Finding extrema of a function
  19. Game theory algorithms
  20. 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
  21. Algorithms for solving equations of mathematical physics
    1. Algorithm level Poisson equation, solving with DFT
  22. Other algorithms
Retrieved from "https://algowiki-project.org/algowiki/en/index.php?title=Algorithm_classification&oldid=684"