6.2. АЛГОРИТМ ШТРАССЕНА ДЛЯ УМНОЖЕНИЯ МАТРИЦ

Пусть две -матрицы, причем степень числа 2. По лемме 6.2 можно разбить каждую матрицу на четыре -матрицы и через них выразить произведение матриц

где

Если рассматривать как -матрицы, элементами каждой из которых служат -матрицы, то их произведение можно выразить через суммы и произведения -матриц (формулы (6.1)). Допустим, что вычисляются с помощью умножений и а сложений (или вычитаний) -матриц. Рекурсивно применяя этот алгоритм, можно вычислить произведение двух -матриц за время удовлетворяющее неравенству

если степень числа 2. Первое слагаемое в правой части неравенства (6.2) — это сложность умножения пар -матриц, а второе — сложность выполнения а сложений при условии, что каждое сложение или вычитание двух -матриц требует времени. Рассуждения, аналогичные проведенным в теореме 2.1 для показывают, что при решение неравенства (6.2) ограничено сверху величиной где некоторая постоянная. Вид этого решения не зависит от а, т. е. от числа сложений. Таким образом, если то мы получаем метод, асимптотически лучший обычного метода сложности

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

Лемма 6.4. Произведение двух -матриц с элементами из произвольного кольца можно вычислить, выполнив 7 умножений и 18 сложений (вычитаний).

Доказательство. Чтобы вычислить произведение матриц

сначала вычислим произведения

Затем вычисляем по формулам

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

В упр. 6.5 приведен способ вычисления произведения двух матриц за 7 умножений и 15 сложений.

Теорема 6.1. Две -матрицы с элементами из произвольного кольца можно перемножить за арифметических операций.

Доказательство. Сначала рассмотрим случай Пусть число арифметических операций, необходимых для умножения двух -матриц. По лемме 6.4

Следовательно, в силу простой модификации теоремы составляет или

Если не является степенью числа 2, то каждую матрицу вложим в матрицу, порядок которой равен наименьшей степени числа 2, большей Это увеличит порядок матриц не более чем вдвое и, значит, постоянную увеличит не более чем в 7 раз. Таким образом, есть для всех

В теореме 6.1 нас интересовал только порядок роста функции Но для того, чтобы выяснить, для каких значений алгоритм Штрассена работает быстрее обычного алгоритма, надо найти соответствующую мультипликативную постоянную. Однако если не является степенью числа 2, то простое вложение каждой исходной матрицы в матрицу, порядок которой равен степени числа 2, ближайшей к сверху, даст слишком большую постоянную. Вместо этого можно вложить каждую матрицу в матрицу порядка для некоторого небольшого числа раз применить лемму 6.4, умножая -матрицы обычным -методом. Или, действуя иначе, можно было бы написать более общий рекурсивный алгоритм, который при четном расщеплял бы каждую матрицу на четыре подматрицы, как и раньше, а при нечетном сначала увеличивал бы порядок матриц на 1.

Следует подчеркнуть, что, вычислив мультипликативную постоянную, мы найдем границу только на число арифметических операций. Чтобы сравнить метод Штрассена с обычным методом умножения матриц, надо также учесть дополнительную сложность процедур, связанных с поиском элементов матриц.