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

умножения булевых матриц менее чем за O(n) шагов. Первый из них асимптотически лучше, но второй, по-видимому, практичнее для умеренных п. Опишем сейчас первый способ.

Теорема 6.9. Произведение двух булевых {пхп)-матриц можно вычислить за Од!/!-") ишгов.

Доказательство. Целые числа по модулю п+1 образуют кольцо Zn+i. Для умножения матриц А и В в Z„+i можно воспользоваться алгоритмом Штрассена. Пусть С - произведение матриц А и В в Z„+i, а D - их произведение как булевых матриц. Легко показать, что если D [t,/]=0, то CU, }]=0, и если D[i, у] = 1, то 1<С и, /Кп. Следовательно, D легко получается из С. □

Следствие 1. Если для умножения двух k-разрядных двоичных чисел требуется т битовых операций, то две булевы матрицы можно перемножить за Об (п*-"* т log п) шагов.

Доказательство. Так как все арифметические операции можно проделать в Z„+i, для представления чисел достаточно lognJ-fl разрядов. Умножение двух таких чисел занимает не более Об {т log п) времени, а сложение и вычитание - не более Об (log п), что, разумеется, не превосходит 0(m \ogn). □

В гл. 7 мы обсудим алгоритм умножения чисел, для которого m{k)=0(k\ogk \og\ogk). Учитывая этот результат, получаем такое следствие.

Следствие 2. Для умножения булевых матриц требуется не более Об (rt4ogn log logn log log logn) шагов.

Второй метод, часто называемый алгоритмом четырех русских в честь его изобретателей, в какой-то мере "практичнее" алгоритма из теоремы 6.9. Кроме того, он легко переносится на вычисления с двоичными векторами, чего нельзя сказать об алгоритме из теоремы 6.9.

Пусть надо перемножить две булевы (пХп)-матрицы А и В. Для простоты будем считать, что п делится на log п. Можно разбить Л на (пХ (log n))-подматрицы, а В - на ((log п)Хп))-подмат-

ailfikj лишь до слагаемого, равного 1. Сумма с таким слагаемым, как мы знаем, *=1

равна I. Если, например, каждый элемент а,- или bkj равен 1 с вероятностью р и эти события независимы, то среднее число слагаемых, которое надо просмотреть, не превосходит \1р, что не зависит от п.



/4g j ...

1 I 1 1

1 1 1


Рис. 6.5. Разбиение булевых матриц А и В.

рицы, как показано на рис. 6.5. Тогда

n/log п

Заметим, что каждое произведение AiBi само является (пхп)-матрицей. Если мы сможем вычислить каждое произведение A/Bi за 0(п) шагов, то сможем вычислить А В за O(n/log п) шагов, ибо всего n/log п таких произведений.

Займемся вычислением произведений AtBi. Каждое такое произведение можно вычислить за О {п log п) шагов. Для этого вычисляем aSj для каждой строки а; матрицы Ai. Чтобы найти аВ,-, берем в матрице Bi все строки с такими номерами г, что в а на k-м месте стоит 1. Затем складываем их, обращаясь с ними как с п-мер-ными двоичными векторами.

Например, пусть

"0

"0101 1 о о г

0 0 0 10 1 0 0

1 1 0 1 0 0 0 0



Тогда

"1

Первая строка в Ci есть в точности третья строка в Bt, поскольку в первой строке в Л j 1 стоит только в третьем столбце. Вторая строка в С,- равна сумме первой и третьей строк в В, поскольку во второй строке в Л г 1 стоит в первом и третьем столбцах, и т. д.

Вычисление ajBi для каждой строки a матрицы At занимает О {п log п) времени. Так как в Л г n строк, то общий объем работы при таком вычислении AiBt составляет 0(п log п).

Чтобы быстрее вычислить AtBi, заметим, что в каждой строке матрицы Ai содержится log п элементов, каждый из которых равен О или 1. Поэтому все матрицы Л t могут содержать в общей сложности не более 2°8" = п различных строк.

Таким образом, из строк матрицы В, можно составить лишь п различных сумм. Можно заранее заготовить таблицу всех возможных сумм строк матрицы Bi и вместо вычисления aBj находить в ней по &} ответ.

Этот метод тратит лишь 0{п) времени на вычисление ЛгВ{. Объясняется это так. Любое подмножество строк матрицы Bj или пусто, или состоит из одного элемента, или равно объединению одноэлементного множества и множества, меньшего исходного. Выбрав правильный порядок, можно вычислять каждую сумму строк, прибавляя одну строку матрицы В; к уже сосчитанной сумме строк. Так можно получить все п сумм строк матрицы В; за О (п) шагов. После вычисления сумм и расположения их в виде массива, можно выбирать нужную сумму для каждой из п строк матрицы At.

Алгоритм 6.2. Алгоритм четырех русских для умножения булевых матриц

Вход. Две булевы (п х /г)-матрицы Л и В. Выход. Произведение С=ЛВ.

Метод. Положим m=[ logn J. Разобьем Л на матрицы Ль Ла, . . ., Afn/mb i> li<.rn/m~\, состоит ИЗ столбцов матрицы Л с номерами от m{i-1)+1 до mi, а А[п/т\ - из оставшихся последних столбцов, к которым добавлены столбцы из нулей, если это нужно, чтобы в Л[„/т1 было т столбцов. Разобьем В на матрицы Bi, В....., Bin/m], где Bi, 1<1< [ п1т~\, состоит из строк матрицы





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