Классификация алгоритмов

1 Векторные операции

1. Суммирование сдваиванием
2. Равномерная норма вектора, вещественная версия, последовательно-параллельный вариант
3. Скалярное произведение векторов, вещественная версия, последовательно-параллельный вариант
4. Последовательно-параллельный метод суммирования

2 Умножение матрицы на вектор

1. Умножение плотной матрицы на вектор

3 Матричные операции

1. Умножение плотных матриц

4 Разложения матриц

4.1 Треугольные разложения

1. Метод Холецкого (нахождение симметричного треугольного разложения)

4.2 Унитарно-треугольные разложения

1. Метод Гивенса (вращений) QR-разложения матрицы
2. Метод Хаусхолдера (отражений) QR-разложения матрицы

4.3 Разложения на унитарные и хессенберговы матрицы

1. Метод Хаусхолдера (отражений) приведения матрицы к хессенберговой (двухдиагональной) форме

4.4 Разложения на унитарные и диагональные матрицы

1. Спектральное разложение (нахождение собственных значений и векторов)
2. Сингулярное разложение (нахождение сингулярных значений и векторов)

5 Решение систем линейных уравнений

1. High Performance Conjugate Gradient (HPCG) benchmark
2. Linpack benchmark
3. Метод Гаусса решения СЛАУ (прямой ход)
4. Метод Гаусса решения СЛАУ (обратный ход)

6 Тесты производительности компьютеров

1. High Performance Conjugate Gradient (HPCG) benchmark
2. Linpack benchmark

7 Преобразование Фурье

1. Быстрое преобразование Фурье для степеней двойки

8 Алгоритмы на графах

1. Алгоритм вычисления кратчайшего пути во взвешенном графе
2. Алгоритм обхода графа

9 Алгоритмы поиска

1. Двоичный поиск - находит элемент в отсортированном списке, [math]O(log(n))[/math]

10 Алгоритмы сортировки

1. Сортировка с помощью двоичного дерева
2. Сортировка пузырьком
3. Сортировка слиянием (последовательный и параллельный варианты)

11 Вычислительная геометрия

1. Поиск диаметра множества точек
2. Построение выпуклой оболочки набора точек
3. Триангуляция Делоне
4. Диаграмма Вороного
5. Принадлежность точки многоугольнику
6. Пересечения выпуклых многоугольников - трудоёмкость [math]O(n_1 + n_2)[/math]
7. Пересечение звёздных многоугольников - трудоёмкость [math]O(n_1 * n_2)[/math]

12 Компьютерная графика

1. Алгоритмы построения отрезка - алгоритмы для аппроксимации отрезка на дискретной графической поверхности
2. Алгоритм определения видимых частей трёхмерной сцены
3. Трассировка лучей - рендеринг реалистичных изображений
4. Глобальное освещение - рассматривает прямое освещение и отражение от других объектов

15 Алгоритмы оптимизации

1. Линейное программирование
2. Симплекс-метод
3. Метод ветвей и границ (последовательный и параллельный варианты)
4. Генетические алгоритмы
5. Муравьиные алгоритмы
6. Комбинированные алгоритмы
7. Нахождение экстремума функции