где

А3В3 (с + d) е се + de /. . . Л

+ • • • {+)

А4В4 d-(f-e) df - de /. . . Л

{- + )

Итак, мы израсходовали четыре умножения на вычисление матриц s и f - пока что никакой экономии по сравнению с очевидным порядком действий. Однако по ходу дела мы вычислили произведения, которые нам ещё пригодятся.

Каждое из восьми слагаемых, встречающихся в правой части равенств (31.10)-(31.13) будем называть существенным. Уже вычисленные две матрицы sat содержат 4 существенных члена ад, bh, се и df. Остаётся вычислить гни; они включают в себя 4 существенных слагаемых ае, bf, eg и dh, которые соответствуют диагональным позициям (4 X 4)-матрицы), сделав не более трёх умножений. Тем самым одно умножение должно охватывать два существенных слагаемых. Попробуем так:

Р5 = А5В5

= (a + d) (e + h) = ае + ah + de + dh

/+ • • +\ {++)

Помимо двух нужных нам слагаемых ае и dh имеются два лишних: ah и de. Уничтожим их с помощью Р4 и Р2, при этом появятся два

Рз =

и

р4 =

других:

Р5 + Р4- Р2 = ae + dh + df - bh

/+ • • Л

Использовав ещё одно произведение

Рб = А6В6

= (b-d)-{f + h) = bf + bh- df - dh

( Л

+ • +

получим

v- - •

r = P5 + P4-P2 + P6 = ае + bf

/+ • • Л + •

V

7

Итак, на три матрицы ушло 6 умножений - что же в этом хорошего? А вто что: при симметричном вычислении и мы снова используем Р$ и одно умножение сэкономим. Для сначала сместим лишние слагаемые в Р$ в другом направлении при помощи Pi и Р3:

Р5 + Pi - Р3 = ае + ад - се + dh

1+ + Л

V +J

Вычитая дополнительное произведение

Р7 = А7В7

= (а - с) (е + д) = ае + ад - се - сд

/+ • + Л

7

получаем

и = Р5 + Рг - Р3 - Р7 = eg + dh

/. . . А

+

Мы видим, что 7 матриц Р\,Р2, , Рг позволяют полностью вычислить призведение С = АВ, что завершает описание алгоритма Штрассена.

Обсуждение

На практике алгоритм Штрассена применяется редко из-за большой величины константы, содержащейся в асимптотическом выражении для времени его работы. Применение его оправдано для плотных (содержащих мало нулей) матриц достаточно большого размера (примерно от 45 X 45). Небольшие матрицы проще всего перемножать обычным способом, а для больших разреженных (содержащих много нулей) матриц существуют специальные алгоритмы, на практике работающие быстрее штрассеновского. Метод Штрассена, таким образом, представляет интерес в основном с теоретической точки зрения.

Ещё более сложные методы (рассмотрение которых выходит за рамки этой книги) позволяют перемножить две (га X га)-матрицы ещё быстрее. Наилучшая известная оценка составляет приблизительно О (га2,376). Что касается нижних оценок, то не известно ничего, кроме тривиальной оценки £7(га2) (по числиу элементов матрицы-результата), так что разрыв между нижними и верхними оценками по-прежнему велик.

Для применения алгоритма Штрассена не обязательно, чтобы элементами матриц были вещественные числа. Важно, чтобы числовая система, которой они принадлежат, являлась кольцом. Однако удаётся использовать идею Штрассена в несколько более общей ситуации; мы рассмотрим этот вопрос в следующем разделе.

Упражнения

Используя алгоритм Штрассена, выполните умножение матриц:

Модифицируйте алгоритм Штрассена, научившись перемножать с его помощью (га X га)-матрицы за время 0(ralg7) при всех значениях га, (а не только для степеней 2).

31.2-1

31.2-2