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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 55: Строка 55:
 
####### {{level|Repeated Thomas algorithm, pointwise version|Thomas algorithm repeated for a new right-hand side: Classical scheme}}
 
####### {{level|Repeated Thomas algorithm, pointwise version|Thomas algorithm repeated for a new right-hand side: Classical scheme}}
 
###### {{level|Stone doubling algorithm}}
 
###### {{level|Stone doubling algorithm}}
###### {{level|Serial-parallel method for solving triangular SLAEs based on the LU decomposition and backward substitutions}}
+
###### {{level|Serial-parallel method for solving tridiagonal SLAEs based on the LU decomposition and backward substitutions}}
 
##### Other methods  
 
##### Other methods  
 
###### {{level|Reduction method}}
 
###### {{level|Reduction method}}
Строка 64: Строка 64:
 
####### {{level|Repeated two-sided Thomas algorithm, pointwise version|Thomas algorithm repeated for a new right-hand side: 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|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 triangular SLAEs based on the LU decomposition and backward substitutions Блочный последовательно-параллельный вариант решения с LU-разложением и обратными подстановками}}
 
##### Другие методы
 
##### Другие методы
 
###### {{level|Встречная прогонка, блочный вариант}}
 
###### {{level|Встречная прогонка, блочный вариант}}

