Главная Промышленная автоматика.

Если рассматривать А и В как (2 х2)-матрицы, элементами каждой из которых служат ((п/2) Х(п/2))-матрицы, то их произведение можно выразить через суммы и произведения ((п/2) X (п/2))-матриц (формулы (6.1)). Допустим, что Ci] вычисляются с помощью т умножений и а сложений (или вычитаний) ((п/2)Х(п/2))-матриц. Рекурсивно применяя этот алгоритм, можно вычислить произведение двух (пХп)-матриц за время Т{п), удовлетворяющее неравенству

(6.2)

Т(п)<тт()-Ь-, п>2.

если п - степень числа 2. Первое слагаемое в правой части неравенства (6.2) - это сложность умножения т пар ((п/2) х (п/2))-ма-триц, а второе - сложность выполнения а сложений при условии, что каждое сложение или вычитание двух ((п/2)Х(/г/2))-матриц требует nV4 времени. Рассуждения, аналогичные проведенным в теореме 2.1 для с=2, показывают, что при /п>4 решение неравенства (6.2) ограничено сверху величиной kn°e где k - некоторая постоянная. Вид этого решения не зависит от а, т. е. от числа сложений. Таким образом, если т<8, то мы получаем метод, асимптотически лучший обычного метода сложности О(п).

Штрассен изобрел искусный метод умножения двух (2х2)-ма-триц с элементами из произвольного кольца, в котором достаточно семи умножений. Рекурсивно применяя свой метод, он смог умножить две (/гХ/г)-матрицы за время О (п°8), что по порядку примерно равно п-*".

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

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

С,2.

«32.

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

т,= (flia-aj(>,i + bj, п»-=(а„ + а (fcu + M. /ns = (aii-a2i)(i+M. /"4 = (011+012) 22.

"e = a82(i-bu).



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

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

Cu = mi + m2-mt + m,,

с21 = те + т,,

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

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

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

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

Г(«) = 7Г (-2.) + 18 для п

.>2.

Следовательно, в силу простой модификации теоремы 2.1 Т (п) составляет О (7°g «), или 0(/г°8).

Если п не является степенью числа 2, то каждую матрицу вложим в матрицу, порядок которой равен наименьшей степени числа 2, большей п. Это увеличит порядок матриц не более чем вдвое и, значит, постоянную увеличит не более чем в 7 раз. Таким образом, Т(п) есть 0(/г°8) для всех /г>1. □

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



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

6.3. ОБРАЩЕНИЕ МАТРИЦ

В данном разделе мы покажем, что задачу обращения матриц из определенного класса можно свести к задаче умножения матриц. Этот класс включает все обратимые треугольные матрицы, но не все обратимые матрицы вообще. В дальнейшем мы обобщим полученный результат на произвольные обратимые матрицы. В данном разделе и в разд. 6.4 и 6.5 рассматриваются матрицы с элементами из некоторого поля.

Лемма 6.5. Пусть матрица А разбита тш:

Предположим, что существует Л. Обозначим Аа-АгААц через Д и допустим, что Д-> существует. Тогда

All-\-All А *Л2,Л1/ ЛцЛдЛ 1

-д-м„лг/ д-

л-1 =

(6.3)

Доказательство. С помощью очевидных алгебраических преобразований можно показать, что

"•12

"•22 j

О д

/ AiiAi О /

откуда

л-1 =

21-1 21

/111 •12

Az 0 -

а д-\

/ о

-ЛЛц /

-ЛгМ.аД-!

Д-"

г1 + Л-м1,д-м,,Л1-1

-д-м,1Лг/ д- • □

Лемму 6.5 нельзя применять ко всем невырожденным матрицам. Например, (/гхп)-матрица перестановки Л, у которой А [/,/]=!, если }=п-1-Ы, и Л i, /]=0 в противном случае, невырожденна, но det(Лll)=0 для любой главной подматрицы Лц. Тем не менее лемма 6.5 применима ко всем невырожденным нижним и верхним треугольным матрицам.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 [83] 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0021