Algorithm classification

Jump to navigation Jump to search
Main page

Problems, methods, algorithms and implementations are grouped by subject. Click a triangle to expand a branch; a linked name opens its article.

P ProblemM MethodA AlgorithmI ImplementationAbout classification levelsAn architecture with * occurs in a descendant; without * it is assigned directly. A dash means no data.
ContentsGPUMPPSMPVEC
Linear algebra problems————
Matrix and vector operations————
Vector operations————
MPairwise summation————
APairwise summation of numbers————
IPairwise summation of numbers, locality————
IPairwise summation of numbers, scalability————
AParallel prefix scan algorithm using pairwise summation————
AUniform norm of a vector: Real version, serial-parallel variant————
IUniform norm of a vector, locality————
ADot product————
IDot product, locality————
IDot product, scalability————
AThe serial-parallel summation method————
IThe serial-parallel summation method, locality————
IThe serial-parallel summation method, scalability————
Matrix-vector operations————
Multiplying a nonsingular matrix by a vector————
ADense matrix-vector multiplication————
IDense matrix-vector multiplication, locality————
IDense matrix-vector multiplication, scalability————
Multiplying a matrix of special form by a vector————
Fourier transform————
Fast Fourier transform for composite dimension————
Fast Fourier transform for composite dimension with small prime divisors (2,3,5,7)————
MFast Fourier transform for powers-of-two————
Fast Fourier transform for even powers-of-two————
ACooley–Tukey Fast Fourier Transform, radix-2 case————
ICooley-Tukey, locality————
ICooley-Tukey, scalability————
Fast Fourier transform for prime dimension————
Matrix operations————
PDense matrix multiplication————
Strassen's algorithm————
ACooley–Tukey Fast Fourier Transform, radix-2 case————
ICooley-Tukey, locality————
ICooley-Tukey, scalability————
ADense matrix multiplication (serial version for real matrices)————
IDense matrix multiplication, locality————
IDense matrix multiplication, scalability————
Matrix decompositions————
Available triangular decompositions for matrices of special form————
Unitary non-similarity reductions to compact forms————
Unitary reduction to bidiagonal form————
Givens (rotations) reduction of a matrix to bidiagonal form————
AHouseholder (reflections) reduction of a matrix to bidiagonal form————
IHouseholder (reflections) reduction of a matrix to bidiagonal form, locality————
IHouseholder (reflections) reduction of a matrix to bidiagonal form, SCALAPACK————
Singular value decomposition————
PSingular value decomposition (finding singular values and singular vectors)————
Methods for calculating singular values of bidiagonal matrices————
The dqds algorithm for calculating singular values of bidiagonal matrices————
AOne step of the dqds algorithm————
IOne step of the dqds, LAPACK————
QR algorithm as applied to singular value decomposition алгоритм————
MJacobi (rotations) method for finding singular values————
Serial Jacobi (rotations) method for finding singular values————
Jacobi method with a special choice of rotations for finding singular values————
PMatrix decomposition problem————
PTriangular decompositions————
MGaussian elimination (finding the LU decomposition)————
MLU decomposition using Gaussian elimination without pivoting————
MGaussian elimination, compact scheme for tridiagonal matrices and its modifications————
Compact scheme for Gaussian elimination: Dense matrix————
MCompact scheme for Gaussian elimination and its modifications: Tridiagonal matrix————
MSerial-parallel algorithm for the LU decomposition of a tridiagonal matrix————
AGaussian elimination, compact scheme for tridiagonal matrices, serial version————
AStone doubling algorithm for the LU decomposition of a tridiagonal matrix————
ALU decomposition via Gaussian elimination————
ILU decomposition via Gaussian elimination, locality————
ILU decomposition via Gaussian elimination, scalability————
MLU decomposition using Gaussian elimination with pivoting————
AGaussian elimination with column pivoting————
AGaussian elimination with row pivoting————
AGaussian elimination with diagonal pivoting————
AGaussian elimination with complete pivoting————
MCholesky method————
ACholesky decomposition————
ICholesky decomposition, locality————
ICholesky decomposition, SCALAPACK————
ICholesky decomposition, scalability————
PUnitary-triangular factorizations————
PQR decomposition of dense nonsingular matrices————
MGivens (rotations) method for the QR decomposition of a matrix————
AGivens method————
IGivens method, locality————
MHouseholder (reflections) method for the QR decomposition of a matrix————
AHouseholder (reflections) method for the QR decomposition of a square matrix, real point-wise version————
IHouseholder (reflections) method for the QR decomposition, locality————
IHouseholder (reflections) method for the QR decomposition, SCALAPACK————
MOrthogonalization method————
AClassical orthogonalization method————
AOrthogonalization method with reorthogonalization————
MTriangular decomposition of a Gram matrix————
PQR decomposition methods for dense Hessenberg matrices————
MGivens (rotations) method for the QR decomposition of a (real) Hessenberg matrix————
MHouseholder (reflections) method for the QR decomposition of a (real) Hessenberg matrix————
PReducing matrices to compact forms————
PUnitary reductions to Hessenberg form————
Givens (rotations) method for reducing a matrix to Hessenberg form————
Classical point-wise Givens (rotations) method for reducing a matrix to Hessenberg form————
MHouseholder (reflections) method for reducing of a matrix to Hessenberg form————
AClassical point-wise Householder (reflections) method for reducing a matrix to Hessenberg form————
PUnitary reductions to tridiagonal form————
Householder (reflections) method for reducing to tridiagonal form————
AHouseholder (reflections) method for reducing a symmetric matrix to tridiagonal form————
IHouseholder (reflections) method for reducing a symmetric matrix to tridiagonal form, locality————
IHouseholder (reflections) method for reducing a symmetric matrix to tridiagonal form, SCALAPACK————
AHouseholder (reflections) method for reducing a complex Hermitian matrix to symmetric tridiagonal form————
Givens (rotations) reduction to tridiagonal form————
PEigenvalue decomposition (finding eigenvalues and eigenvectors)————
Lanczos algorithm————
ALanczos algorithm in exact algorithm (without reorthogonalization)————
ILanczos, MPI, OpenMP————
ILanczos, C++, MPI————
ILanczos, C++, MPI, 2————
ILanczos, C, MPI————
ILanczos, C++, MPI, 3————
MQR algorithm————
AQR algorithm as implemented in SCALAPACK————
AClassical point-wise Householder (reflections) method for reducing a matrix to Hessenberg form————
AHessenberg QR algorithm as implemented in SCALAPACK————
ASymmetric QR algorithm as implemented in SCALAPACK————
Symmetric tridiagonal QR algorithm as implemented in SCALAPACK————
AHouseholder (reflections) method for reducing a symmetric matrix to tridiagonal form————
IHouseholder (reflections) method for reducing a symmetric matrix to tridiagonal form, locality————
IHouseholder (reflections) method for reducing a symmetric matrix to tridiagonal form, SCALAPACK————
AQR algorithm for complex Hermitian matrices as implemented in SCALAPACK————
Symmetric tridiagonal QR algorithm as implemented in SCALAPACK————
AHouseholder (reflections) method for reducing a complex Hermitian matrix to symmetric tridiagonal form————
MThe Jacobi (rotations) method for solving the symmetric eigenvalue problem————
AThe classical Jacobi (rotations) method with pivoting for symmetric matrices————
ASerial Jacobi (rotations) method for symmetric matrices————
ASerial Jacobi (rotations) method with thresholds for symmetric matrices————
Solving systems of linear algebraic equations————
Direct methods————
Matrices of a special form————
Triangular matrices————
Bidiagonal matrices————
Forward and backward substitution for bidiagonal matrices————
Serial-parallel variant of the backward substitution————
AStone doubling algorithm for solving bidiagonal SLAEs————
AForward substitution————
ABackward substitution————
IBackward substitution, locality————
IBackward substitution, scalability————
Methods for solving block triangular matrices————
Block forward substitution (real version)————
Block backward substitution (real version)————
Methods for solving block bidiagonal matrices————
Forward and backward substitution for block bidiagonal matrices————
Stone doubling algorithm for solving block bidiagonal matrices————
Serial-parallel variant of the block backward substitution for solving block bidiagonal matrices————
Methods for solving block tridiagonal matrices————
Methods based on the conventional LU decomposition————
Serial-parallel method for solving block systems of linear algebraic equations based on the LU decomposition and backward substitutions————
ABlock Thomas algorithm————
Other methods————
Block cyclic reduction————
Block bordering method————
ATwo-sided Thomas algorithm, block variant————
PMethods for solving tridiagonal SLAEs————
Methods based on the conventional LU decomposition————
MThomas algorithm————
AThomas algorithm, pointwise version————
IThomas, locality————
ARepeated Thomas algorithm, pointwise version————
IRepeated Thomas, locality————
MStone doubling algorithm————
AStone doubling algorithm for the LU decomposition of a tridiagonal matrix————
AStone doubling algorithm for solving bidiagonal SLAEs————
MSerial-parallel method for solving tridiagonal matrices based on the LU decomposition and backward substitutions————
Other methods————
Reduction method————
Complete reduction method————
Reduction method repeated for a new right-hand side————
Two-sided Thomas algorithm————
ATwo-sided Thomas algorithm, pointwise version————
ITwo-sided Thomas, locality————
ARepeated two-sided Thomas algorithm, pointwise version————
IRepeated two-sided Thomas, locality————
Cyclic reduction————
Cyclic reduction repeated for a new right-hand side————
AComplete cyclic reduction————
IComplete cyclic reduction, locality————
IComplete cyclic reduction, scalability————
Bordering method————
Solving systems of linear algebraic equations with coefficient matrices of special form whose inverses are known————
ALinpack benchmark————
ILinpack, locality————
ILinpack, HPL————
Iterative methods for solving systems of linear algebraic equations————
AHigh Performance Conjugate Gradient (HPCG) benchmark————
IHPCG, locality————
IHPCG, scalability————
ABiconjugate gradient stabilized method (BiCGStab)————
IBiCGStab, MIT————
IBiCGStab, HYPRE————
IBiCGStab, NVIDIA AmgX————
AKaczmarz's algorithm————
IKaczmarz's, MATLAB1————
IKaczmarz's, MATLAB2————
IKaczmarz's, MATLAB3————
Solving eigenvalue problems————
Partial eigenvalue problem————
Method of bisection————
PEigenvalue decomposition (finding eigenvalues and eigenvectors)————
Lanczos algorithm————
ALanczos algorithm in exact algorithm (without reorthogonalization)————
ILanczos, MPI, OpenMP————
ILanczos, C++, MPI————
ILanczos, C++, MPI, 2————
ILanczos, C, MPI————
ILanczos, C++, MPI, 3————
MQR algorithm————
AQR algorithm as implemented in SCALAPACK————
AClassical point-wise Householder (reflections) method for reducing a matrix to Hessenberg form————
AHessenberg QR algorithm as implemented in SCALAPACK————
ASymmetric QR algorithm as implemented in SCALAPACK————
Symmetric tridiagonal QR algorithm as implemented in SCALAPACK————
AHouseholder (reflections) method for reducing a symmetric matrix to tridiagonal form————
IHouseholder (reflections) method for reducing a symmetric matrix to tridiagonal form, locality————
IHouseholder (reflections) method for reducing a symmetric matrix to tridiagonal form, SCALAPACK————
AQR algorithm for complex Hermitian matrices as implemented in SCALAPACK————
Symmetric tridiagonal QR algorithm as implemented in SCALAPACK————
AHouseholder (reflections) method for reducing a complex Hermitian matrix to symmetric tridiagonal form————
MThe Jacobi (rotations) method for solving the symmetric eigenvalue problem————
AThe classical Jacobi (rotations) method with pivoting for symmetric matrices————
ASerial Jacobi (rotations) method for symmetric matrices————
ASerial Jacobi (rotations) method with thresholds for symmetric matrices————
PSingular value decomposition (finding singular values and singular vectors)————
Methods for calculating singular values of bidiagonal matrices————
The dqds algorithm for calculating singular values of bidiagonal matrices————
AOne step of the dqds algorithm————
IOne step of the dqds, LAPACK————
QR algorithm as applied to singular value decomposition алгоритм————
MJacobi (rotations) method for finding singular values————
Serial Jacobi (rotations) method for finding singular values————
Jacobi method with a special choice of rotations for finding singular values————
Algebra of polynomials————
AHorners method————
IHorners, locality————
Algorithms on lists and arraysGPU*MPP*SMP*—
Search algorithms————
Linear search————
ABinary search: Finding the position of a target value within a sorted array————
IBinary search, locality————
IBinary search, С————
IBinary search, C++————
IBinary search, Java————
IBinary search, .NET Framework 2.0————
IBinary search, Python————
Sorting algorithms————
Binary tree sort————
Bubble sort————
Merge sort (serial and parallel variants)————
Graph algorithmsGPU*MPP*SMP*—
Graph traversalGPU*MPP*SMP*—
ABreadth-first search (BFS)GPUMPPSMP—
IBFS, MPI, Graph500————
IBFS, RCC for CPU————
IBFS, RCC for GPU————
IBFS, C++, Boost Graph Library————
IBFS, C++, MPI, Boost Graph Library————
IBFS, GAP————
IBFS, Java, WebGraph————
IBFS, Ligra————
IBFS, Python, NetworkX————
IBFS, Python/C++, NetworKit————
IBFS, VGL————
ADepth-first search (DFS)————
IDFS, C++, Boost Graph Library————
IDFS, C++, MPI, Parallel Boost Graph Library————
IDFS, Python, NetworkX————
Betweenness centrality algorithm————
PSingle Source Shortest Path (SSSP)GPU*MPP*SMP*—
ABreadth-first search (BFS)GPUMPPSMP—
IBFS, MPI, Graph500————
IBFS, RCC for CPU————
IBFS, RCC for GPU————
IBFS, C++, Boost Graph Library————
IBFS, C++, MPI, Boost Graph Library————
IBFS, GAP————
IBFS, Java, WebGraph————
IBFS, Ligra————
IBFS, Python, NetworkX————
IBFS, Python/C++, NetworKit————
IBFS, VGL————
ADijkstra's algorithm————
IDijkstra, C++, Boost Graph Library————
IDijkstra, C++, MPI: Parallel Boost Graph Library, 1————
IDijkstra, C++, MPI: Parallel Boost Graph Library, 2————
IDijkstra, Python————
IDijkstra, Python/C++————
IDijkstra, locality————
IDijkstra, Google————
IDijkstra, VGL, push————
IDijkstra, VGL, pull————
ABellman-Ford algorithm————
IBellman-Ford, C++, Boost Graph Library————
IBellman-Ford, Python, NetworkX————
IBellman-Ford, Java, JGraphT————
IBellman-Ford, OpenMP, Stinger————
IBellman-Ford, Nvidia nvGraph————
IBellman-Ford, MPI, Graph500————
IBellman-Ford, Ligra————
IBellman-Ford, locality————
IBellman-Ford, scalability————
AΔ-stepping algorithm————
IΔ-stepping, C++, MPI, Parallel Boost Graph Library————
IΔ-stepping, Gap————
PAll Pairs Shortest Path (APSP)————
AJohnson's algorithm————
IJohnson's, C++, Boost Graph Library————
AFloyd-Warshall algorithm————
IFloyd-Warshall, C++, Boost Graph Library————
IFloyd-Warshall, Python, NetworkX————
IFloyd-Warshall, Java, JGraphT————
IFloyd-Warshall, scalability————
PTransitive closure of a directed graph————
APurdom's algorithm————
IPurdom's, Boost Graph Library————
PConstruction of the minimum spanning tree (MST)————
ABoruvka's algorithm————
IBoruvka's, C++, MPI, Parallel Boost Graph Library————
IBoruvka's, RCC for CPU————
IBoruvka's, RCC for GPU————
IBoruvka's, scalability————
IBoruvka's, locality————
AKruskal's algorithm————
IKruskal's, C++, Boost Graph Library————
IKruskal's, C++, MPI, Parallel Boost Graph Library————
IKruskal's, Python, NetworkX————
IKruskal's, Java, JGraphT————
APrim's algorithm————
IPrim's, C++, Boost Graph Library————
IPrim's, Java, JGraphT————
AGHS algorithm————
PSearch for isomorphic subgraphs————
AUllman's algorithm————
IUllman's, C++, Chemical Descriptors Library————
IUllman's, C++, VF Library————
AVF2 algorithm————
IVF2, C++, VF Library————
IVF2, C++, Boost Graph Library————
IVF2, Python, NetworkX————
PGraph connectivity————
AShiloach-Vishkin algorithm for finding the connected components————
ADisjoint set union————
IDisjoint set union, Boost Graph Library————
IDisjoint set union, Java, JGraphT————
ATarjan's strongly connected components algorithm————
ITarjan's strongly connected components, C++, Boost Graph Library————
ITarjan's strongly connected components, Java, WebGraph————
ITarjan's strongly connected components, Java, JGraphT————
ITarjan's strongly connected components, Python, NetworkX————
ITarjan's strongly connected components, Python/C++, NetworKit————
ADCSC algorithm for finding the strongly connected components————
IDCSC for finding the strongly connected components, C++, MPI, Parallel Boost Graph Library————
ATarjan's biconnected components algorithm————
ITarjan's biconnected components, C++, Boost Graph Library————
ITarjan's biconnected components, Python, NetworkX————
ITarjan's biconnected components, Java, JGraphT————
ATarjan-Vishkin biconnected components algorithm————
ITarjan-Vishkin biconnected components, scalability————
ATarjan's algorithm for finding the bridges of a graph————
AVertex connectivity of a graph————
AGabow's edge connectivity algorithm————
PFinding maximal flow in a transportation network————
AFord–Fulkerson algorithm————
IFord–Fulkerson, C++, Boost Graph Library————
IFord–Fulkerson, Python, NetworkX————
IFord–Fulkerson, Java, JGraphT————
APreflow-Push algorithm————
IPreflow-Push, C++, Boost Graph Library————
IPreflow-Push, Python, NetworkX————
PFinding minimal-cost flow in a transportation network————
PAssignment problem————
AHungarian algorithm————
IHungarian, Java, JGraphT————
AAuction algorithm————
AHopcroft–Karp algorithm————
IHopcroft–Karp, Java, JGraphT————
ALongest shortest path————
ILongest shortest path, Java, WebGraph————
ILongest shortest path, Python/C++, NetworKit————
Computational geometry————
Finding the diameter of a point set————
Finding the convex hull of a point set————
Delaunay triangulation————
Voronoi diagram————
Point-in-polygon problem————
Convex polygon intersection————
Star-shaped polygon intersection————
Computer graphics————
Line drawing algorithms: Approximating a line segment on discrete graphical media————
Determining visible parts of a three-dimensional scene————
Ray tracing: Rendering realistic images————
Global illumination: Regarding direct illumination and reflection from other objects————
Computer analysis and modeling————
Computer benchmarks————
ALinpack benchmark————
ILinpack, locality————
ILinpack, HPL————
AHigh Performance Conjugate Gradient (HPCG) benchmark————
IHPCG, locality————
IHPCG, scalability————
Algorithms of quantum system simulation————
Algorithms of quantum computation simulation————
Quantum Fourier transform simulation————
ASingle-qubit transform of a state vector————
ISingle-qubit transform of a state vector, locality————
ISingle-qubit transform of a state vector, scalability————
ATwo-qubit transform of a state vector————
Machine learning algorithms————
Neural networks————
Pattern recognition————
Text recognition————
Speech recognition————
AFace recognition————
IFace recognition, scalability————
Game theory algorithms————
Ak-means clustering————
IK-means clustering, scalability1————
IK-means clustering, scalability2————
IK-means clustering, scalability3————
IK-means clustering, scalability4————
IK-means clustering, CrimeStat————
IK-means clustering, Julia————
IK-means clustering, Apache Mahout————
IK-means clustering, Octave————
IK-means clustering, Spark————
IK-means clustering, Weka————
IK-means clustering, Accord.NET————
IK-means clustering, OpenCV————
IK-means clustering, MLPACK————
IK-means clustering, SciPy————
IK-means clustering, scikit-learn————
IK-means clustering, R————
IK-means clustering, ELKI————
IK-means clustering, Ayasdi————
IK-means clustering, Stata————
IK-means clustering, Mathematica————
IK-means clustering, MATLAB————
IK-means clustering, SAS————
IK-means clustering, RapidMiner————
IK-means clustering, SAP HANA————
IK-means clustering, Torch————
Miscellaneous applied problems————
Optimization algorithms————
Linear programming————
Simplex algorithm————
Branch and bound method————
Genetic algorithms————
Ant colony algorithms————
Hybrid algorithms————
AStochastic dual dynamic programming (SDDP)————
ISDDP, scalability————
Solving systems of nonlinear equations————
ANewton's method for systems of nonlinear equations————
INewton's method for systems of nonlinear equations, scalability1————
INewton's method for systems of nonlinear equations, scalability2————
INewton's method for systems of nonlinear equations, scalability3————
INewton's method for systems of nonlinear equations, scalability4————
INewton's method for systems of nonlinear equations, ALIAS C++————
INewton's method for systems of nonlinear equations, Numerical Recipes————
INewton's method for systems of nonlinear equations, Sundials————
INewton's method for systems of nonlinear equations, Numerical Mathematics - NewtonLib————
INewton's method for systems of nonlinear equations, PETSc————
INewton's method for systems of nonlinear equations, parallel1————
INewton's method for systems of nonlinear equations, parallel2————
INewton's method for systems of nonlinear equations, parallel3————
Numerical quadrature————
ACubature rules————
ANumerical quadrature (cubature) rules on an interval (for a multidimensional cube)————
INumerical quadrature (cubature) rules on an interval (for a multidimensional cube), scalability————
Algorithms for solving equations of mathematical physics————
APoisson equation, solving with DFT————
IPoisson equation, solving with DFT, locality————
IPoisson equation, solving with DFT, scalability————
IPoisson equation, solving with DFT, FFTW————
IPoisson equation, solving with DFT, FFTE————
IPoisson equation, solving with DFT, P3DFFT————
IPoisson equation, solving with DFT, cuFFT————
IPoisson equation, solving with DFT, AccFFT————
IPoisson equation, solving with DFT, MKL FFT————
IPoisson equation, solving with DFT, PFFT————
PAlgorithms on Internet pages————
PRanking of web pages————
AHITS (Hyperlink Induced Topic Search)————
IHITS, VGL————
APageRank————
IPageRank, VGL————
Cryptographic algorithms————
AMeet-in-the-middle attack————
IMeet-in-the-middle attack, scalability————
IMeet-in-the-middle attack, implementation1————
IMeet-in-the-middle attack, implementation2————
IMeet-in-the-middle attack, implementation3————
Other algorithms————
Retrieved from "https://xn--80aecvaldz.xn--80ahdrnmvk.xn--p1ai/pool/Special:Pma_Tree"