Код с комментариями

10.02.2022

Многопоточность • Блочные матрицы • Сравнение алгоритмов

Рассмотрим модификацию алгоритма Штрассена для умножения квадратных матриц с меньшим количеством сложений между блоками, чем в обычном алгоритме — 15 вместо 18 и таким же количеством умножений как в обычном алгоритме — 7. Будем использовать потоки Java Stream.

Рекурсивное дробление матриц на блоки при перемножении имеет смысл до определенного предела, а дальше теряет смысл, так как алгоритм Штрассена не использует кеш среды выполнения. Поэтому для малых блоков будем использовать параллельный вариант вложенных циклов, а для больших блоков параллельно будем выполнять рекурсивное дробление.

Границу между двумя алгоритмами определяем экспериментально — подстраиваем под кеш среды выполнения. Выгода алгоритма Штрассена становится заметнее на больших матрицах — отличие от алгоритма на вложенных циклах становится больше и зависит от среды выполнения. Сравним время работы двух алгоритмов.

08.02.2022

Умножение матриц в параллельных потоках

Многопоточность • Вложенные циклы • Сравнение алгоритмов

Рассмотрим алгоритм перемножения прямоугольных матриц с использованием потоков Java Stream. Возьмём оптимизированный вариант алгоритма на трёх вложенных циклах и заменим внешний цикл на поток. Сравним время работы двух алгоритмов.

Строки результирующей матрицы обрабатываем в параллельном режиме, а каждую строку заполняем слоями. За счёт параллельного использования кеша среды выполнения на многоядерных машинах время вычислений можно сократить более чем в два раза. Для проверки возьмём две прямоугольные матрицы: {L×M} и {M×N}.

16.12.2021

Поворот матрицы на 180 градусов

Транспонирование • Сравнение алгоритмов

Рассмотрим алгоритм разворота матрицы на 180 градусов. В отличие от алгоритма транспонирования, здесь в результирующей матрице строки и колонки не меняются местами, но отображаются зеркально.

Напишем метод на Java для поворота матрицы {m×n} на 180 градусов. Для примера возьмём прямоугольную матрицу {4×3}.

12.12.2021

Поворот матрицы на 90 градусов

Транспонирование • Сравнение алгоритмов

Рассмотрим алгоритм поворота матрицы на 90 градусов по часовой стрелке и против часовой стрелки. Этот алгоритм похож на транспонирование матрицы с тем отличием, что здесь для каждой точки одна из координат отображается зеркально.

Напишем метод на Java для поворота матрицы {m×n} на 90 градусов. Дополнительный параметр задаёт направление поворота: по часовой стрелке или против часовой стрелки. Для примера возьмём прямоугольную матрицу {4×3}.

09.12.2021

Оптимизация умножения матриц

Перестановки • Вложенные циклы • Сравнение алгоритмов

Рассмотрим алгоритм перемножения матриц с использованием трёх вложенных циклов. Сложность такого алгоритма по определению должна составлять O(n³), но есть особенности, связанные со средой выполнения — скорость работы алгоритма зависит от последовательности, в которой выполняются циклы.

Сравним различные варианты перестановок вложенных циклов и время выполнения алгоритмов. Возьмём две матрицы: {L×M} и {M×N} → три цикла → шесть перестановок: LMN, LNM, MLN, MNL, NLM, NML.

Быстрее других отрабатывают те алгоритмы, которые пишут данные в результирующую матрицу построчно слоями: LMN и MLN, — разница в процентах к другим алгоритмам значительная и зависит от среды выполнения.