Версия 18:27, 8 апреля 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 special matrices
    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 triangular SLAEs based on the LU decomposition and backward substitutions Блочный последовательно-параллельный вариант решения с LU-разложением и обратными подстановками|Serial-parallel method for solving triangular SLAEs based on the LU decomposition and backward substitutions Блочный последовательно-параллельный вариант решения с LU-разложением и обратными подстановками]]
          2. Другие методы
            1. Уровень алгоритма Встречная прогонка, блочный вариант
            2. Блочный метод циклической редукции
            3. Блочный метод окаймления
      3. Решения СЛАУ с матрицами специального вида, имеющими известные обратные матрицы
    2. Итерационные методы решения СЛАУ
      1. Уровень алгоритма High Performance Conjugate Gradient (HPCG) benchmark
  6. Решения спектральных задач
    1. Уровень задачи Спектральное разложение (нахождение собственных значений и векторов)
      1. Уровень метода QR-алгоритм
      2. Метод Гивенса (вращений) для решения спектральной задачи у симметричных матриц
    2. Уровень задачи Сингулярное разложение (нахождение сингулярных значений и векторов)
  7. Тесты производительности компьютеров
    1. Уровень алгоритма High Performance Conjugate Gradient (HPCG) benchmark
    2. Уровень алгоритма Linpack benchmark
  8. Преобразование Фурье
    1. Уровень метода Быстрое преобразование Фурье для степеней двойки
  9. Алгебра многочленов
    1. Уровень алгоритма Схема Горнера, вещественная версия, последовательный вариант
  10. Численные методы интегрирования
    1. Уровень алгоритма Квадратурные формулы
    2. Уровень алгоритма Квадратурные (кубатурные) методы численного интегрирования по отрезку (многомерному кубу)
      1. Уровень алгоритма Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание
      2. Уровень алгоритма Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание
      3. Уровень алгоритма Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание
      4. Уровень алгоритма Квадратурные_(кубатурные)_методы_численного_интегрирования_по_отрезку_(многомерному_кубу)#Математическое описание
  11. Алгоритмы на графах
    1. Обход графа
      1. Уровень алгоритма Поиск в ширину (BFS)
      2. Уровень алгоритма Поиск в глубину (DFS)
    2. Уровень задачи Поиск кратчайшего пути от одной вершины (SSSP)
      1. Уровень алгоритма Поиск в ширину (BFS) (для невзвешенных графов)
      2. Уровень алгоритма Алгоритм Дейкстры
      3. Уровень алгоритма Алгоритм Беллмана-Форда
      4. Уровень алгоритма Алгоритм Δ-шагания
    3. Уровень задачи Поиск кратчайшего пути для всех пар вершин (APSP)
      1. Уровень алгоритма Алгоритм Джонсона
      2. Уровень алгоритма Алгоритм Флойда-Уоршелла
    4. Уровень задачи Поиск транзитивного замыкания орграфа
      1. Уровень алгоритма Алгоритм Пурдома
    5. Уровень алгоритма Определение диаметра графа
    6. Уровень задачи Построение минимального остовного дерева (MST)
      1. Уровень алгоритма Алгоритм Борувки
      2. Уровень алгоритма Алгоритм Крускала
      3. Уровень алгоритма Алгоритм Прима
      4. Уровень алгоритма Алгоритм GHS
    7. Уровень задачи Поиск изоморфных подграфов
      1. Уровень алгоритма Алгоритм Ульмана
      2. Уровень алгоритма Алгоритм VF2
    8. Уровень задачи Связность в графах
      1. Уровень алгоритма Алгоритм Шилоаха-Вишкина поиска компонент связности
      2. Уровень алгоритма Система непересекающихся множеств
      3. Уровень алгоритма Алгоритм Тарьяна поиска компонент сильной связности
      4. Уровень алгоритма Алгоритм DCSC поиска компонент сильной связности
      5. Уровень алгоритма Алгоритм Тарьяна поиска компонент двусвязности
      6. Уровень алгоритма Алгоритм Тарьяна-Вишкина поиска компонент двусвязности
      7. Уровень алгоритма Алгоритм Тарьяна поиска «мостов» в графе
      8. Уровень алгоритма Определение вершинной связности графа
      9. Уровень алгоритма Алгоритм Габова определения рёберной связности графа
    9. Уровень задачи Поиск максимального потока в транспортной сети
      1. Уровень алгоритма Алгоритм Форда-Фалкерсона
      2. Уровень алгоритма Алгоритм проталкивания предпотока
    10. Уровень задачи Поиск потока минимальной стоимости в транспортной сети
    11. Уровень задачи Задача о назначениях
      1. Уровень алгоритма Венгерский алгоритм
      2. Уровень алгоритма Алгоритм аукциона
      3. Уровень алгоритма Алгоритм Гопкрофта-Карпа
    12. Вычисление betweenness centrality
  12. Алгоритмы поиска
    1. Двоичный поиск - находит элемент в отсортированном списке, [math]O(log(n))[/math]
  13. Алгоритмы сортировки
    1. Сортировка с помощью двоичного дерева
    2. Сортировка пузырьком
    3. Сортировка слиянием (последовательный и параллельный варианты)
  14. Вычислительная геометрия
    1. Поиск диаметра множества точек
    2. Построение выпуклой оболочки набора точек
    3. Триангуляция Делоне
    4. Диаграмма Вороного
    5. Принадлежность точки многоугольнику
    6. Пересечения выпуклых многоугольников - трудоёмкость [math]O(n_1 + n_2)[/math]
    7. Пересечение звёздных многоугольников - трудоёмкость [math]O(n_1 * n_2)[/math]
  15. Компьютерная графика
    1. Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности
    2. Алгоритм определения видимых частей трёхмерной сцены
    3. Трассировка лучей - рендеринг реалистичных изображений
    4. Глобальное освещение - рассматривает прямое освещение и отражение от других объектов
  16. Криптографические алгоритмы
  17. Нейронные сети
  18. Алгоритмы оптимизации
    1. Линейное программирование
    2. Симплекс-метод
    3. Метод ветвей и границ (последовательный и параллельный варианты)
    4. Генетические алгоритмы
    5. Муравьиные алгоритмы
    6. Комбинированные алгоритмы
    7. Нахождение экстремума функции
  19. Алгоритмы теории игр
  20. Алгоритмы моделирования квантовых систем
    1. Алгоритмы моделирования квантовых вычислений
      1. Уровень алгоритма Однокубитное преобразование вектора-состояния
      2. Уровень алгоритма Двухкубитное преобразование вектора-состояния
      3. Моделирование квантового преобразования Фурье
  21. Алгоритмы решения уравнений математической физики
    1. Уровень алгоритма Уравнение Пуассона, решение дискретным преобразованием Фурье
  22. Другие алгоритмы