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

begin

1. for until \n/m~\ do

begin

comment Вычисляем суммы строк Ъ[*.....bJi матрицы

2. СУММАСТРОКИГО, О, .... 0];

3. for /1 until 2»>-1 do

begin

4. пусть k таково, что 2* < / < 2*+;

5. СУММАСТРОК[/] СУММАСТРОК[/ - 2*] + bi, end

6. пусть С; - матрица, /-я строка которой равна СУММА-

СТРОК[ЧИС(ау)], где а, есть /-я строка матрицы Л,-,

end;

Гл/m-l

7. пусть С= 2 Q end

) Здесь, конечно, подразумевается поразрядная булева сумма. Рис. 6.6. Алгоритм четырех русских.

В с номерами отт(1-1)+1 до mi, а Bf„/mi- из оставшихся строк, к которым добавлены строки из нулей, если это необходимо для получения т строк. Эта ситуация, по существу, совпадает с изображенной на рис. 6.5. Вычисления приведены на рис. 6.6. ЧИС(у) обозначает целое число, представленное двоичным вектором v, записанным в двоичной системе счисления с обратным порядком разрядов. Например, ЧИС([0, 1, 1])=6. □

Теорема 6.10. Алгоритм 6.2 вычисляет С=АВ за O(nVlogrt) шагов.

Доказательство. Простая индукция по / показывает, что в строках 2-5 СУММАСТРОКГ/] становится равной поразрядной булевой сумме таких строк Ь матрицы В,-, что в двоичном представлении числа / на k-м месте справа стоит 1. Отсюда вытекает, что Ci=AiBi в строке 6 и, значит, С=АВ в строке 7.

Для подсчета временной сложности алгоритма сначала рассмотрим цикл, описанный строками 3-5. Оператор присваивания в



УПРАЖНЕНИЯ

строке 5, очевидно, выполняется за О (п) шагов. Вычисление значения k в строке 4 занимает время 0{т), меньшее 0{п), так что все тело цикла (строки 4, 5) занимает время 0{п). Цикл повторяется 2""-1 раз, поэтому его сложность равна 0(п 2""). Так как m<log п, то цикл в строках 3-5 занимает время 0{п).

В строке 6 вычисление ЧИС(а;) имеет сложность 0{т), а копирование вектора СУММАСТРОК 1ЧИС(а;)] - сложность 0{п), так что строка 6 выполняется за О (п) шагов. Так как f п/т ~ <2n/log п, то цикл в строках 1-6, который повторяется f п/т ~\ раз, занимает время О (n/log п). Аналогично в строке 7 надо найти не более 2/i/Iog п сумм (/гХп)-матриц, что дает сложность 0(rtVlog п). Таким образом, весь алгоритм требует О (nVlog п) шагов. □

Интереснее, по-видимому, то, что алгоритм 6.2 можно реализсвать за Одв (nVlog п) вычислений с двоичными векторами, если в нашем распоряжении есть логические и арифметические операции над цепочками из О и 1.

Теорема 6.11. Алгоритм 6.2 можно реализовать за OB(n/]ogn) операций с двоичными векторами.

Доказательство. Для того чтобы узнавать, когда надо увеличить к, используется счетчик. Вначале значение счетчика равно 1, а /г=0. Всякий раз, когда / увеличивается, счетчик уменьшается на 1, если его значение было отлично от 1; а в последнем случае значение счетчика полагается равным новому значению /, а к увеличивается на 1.

Присваивания в строках 2и 5 рис. 6.6 занимают постояннее время. Следовательно, цикл в строках 3-5 имеет сложность Одв(/г). Поскольку в РАМ двоичный вектор представляется целым числом на вычисление ЧИС(аг) в строке 6 не уходит время, так что каждую строку матрицы Ci можно найти за фиксированное число операций над двоичными векторами и строка 6 имеет сложность Одв (л). Поэтому цикл в строках 1-6 занимает время Oдв(nVlogn); такое же время тратится и на строку 7. □

УПРАЖНЕНИЯ

6.1. Покажите, что целые числа по модулю п образуют кольцо, т. е. что Zn- кольцо ({О, 1, . . ., + , -,0, 1), где а+Ь и а-Ь - обычные сложение и умножение по модулю п.

6.2. Покажите, что (п х п)-матрицы с элементами из некоторого кольца R образуют кольцо.

) Можно обойти ту деталь, что ЧИС (а,) соответствует не самому вектору а,-, а перестановке его элементов в обратном порядке, если в качестве /-й строки матрицы В взять /-ю строку снизу, а не сверху, как мы делали раньше.



6.3. Приведите пример, показывающий, что произведение матриц некоммутативно, даже если их элементы берутся из кольца с коммутативным умножением.

6.4. Примените алгоритм Штрассена для вычисления произведения

"1 т

7 8

6.5. Еще один вариант алгоритма Штрассена использует для вычисления произведения двух (2х2)-матриц равенства

«3 = «11-021. «8=01821.

S4 = 0ia -Sa, от* = 838,,

«5=12-1> tn,=SiS,

Se = 6ga-s5, mt = Stb2t,

Sj = 622 - 12» = OaaSg.

Sg = Se-bx. Элементы произведения получаются так:

Покажите, что эти элементы равны соответствующим элементам из (6.1). Заметьте, что было сделано только 7 умножений и 15 сложений.

6.6. Докажите следующие соотношения для (/гхп)-матриц А, В и С:

(а) если АВ=1 и ЛС=/, то В=С, (б) Л-М=/, (в) {АВ)-=В-А-\ (г) (Л-1)-1=Л,

(д) det(B)=det()det(B).

6.7. Теорема 6.2 показывает, что невырожденную верхнюю треугольную матрицу можно обратить за сп арифметических операций, где с - постоянная. Найдите эту постоянную с в предположении, что матрицы умножаются по алгоритму Штрассена и n - степень числа 2.

6.8. Представим матрицу перестановки массивом Р, для которого PU]=j тогда и только тогда, когда в t-м столбце на /-й строке стоит 1. Пусть Pi и Pj-такие представления (пХл)-матриц перестановки.

(а) Докажите, что PiP2[/l=Pi[P2[i]].

(б) Постройте алгоритм, вычисляющий Pf за время 0(п).





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.0036