Max Home IndustryУмножение матриц вместе — фундаментальный алгоритм. Он используется во многих математических процедурах, и, найдя способ сделать это быстрее, вы сэкономите часы вычислений и уменьшите потребность в суперкомпьютерах.
Фактический алгоритм умножения двух матриц удивительно прост, но он включает в себя три вложенных цикла for, поэтому для умножения двух матриц размера n x n требуется порядка n3 умножений.
Алгоритм настолько прост, что вы можете подумать, что нет возможности для общего сокращения этого объема работы — для этого явно нужны три цикла порядка n в целом. Однако давно высказывались предположения, что умножение матриц возможно за очень почти квадратичное время. То есть вы могли бы умножить две матрицы пропорционально времени nω на ω <3. Первый такой алгоритм был изобретен в 1969 году Фолькером Штрассеном. Он нашел способ умножать матрицы 2x2, используя всего 7, а не 8 умножений - компромисс заключался в том, что вам приходилось делать больше сложений. Вы можете выполнить умножение матриц любого размера путем рекурсивного умножения блоков 2x2, и это дает начало общему алгоритму, который принимает O (nω) с ω = log27 = 2,807. Этот алгоритм не является численно стабильным, но он используется в некоторых пакетах обработки чисел для ускорения работы с матрицами большой размерности. Следующий прорыв произошел в 1990 году, когда Копперсмит и Виндоград сумели найти алгоритм, который уменьшил ω до 2,376. И на этом история останавливается, поскольку за последние 20 с лишним лет не было никаких улучшений. Теперь Вирджиния Василевска Уильямс из Калифорнийского университета в Беркли и Стэнфордском университете нашла алгоритм, который снижает ω до 2,373, что при 0,003 не является большим уменьшением, но доказывает, что даже после 20 лет отсутствия прогресса границу можно снизить. Использованный принцип заключался в применении метода Копперсмита и Виндограда более чем дважды. Об этом думали раньше, но трехкратное применение этого метода не дает никаких улучшений - вам нужно применить его восемь раз, прежде чем вы получите лучший результат. Идея, по-видимому, изначально была представлена как часть докторской диссертации Эндрю Стотерсом, но осталась незамеченной. Только после того, как Вирджиния Василевска Уильямс предоставила общую методологию и заново открыла идею, ее важность стала очевидной. Итак, к концу 2011 года мы можем утверждать, что барьер медных кузнецов и Виндограда был сломан. Насколько ниже ω может опуститься? Кто знает, но плохая новость в том, что для любой матрицы практического размера алгоритм настолько сложен, что его просто не стоит использовать. Похоже, что это действительно дошло до того, что превратилось в теоретический поиск.