Приветствую Вас, уважаемые Читатели! Сегодня речь пойдет о непрекращающемся сражении математиков за вычислительные ресурсы современных компьютеров, а конкретно про модификацию стандартного алгоритма умножения матриц, который практически все изучают на первом курсе института.
Оказывается, что правило, которым мы все пользуемся на бумаге может быть оптимизировано, что даёт особенный прирост в отраслях науки и техники, в которых применяются совершенном монструозные матричные вычисления.
Алгоритм, который мы рассмотрим, в целом является обобщением метода Карацубы для умножения столбиком
Правоверное умножение
Давайте исследует проблему, связанную с применением условно "школьной" процедуры. Давайте умножим две квадратные матрицы и посчитаем, какое количество сложений и умножений мы получаем:
Итого имеется 8 умножений и 4 сложения. Теперь посмотрим, насколько возрастет сложность при умножении матрицы третьего порядка:
Итого получается 27 умножений и 18 сложений. Теперь, не претендуя на строгость, можно оценить сложность стандартного умножения матриц:
И тут нужно сделать некоторое отступление: технологически (обусловлено применением транзисторов) сложилось, что арифметико-логические устройства ЭВМ выполняют сложение намного быстрее, чем умножение.
Для примера вот стандартный сумматор:
А вот схема умножителя всего лишь 4-разрядных целых чисел:
Не акцентируя внимание на современной применимости данных схем, напрашивается вывод, что умножение требует значительно большее количество более элементарных операций, таких как сложение и сдвиг разряда.
Ремарка: понятно, что не все умножения "одинаково полезны". Например, умножение на 2 можно реализовать только лишь сдвигом разряда (000110)*2 = 001100 (6^2 = 12)
Поэтому основные усилия математиков всего мира (я не преувеличиваю) направлены, в т.ч., на поиск алгоритма, который уменьшил бы количество умножений. Первая ласточка грядущей революции явилась миру в 1969 году.
Алгоритм Штрассена
В 1969 немецкий математик Фолькер Штрассен в статье о неоптимальности метода Гаусса (который про решение систем линейных уравнений) доказал, что для перемножения двух матриц 2 X 2 достаточно семи умножений!
Напомню, мы насчитали 8 в стандартном алгоритме
Это был первый алгоритм, который позволяет перемножать большие матрицы за время меньше, чем O(n^3), т.е. используя, например, для матрицы третьего порядка меньше, чем 3^3 умножений.
Давайте посмотрим, что же это за алгоритм. Первое, о чем нужно говорить - это о том, как алгоритм сводит все матрицы к специальному, блочному виду. Ведь было бы странно называть громким именем такой алгоритм, который применим только для квадратных матриц определенного порядка.
Например, вот так решается проблема сведения умножения квадратной матрицы на прямоугольную:
Добавление столбца из нулей позволяет нам находить правильный результат. Однако, стоит заметить, что алгоритм Штрассена работает только для матриц, порядок которых равен 2^n. Это тоже не проблема:
Таким образом, мы знаем, как свести любые матрицы к нужному нам виду. Теперь рассмотрим, как непосредственно работает быстрый алгоритм.
Вычисляются несколько вспомогательных матриц, для чего требуется только 7 умножений, а затем из них с помощью сложений формируется итоговая матрица!
Понятно, что этот алгоритм работает в глубину: каждое из умножений матриц 2х2 можно выполнять рекурсивно. Так какой же выигрыш даёт алгоритм Штрассена?
Может показаться, что это немного, но в мире высоких скоростей нет незначительных результатов! На данный момент алгоритм Штрассена повсеместно используется из-за простоты программирования и высокой эффективности умножения матриц небольшого размера.
В названии я говорил про самый быстрый "практический" алгоритм умножения. Действительно, есть модификации: например, в алгоритме Винограда-Штрассена при неизменном числе умножений, сложений на три меньше.
Кроме того, для матриц астрономически большого размера (это значит, что они не поместятся в памяти ни одного из существующих компьютеров) существует алгоритм Копперсмита-Винограда с параметром 2,376.
На данный момент гипотетическая нижняя граница вычислительной сложности умножения матриц равняется n^(2+ε), где ε - сколь угодно малое число. Это утверждение известно как гипотеза Штрассена. Спасибо за внимание!