Algorithm classification: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][выверенная версия]
м (Откат правок AntonChupin (обсуждение) к версии ASA)
 
(не показаны 24 промежуточные версии 3 участников)
Строка 1: Строка 1:
# <div id="Векторные операции">'''Vector operations'''</div>
+
# <div id="Vector operations">'''Vector operations'''</div>
 
## ''Pairwise summation''
 
## ''Pairwise summation''
 
### {{level|Summing an array by pairwise summation}}
 
### {{level|Summing an array by pairwise summation}}
Строка 6: Строка 6:
 
## {{level|Dot product: Real version, serial-parallel variant}}
 
## {{level|Dot product: Real version, serial-parallel variant}}
 
## {{level|Serial-parallel summation method}}
 
## {{level|Serial-parallel summation method}}
# <div id="Матрично-векторные операции">'''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'''</div>
+
# <div id="Matrix operations">'''Matrix operations'''</div>
 
## {{level|Dense matrix multiplication}}
 
## {{level|Dense matrix multiplication}}
# <div id="Разложения матриц">'''Matrix factorizations'''</div>
+
# <div id="Matrix decompositions">'''Matrix decompositions'''</div>
 
## ''Triangular decompositions''
 
## ''Triangular decompositions''
 
### Gaussian elimination (finding the LU decomposition)
 
### Gaussian elimination (finding the LU decomposition)
Строка 24: Строка 24:
 
##### Gaussian elimination with column pivoting  
 
##### Gaussian elimination with column pivoting  
 
##### Gaussian elimination with row pivoting  
 
##### Gaussian elimination with row pivoting  
##### Метод Гаусса с выбором ведущего элемента по главной диагонали
+
##### Gaussian elimination with diagonal pivoting
##### Метод Гаусса с выбором ведущего элемента по всей матрице
+
##### Gaussian elimination with complete pivoting
### {{level|Метод Холецкого (нахождение симметричного треугольного разложения)}}
+
### {{level|Cholesky method (finding the symmetric triangular decomposition)}}
#### {{level|Разложение Холецкого (метод квадратного корня)}} базовый точечный вещественный вариант для плотной симметричной положительно-определённой матрицы
+
#### {{level|Cholesky decomposition (square root method)}}: Basic pointwise real variant, dense symmetric positive definite matrix
### {{level|Известные треугольные разложения для матриц специального вида}}
+
### {{level|Available triangular decompositions for matrices of special form}}
## ''Унитарно-треугольные разложения''
+
## ''Unitary-triangular decompositions''
### {{level|Метод Гивенса (вращений) QR-разложения матрицы}}
+
### {{level|Givens method (rotation method) for the QR-decomposition of a matrix}}
### {{level|Метод Хаусхолдера (отражений) QR-разложения матрицы}}
+
### {{level|Householder method (reflection method) for the QR-decomposition of a matrix}}
## ''Разложения на унитарные и хессенберговы матрицы''
+
## ''Unitary Hessenberg decompositions''
### {{level|Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (двухдиагональной) форме}}
+
### {{level|Householder method (reflection method) for reducing a matrix to Hessenberg (bidiagonal) form}}
### {{level|Метод Гивенса (вращений) приведения матрицы к хессенберговой (двухдиагональной) форме}}
+
### {{level|Givens method (rotation method) for reducing a matrix to Hessenberg (bidiagonal) form}}
## ''Разложения на унитарные и диагональные матрицы''
+
## ''Unitary-diagonal decompositions''
### {{level|Спектральное разложение (нахождение собственных значений и векторов)}}
+
### {{level|Eigenvalue decomposition (finding eigenvalues and eigenvectors)}}
### {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}}
+
### {{level|Singular value decomposition (finding singular values and singular vectors)}}
# <div id="Решение систем линейных уравнений">'''Решение систем линейных уравнений'''</div>
+
# <div id="Solving systems of linear algebraic equations (SLAEs)">'''Solving systems of linear algebraic equations (SLAEs)'''</div>
## Прямые методы решения СЛАУ
+
## Direct methods for solving SLAEs
 
### {{level|Linpack benchmark}}
 
