6.6. УМНОЖЕНИЕ БУЛЕВЫХ МАТРИЦ

В разд. 5.9 изучалась задача умножения двух булевых матриц с элементами из замкнутого полукольца в котором сложение и умножение определяются таблицами

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

Очевидно, что обычный алгоритм умножения матриц требует шагов 1). Тем не менее известно по крайней мере два способа

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

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

Доказательство. Целые числа по модулю образуют кольцо Для умножения матриц в можно воспользоваться алгоритмом Штрассена. Пусть С — произведение матриц в их произведение как булевых матриц. Легко показать, что если то и если то Следовательно, легко получается из

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

Доказательство. Так как все арифметические операции можно проделать в для представления чисел достаточно разрядов. Умножение двух таких чисел занимает не более времени, а сложение и вычитание — не более что, разумеется, не превосходит

В гл. 7 мы обсудим алгоритм умножения чисел, для которого Учитывая этот результат, получаем такое следствие.

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

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

Пусть надо перемножить две булевы -матрицы Для простоты будем считать, что делится на Можно разбить на -подматрицы, на -подматрицы,

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

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

Заметим, что каждое произведение само является -матрицей. Если мы сможем вычислить каждое произведение за шагов, то сможем вычислить А В за шагов, ибо всего таких произведений.

Займемся вычислением произведений Каждое такое произведение можно вычислить за шагов. Для этого вычисляем для каждой строки а; матрицы Чтобы найти берем в матрице все строки с такими номерами что в на месте стоит 1. Затем складываем их, обращаясь с ними как с -мер-ными двоичными векторами.

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

Тогда

Первая строка в есть в точности третья строка в поскольку в первой строке в стоит только в третьем столбце. Вторая строка в равна сумме первой и третьей строк в поскольку во второй строке в стоит в первом и третьем столбцах, и т. д.

Вычисление адля каждой строки а матрицы занимает времени. Так как в строк, то общий объем работы при таком вычислении составляет

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

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

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

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

Вход. Две булевы -матрицы

Выход. Произведение

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

Рис. 6.6. (см. скан) Алгоритм четырех русских.

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

Теорема 6.10. Алгоритм 6.2 вычисляет за шагов.

Доказательство. Простая индукция по показывает, что в строках становится равной поразрядной булевой сумме таких строк матрицы что в двоичном представлении числа на месте справа стоит 1. Отсюда вытекает, что в строке 6 и, значит, в строке 7.

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

строке 5, очевидно, выполняется за шагов. Вычисление значения в строке 4 занимает время меньшее так что все тело цикла (строки 4, 5) занимает время Цикл повторяется раз, поэтому его сложность равна Так как то цикл в строках 3—5 занимает время

В строке 6 вычисление имеет сложность а копирование вектора сложность так что строка 6 выполняется за шагов. Так как то цикл в строках 1—6, который повторяется раз, занимает время Аналогично в строке 7 надо найти не более сумм -матриц, что дает сложность Таким образом, весь алгоритм требует шагов.

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

Теорема 6.11. Алгоритм 6.2 можно реализовать за операций с двоичными векторами.

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

Присваивания в строках 2 и 5 рис. 6.6 занимают постояннее время. Следовательно, цикл в строках 3—5 имеет сложность Поскольку в РАМ двоичный вектор представляется целым числом на вычисление в строке 6 не уходит время, так что каждую строку матрицы можно найти за фиксированное число операций над двоичными векторами и строка 6 имеет сложность Поэтому цикл в строках 1—6 занимает время такое же время тратится и на строку

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

Замечания по литературе

Алгоритм Штрассена заимствован из работы Штрассена [1969]. Виноград [1973] уменьшил число необходимых сложений до 15, что улучшило мультипликативную постоянную, но не порядок сложности (см. упр. 6.5).

Штрассен [1969] также описал методы сложности для обращения матриц, вычисления определителей и решения систем линейных уравнений в предположении, что каждая матрица, встречающаяся в процессе вычислений, невырожденна. Банч, Хопкрофт [1974] показали, что НВП-разложение можно сделать за шагов при единственном предположении, что исходная матрица невырожденна. Шёнхаге независимо показал, что обращение любой невырожденной матрицы над упорядоченным полем можно найти за шагов (упр. 6.25).

Результат о том, что умножение матриц не сложнее обращения матрицы, получен Виноградом [19706]. Алгоритм сложности для умножения булевых матриц построен Фишером, Мейером [1971], а алгоритм четырех русских — Арлазаровым, Диницем, Кронродом, Фараджевым [1970]. Валиант [1974] применил алгоритм Штрассена для распознавания бесконтекстных языков

Дополнительные сведения по теории матриц можно найти у Хоиа [1958]. Алгебраические понятия, такие, как кольцо, изложены в книге Маклейна, Биркгофа [1967]. Решение упр. 6.13 приведено Биркгофом, Барти [1970], упр. 6.16 принадлежит Хопкрофту.