Быстрое умножение матриц и смежные вопросы алгебры

Матричное умножение является одной из самых фундаментальных операций в современных вычислениях. До 1969 г. общим убеждением было, что кубический во времени классический алгоритм является оптимальным, хотя специалисты уже знали, что это не так. В 1969 г. Ф. Штрассен понизил значение 3 в показателе временно́й сложности кубического алгоритма до $2.807$, и после этого все ожидали, что очень скоро это значение понизится до своей нижней границы 2. Однако дальнейший прогресс оказался весьма затруднительным. Почти 10 лет дело не сдвигалось с мертвой точки, но затем сочетание удивительных техник, абсолютно не связанных с идеями Штрассена и гораздо более продвинутых, позволило уменьшить показатель в 1978–1981 гг. и в 1986 г. до $2.376$. В 2017 г. он все еще превышает $2.373$, но главная проблема — это проклятие рекурсии: уменьшение показателя ниже $2.7733$ требует много рекурсивных шагов, и на каждом из них размер задачи возрастает квадратично. В итоге все алгоритмы, сложность которых соответствовала таким показателям, превосходили классический алгоритм только на входных данных огромных размеров, далеко выходящих за рамки любого потенциального интереса для пользователя.
Мы приводим обзор продолжительной истории развития быстрого матричного умножения, сосредоточив свое внимание на оставшихся незамеченными реально применимых алгоритмах матричного умножения. Обсуждается их структура, используемые техники, тонкости реализации, влияние их изучения на современную теорию и практику алгебраических вычислений и перспективы для быстрого матричного умножения.
Библиография: 162 названия.