Доказательство алгоритма Штрассена
Я читал об алгоритме Штрассена для умножения матриц.
Как упомянуто во введении к алгоритмам Кормена, алгоритм не является интуитивно понятным. Однако мне любопытно узнать, существует ли какое-либо строгое математическое доказательство алгоритма и что фактически вошло в разработку алгоритма.
Я пробовал поиск в Google и stackru, но все ссылки только на сравнение подхода Штрассена со стандартным подходом умножения матриц или в них подробно описывается процедура, представленная алгоритмом.
2 ответа
Вам следует перейти к исходному материалу. В данном случае оригинальная статья Штрассена:
Штрассен, Фолькер, Гауссово Исключение не является оптимальным, Нумер. Математика 13, с. 354-356, 1969
http://link.springer.com/article/10.1007%2FBF02165411?LI=true
Несмотря на то, что я не читал его сам, я бы предположил, что существует жесткое обсуждение и доказательство сложности алгоритма.
Похоже, профессор Штрассен все еще активен ( http://en.wikipedia.org/wiki/Volker_Strassen) и имеет домашнюю страницу ( http://www.math.uni-konstanz.de/~strassen/). Если, после того, как вы узнаете как можно больше об алгоритме, вам все еще будет интересно узнать больше, я не думаю, что подробное письмо профессору могло бы быть и речи.
К сожалению, в Интернете, похоже, нет бесплатной версии документа, несмотря на тот факт, что работа была завершена в государственном университете (Калифорнийский университет в Беркли) с использованием федеральных средств (грант NSF), но это совершенно отдельный вопрос, который мы не должны обсудить здесь
Если вы учитесь, вы, скорее всего, будете иметь доступ через свою школу, или, по крайней мере, ваша школа может получить вам копию без каких-либо затрат для вас. Удачи.
Доказательством того, что алгоритм Штрассена должен существовать, является простой подсчет измерений (в сочетании с доказательством того, что подсчет простых измерений дает правильный ответ). Рассмотрим векторное пространство всех билинейных отображений $C^n\times C^n \rightarrow C^n$это векторное пространство измерения $n^3$ (в случае умножения матриц мы имеем $n=m^2$например, $n=4$ для $2\times 2$ дело). Множество билинейных отображений ранга один, т. Е. Вычисляемых в алгоритме с использованием только одного скалярного умножения, имеет размерность $3(n-1)+1$ и множество билинейных карт ранга не более $r$ имеет размерность мин $r[3(n-1)]+r$ а также $n^3$ для большинства значений $n,r$ (и можно проверить, что это правильно, когда $r=7,n=4$, При этом любая билинейная карта $C^4\times C^4\rightarrow C^4$с вероятностью один имеет ранг не более $7$и всегда может быть приближен с произвольной точностью билинейной картой ранга не более $7$,