### {{level|Linpack benchmark}}
### Методы решения СЛАУ с матрицами специального вида
+
### Methods for solving SLAEs of special forms
#### Методы решения СЛАУ с треугольными матрицами
+
#### Methods for solving triangular SLAEs 
##### {{level|Прямая подстановка (вещественный вариант)|Прямая подстановка}}
+
##### {{level|Forward substitution (real version)|Forward substitution}}
##### {{level|Обратная подстановка (вещественный вариант)|Обратная подстановка}}
+
##### {{level|Backward substitution (real version)|Backward substitution}}
##### Методы решения СЛАУ с двухдиагональными матрицами
+
##### Methods for solving bidiagonal SLAEs
###### {{level|Прямая и обратная подстановка в СЛАУ с двухдиагональной матрицей}}
+
###### {{level|Forward and backward substitution for bidiagonal SLAEs}}
###### {{level|Метод сдваивания Стоуна для решения двухдиагональных СЛАУ}}
+
###### {{level|Stone doubling algorithm for solving bidiagonal SLAEs}}
###### {{level|Последовательно-параллельный вариант обратной подстановки}}
+
###### {{level|Serial-parallel variant of the backward substitution}}
#### {{level|Методы решения СЛАУ с трёхдиагональными матрицами}}
+
#### {{level|Methods for solving tridiagonal SLAEs}}
##### Методы, основанные на стандартном LU-разложении матрицы
+
##### Methods based on the conventional LU decomposition
###### {{level|Прогонка}}
+
###### {{level|Thomas algorithm}}
####### {{level|Прогонка, точечный вариант|Классическая монотонная прогонка}}
+
####### {{level|Thomas algorithm, pointwise version|Classical monotone elimination algorithm}}
####### {{level|Повторная прогонка, точечный вариант|Повторная прогонка для новой правой части, классическая схема}}
+
####### {{level|Repeated Thomas algorithm, pointwise version|Thomas algorithm repeated for a new right-hand side: Classical scheme}}
###### {{level|Метод сдваивания Стоуна}}
+
###### {{level|Stone doubling algorithm}}
###### {{level|Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками}}
+
###### {{level|Serial-parallel method for solving tridiagonal SLAEs based on the LU decomposition and backward substitutions}}
##### Другие методы
+
##### Other methods
###### {{level|Метод редукции}}
+
###### {{level|Reduction method}}
####### {{level|Полный метод редукции}}
+
####### {{level|Complete reduction method}}
####### {{level|Повторный метод редукции для новой правой части}}
+
####### {{level|Reduction method repeated for a new right-hand side}}
###### Встречная прогонка
+
###### Two-sided Thomas algorithm
####### {{level|Встречная прогонка, точечный вариант|Классическая встречная прогонка}}
+
####### {{level|Two-sided Thomas algorithm, pointwise version|Classical two-sided scheme}}
####### {{level|Повторная встречная прогонка, точечный вариант|Повторная прогонка для новой правой части, встречная схема}}
+
####### {{level|Repeated two-sided Thomas algorithm, pointwise version|Thomas algorithm repeated for a new right-hand side: Two-sided scheme }}
###### {{level|Метод циклической редукции}}
+
###### {{level|Cyclic reduction}}
####### {{level|Полный метод циклической редукции}}
+
####### {{level|Complete cyclic reduction}}
####### {{level|Повторный метод циклической редукции для новой правой части}}
+
####### {{level|Cyclic reduction repeated for a new right-hand side}}
###### {{level|Метод окаймления}}
+
###### {{level|Bordering method}}
#### Методы решения СЛАУ с блочно-треугольными матрицами
+
#### Methods for solving block triangular SLAEs
##### {{level|Блочная прямая подстановка (вещественный вариант)|Блочная прямая подстановка}}
+
##### {{level|Block forward substitution (real version)|Block forward substitution}}
##### {{level|Блочная обратная подстановка (вещественный вариант)|Блочная обратная подстановка}}
+
##### {{level|Block backward substitution (real version))|Block backward substitution}}
##### Методы решения СЛАУ с блочно-двухдиагональными матрицами
+
##### Methods for solving block bidiagonal SLAEs
###### {{level|Прямая и обратная подстановка в СЛАУ с блочно-двухдиагональной матрицей}}
+
###### {{level|Forward and backward substitution for block bidiagonal SLAEs}}
###### {{level|Метод сдваивания Стоуна для решения блочно-двухдиагональных СЛАУ}}
+
###### {{level|Stone doubling algorithm for solving block bidiagonal SLAEs}}
###### {{level|Блочный последовательно-параллельный вариант обратной подстановки для решения блочно-двухдиагональных СЛАУ}}
+
###### {{level|Serial-parallel variant of the block backward substitution for solving block bidiagonal SLAEs}}
#### {{level|Методы решения СЛАУ с блочно-трёхдиагональными матрицами}}
+
#### {{level|Methods for solving block tridiagonal SLAEs}}
##### Методы, основанные на стандартном LU-разложении матрицы
+
##### Methods based on the conventional LU decomposition
###### {{level|Блочная прогонка}}
+
###### {{level|Block Thomas algorithm}}
###### {{level|Блочный последовательно-параллельный вариант решения с LU-разложением и обратными подстановками}}
+
###### {{level|Serial-parallel method for solving block SLAEs based on the LU decomposition and backward substitutions}}
##### Другие методы
+
##### Other methods
###### {{level|Встречная прогонка, блочный вариант}}
+
###### {{level|Two-sided Thomas algorithm, block variant}}
###### {{level|Блочный метод циклической редукции}}
+
###### {{level|Block cyclic reduction}}
###### {{level|Блочный метод окаймления}}
+
###### {{level|Block bordering method}}
### {{level|Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы}}
+
### {{level|Solving SLAEs with coefficient matrices of special form whose inverses are known}}
## Итерационные методы решения СЛАУ
+
## Iterative methods for solving SLAEs
 
### {{level|High Performance Conjugate Gradient (HPCG) benchmark}}
 
### {{level|High Performance Conjugate Gradient (HPCG) benchmark}}
# <div id="Решения спектральных задач">'''Решения спектральных задач'''</div>
+
# <div id="Solving eigenvalue problems">'''Solving eigenvalue problems'''</div>
## {{level|Спектральное разложение (нахождение собственных значений и векторов)}}
+
## {{level|Eigenvalue decomposition (finding eigenvalues and eigenvectors)}}
### {{level|QR-алгоритм}}
+
### {{level|QR algorithm}}
### {{level|Метод Гивенса (вращений) для решения спектральной задачи у симметричных матриц}}
+
### {{level|Givens method (rotation method) for solving the symmetric eigenvalue problem}}
## {{level|Сингулярное разложение (нахождение сингулярных значений и векторов)}}
+
## {{level|Singular value decomposition (finding singular values and singular vectors)}}
# <div id="Тесты производительности компьютеров">'''Тесты производительности компьютеров'''</div>
+
# <div id="Computer performance tests">'''Computer performance tests'''</div>
 
## {{level|High Performance Conjugate Gradient (HPCG) benchmark}}
 
## {{level|High Performance Conjugate Gradient (HPCG) benchmark}}
 
## {{level|Linpack benchmark}}
 
## {{level|Linpack benchmark}}
# <div id="Преобразование Фурье">'''Преобразование Фурье'''</div>
+
# <div id="Fourier transform">'''Fourier transform'''</div>
## {{level|Быстрое преобразование Фурье для степеней двойки}}
+
## {{level|Fast Fourier transform for powers of two}}
# <div id="Алгебра многочленов">'''Алгебра многочленов'''</div>
+
# <div id="Algebra of polynomials">'''Algebra of polynomials'''</div>
## {{level|Схема Горнера, вещественная версия, последовательный вариант|Схема Горнера}}
+
## {{level|Horner's rule: Real version, serial variant|Horner's rule}}
# <div id="Численные методы интегрирования">'''Численные методы интегрирования'''</div>
+
# <div id="Numerical quadrature">'''Numerical quadrature'''</div>
## {{level|Квадратурные формулы}}
+
## {{level|Cubature rules}}
## {{level|Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)}}
+
## {{level|Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)}}
### {{level|Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод прямоугольников}}
+
### [[Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Rectangle rule|Rectangle rule]]
### {{level|Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод трапеций}}
+
### [[Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Trapezoid rule|Trapezoid rule]]
### {{level|Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод парабол (метод Симпсона)}}
+
### [[Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Simpson rule|Simpson rule]]
### {{level|Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание|Метод Гаусса}}
+
### [[Numerical quadrature (cubature) rules on an interval (for a multidimensional cube)#Gauss rule|Gauss rule]]
# <div id="Алгоритмы на графах">'''Алгоритмы на графах'''</div>
+
# <div id="Graph algorithms">'''Graph algorithms'''</div>
## Обход графа
+
## Traversing a graph
### {{level|Поиск в ширину (BFS)}}
+
### {{level|Breadth-first search (BFS)}}
### {{level|Поиск в глубину (DFS)}}
+
### {{level|Depth-first search (DFS)}}
## {{level|Поиск кратчайшего пути от одной вершины (SSSP)}}
+
## {{level|Single source shortest path (SSSP)}}
### {{level|Поиск в ширину (BFS)}} (для невзвешенных графов)
+
### {{level|Breadth-first search (BFS)}} (for unweighted graphs)
### {{level|Алгоритм Дейкстры}}
+
### {{level|Dijkstra's algorithm}}
### {{level|Алгоритм Беллмана-Форда}}
+
### {{level|Bellman-Ford algorithm}}
### {{level|Алгоритм Δ-шагания}}
+
### {{level|Δ-stepping algorithm}}
## {{level|Поиск кратчайшего пути для всех пар вершин (APSP)}}
+
## {{level|All pairs shortest path (APSP)}}
### {{level|Алгоритм Джонсона}}
+
### {{level|Johnson's algorithm}}
### {{level|Алгоритм Флойда-Уоршелла}}
+
### {{level|Floyd-Warshall algorithm}}
## {{level|Поиск транзитивного замыкания орграфа}}
+
## {{level|Transitive closure of a directed graph}}
### {{level|Алгоритм Пурдома}}
+
### {{level|Purdom's algorithm}}
## {{level|Определение диаметра графа}}
+
## {{level|Longest shortest path}}
## {{level|Построение минимального остовного дерева (MST)}}
+
## {{level|Construction of the minimum spanning tree (MST)}}
### {{level|Алгоритм Борувки}}
+
### {{level|Boruvka's akgorithm}}
### {{level|Алгоритм Крускала}}
+
### {{level|Kruskal's algorithm}}
### {{level|Алгоритм Прима}}
+
### {{level|Prim's algorithm}}
### {{level|Алгоритм GHS}}
+
### {{level|GHS algorithm}}
## {{level|Поиск изоморфных подграфов}}
+
## {{level|Search for isomorphic subgraphs}}
### {{level|Алгоритм Ульмана}}
+
### {{level|Ullman's algorithm}}
### {{level|Алгоритм VF2}}
+
### {{level|VF2 algorithm}}
## {{level|Связность в графах}}
+
## {{level|Graph connectivity}}
### {{level|Алгоритм Шилоаха-Вишкина поиска компонент связности}}
+
### {{level|Shiloach-Vishkin algorithm for finding the connected components}}
### {{level|Система непересекающихся множеств}}
+
### {{level|Disjoint set union}}
### {{level|Алгоритм Тарьяна поиска компонент сильной связности}}
+
### {{level|Tarjan's strongly connected components algorithm}}
### {{level|Алгоритм DCSC поиска компонент сильной связности}}
+
### {{level|DCSC algorithm for finding the strongly connected components}}
### {{level|Алгоритм Тарьяна поиска компонент двусвязности}}
+
### {{level|Tarjan's biconnected components algorithm}}
### {{level|Алгоритм Тарьяна-Вишкина поиска компонент двусвязности}}
+
### {{level|Tarjan-Vishkin biconnected components algorithm}}
### {{level|Алгоритм Тарьяна поиска «мостов» в графе}}
+
### {{level|Tarjan's algorithm for finding the bridges of a graph}}
### {{level|Определение вершинной связности графа}}
+
### {{level|Vertex connectivity of a graph}}
### {{level|Алгоритм Габова определения рёберной связности графа}}
+
### {{level|Gabow's edge connectivity algorithm}}
## {{level|Поиск максимального потока в транспортной сети}}
+
## {{level|Finding maximal flow in a transportation network}}
### {{level|Алгоритм Форда-Фалкерсона}}
+
### {{level|Ford–Fulkerson algorithm}}
### {{level|Алгоритм проталкивания предпотока}}
+
### {{level|Preflow-Push algorithm}}
## {{level|Поиск потока минимальной стоимости в транспортной сети}}
+
## {{level|Finding minimal-cost flow in a transportation network}}
## {{level|Задача о назначениях}}
+
## {{level|Assignment problem}}
### {{level|Венгерский алгоритм}}
+
### {{level|Hungarian algorithm}}
### {{level|Алгоритм аукциона}}
+
### {{level|Auction algorithm}}
### {{level|Алгоритм Гопкрофта-Карпа}}
+
### {{level|Hopcroft–Karp algorithm}}
## {{level|Вычисление betweenness centrality|Вычисление центральности вершин}}
+
## {{level|Betweenness centrality algorithm|Finding the betweenness centrality of vertices}}
# <div id="Алгоритмы поиска">'''Алгоритмы поиска'''</div>
+
# <div id="Search algorithms">'''Search algorithms'''</div>
## {{level|Двоичный поиск - находит элемент в отсортированном списке}}, <math>O(log(n))</math>
+
## {{level|Binary search: Finding the position of a target value within a sorted array}}, <math>O(log(n))</math>
# <div id="Алгоритмы сортировки">'''Алгоритмы сортировки'''</div>
+
# <div id="Sorting algorithms">'''Sorting algorithms'''</div>
## {{level|Сортировка с помощью двоичного дерева}}
+
## {{level|Binary tree sort}}
## {{level|Сортировка пузырьком}}
+
## {{level|Bubble sort}}
## {{level|Сортировка слиянием (последовательный и параллельный варианты)}}
+
## {{level|Merge sort (serial and parallel variants)}}
# <div id="Вычислительная геометрия">'''Вычислительная геометрия'''</div>
+
# <div id="Computational geometry">'''Computational geometry'''</div>
## {{level|Поиск диаметра множества точек}}
+
## {{level|Finding the diameter of a point set}}
## {{level|Построение выпуклой оболочки набора точек}}
+
## {{level|Finding the convex hull of a point set}}
## {{level|Триангуляция Делоне}}
+
## {{level|Delaunay triangulation}}
## {{level|Диаграмма Вороного}}
+
## {{level|Voronoi diagram}}
## {{level|Принадлежность точки многоугольнику}}
+
## {{level|Point-in-polygon problem}}
## {{level|Пересечения выпуклых многоугольников}} - трудоёмкость <math>O(n_1 + n_2)</math>
+
## {{level|Convex polygon intersection}} - complexity <math>O(n_1 + n_2)</math>
## {{level|Пересечение звёздных многоугольников}} - трудоёмкость <math>O(n_1 * n_2)</math>
+
## {{level|Star-shaped polygon intersection}} - complexity <math>O(n_1 * n_2)</math>
# <div id="Компьютерная графика">'''Компьютерная графика'''</div>
+
# <div id="Computer graphics">'''Computer graphics'''</div>
## {{level|Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности}}
+
## {{level|Line drawing algorithms: Approximating a line segment on discrete graphical media}}
## {{level|Алгоритм определения видимых частей трёхмерной сцены}}
+
## {{level|Determining visible parts of a three-dimensional scene}}
## {{level|Трассировка лучей - рендеринг реалистичных изображений}}
+
## {{level|Ray tracing: Rendering realistic images}}
## {{level|Глобальное освещение - рассматривает прямое освещение и отражение от других объектов}}
+
## {{level|Global illumination: Regarding direct illumination and reflection from other objects}}
# <div id="Криптографические алгоритмы">'''Криптографические алгоритмы'''</div>
+
# <div id="Cryptographic algorithms">'''Cryptographic algorithms'''</div>
# <div id="Нейронные сети">'''Нейронные сети'''</div>
+
# <div id="Нейронные сети">'''Neural networks'''</div>
# <div id="Алгоритмы оптимизации">'''Алгоритмы оптимизации'''</div>
+
# <div id="Optimization algorithms">'''Optimization algorithms'''</div>
## {{level|Линейное программирование}}
+
## {{level|Linear programming}}
## {{level|Симплекс-метод}}
+
## {{level|Simplex algorithm}}
## {{level|Метод ветвей и границ (последовательный и параллельный варианты)}}
+
## {{level|Branch and bound method (serial and parallel variants)}}
## {{level|Генетические алгоритмы}}
+
## {{level|Genetic algorithms}}
## {{level|Муравьиные алгоритмы}}
+
## {{level|Ant colony algorithms}}
## {{level|Комбинированные алгоритмы}}
+
## {{level|Hybrid algorithms}}
## {{level|Нахождение экстремума функции}}
+
## {{level|Finding extrema of a function}}
# <div id="Алгоритмы теории игр">'''Алгоритмы теории игр'''</div>
+
# <div id="Game theory algorithms">'''Game theory algorithms'''</div>
# <div id="Алгоритмы моделирования квантовых систем">'''Алгоритмы моделирования квантовых систем'''</div>
+
# <div id="Algorithms for quantum system simulation">'''Algorithms for quantum system simulation'''</div>
## ''Алгоритмы моделирования квантовых вычислений''
+
## ''Algorithms for quantum computation simulation''
### {{level|Однокубитное преобразование вектора-состояния}}
+
### {{level|Single-qubit transform of a state vector}}
### {{level|Двухкубитное преобразование вектора-состояния}}
+
### {{level|Two-qubit transform of a state vector}}
### {{level|Моделирование квантового преобразования Фурье}}
+
### {{level|Quantum Fourier transform simulation}}
# <div id="Алгоритмы решения уравнений математической физики">'''Алгоритмы решения уравнений математической физики'''</div>
+
# <div id="Algorithms for solving equations of mathematical physics">'''Algorithms for solving equations of mathematical physics'''</div>
## {{level|Уравнение Пуассона, решение дискретным преобразованием Фурье}}
+
## {{level|Poisson equation: Solving with DFT}}
# <div id="Другие алгоритмы">'''Другие алгоритмы'''</div>
+
# <div id="Other algorithms">'''Other algorithms'''</div>

Текущая версия на 18:23, 1 ноября 2016

  1. Vector operations
    1. Pairwise summation
      1. Summing an array by pairwise summation
      2. Finding partial sums of an array by pairwise summation
    2. Uniform norm of a vector: Real version, serial-parallel variant
    3. Dot product: Real version, serial-parallel variant
    4. Serial-parallel summation method
  2. Matrix-vector operations
    1. Dense matrix-vector multiplication
  3. Matrix operations
    1. Dense matrix multiplication
  4. Matrix decompositions
    1. Triangular decompositions
      1. Gaussian elimination (finding the LU decomposition)
        1. Gaussian elimination without pivoting
          1. LU decomposition via Gaussian elimination
          2. Compact scheme for Gaussian elimination and its modifications
            1. Compact scheme for Gaussian elimination: Dense matrix
            2. Compact scheme for Gaussian elimination and its modifications: Tridiagonal matrix
              1. Compact scheme for Gaussian elimination: Tridiagonal matrix, serial variant
              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. 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 (finding the symmetric triangular decomposition)
        1. Cholesky decomposition (square root method): Basic pointwise real variant, dense symmetric positive definite matrix
      3. Available triangular decompositions for matrices of special form
    2. Unitary-triangular decompositions
      1. Givens method (rotation method) for the QR-decomposition of a matrix
      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. Eigenvalue decomposition (finding eigenvalues and eigenvectors)
      2. Singular value decomposition (finding singular values and singular vectors)
  5. Solving systems of linear algebraic equations (SLAEs)
    1. Direct methods for solving SLAEs
      1. Уровень алгоритма Linpack benchmark
      2. Methods for solving SLAEs of special forms
        1. Methods for solving triangular SLAEs
          1. Forward substitution (real version)
          2. Backward substitution (real version)
          3. Methods for solving bidiagonal SLAEs
            1. Forward and backward substitution for bidiagonal SLAEs
            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
            3. Serial-parallel method for solving tridiagonal SLAEs 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 SLAEs
          1. Block forward substitution (real version)
          2. Block backward substitution (real version))
          3. Methods for solving block bidiagonal SLAEs
            1. Forward and backward substitution for block bidiagonal SLAEs
            2. Stone doubling algorithm for solving block bidiagonal SLAEs
            3. Serial-parallel variant of the block backward substitution for solving block bidiagonal SLAEs
        4. Methods for solving block tridiagonal SLAEs
          1. Methods based on the conventional LU decomposition
            1. Block Thomas algorithm
            2. Serial-parallel method for solving block SLAEs 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 SLAEs with coefficient matrices of special form whose inverses are known
    2. Iterative methods for solving SLAEs
      1. Уровень алгоритма High Performance Conjugate Gradient (HPCG) benchmark
  6. Solving eigenvalue problems
    1. Eigenvalue decomposition (finding eigenvalues and eigenvectors)
      1. QR algorithm
      2. Givens method (rotation method) for solving the symmetric eigenvalue problem
    2. Singular value decomposition (finding singular values and singular vectors)
  7. Computer performance tests
    1. Уровень алгоритма High Performance Conjugate Gradient (HPCG) benchmark
    2. Уровень алгоритма Linpack benchmark
  8. Fourier transform
    1. Fast Fourier transform for powers of two
  9. Algebra of polynomials
    1. Horner's rule: Real version, serial variant
  10. 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
  11. Graph algorithms
    1. Traversing a graph
      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 akgorithm
      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
  12. Search algorithms
    1. 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 for quantum system simulation
    1. Algorithms for quantum computation simulation
      1. Уровень алгоритма Single-qubit transform of a state vector
      2. Two-qubit transform of a state vector
      3. Quantum Fourier transform simulation
  21. Algorithms for solving equations of mathematical physics
    1. Poisson equation: Solving with DFT
  22. Other algorithms