1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 54
Текст из файла (страница 54)
П гл. е. умножении матриц Следствие. Систему из л уравнений с л неизвестными можно ре. шить за 0(п'") шагов. В заключение покажем, что умножение матриц и обращение их имеют вычислительные сложности одного порядка, Теорема 6.8. Пусть для умножения двух (лусп)-матриц и обршцения (и усп)-матрицы требуется соответственно М (п) и 1(л) времени. Предположим, что 8М(т))М(2т)= 2з" М(т) при некотором е~О и аналогичные неравенства верны для 1 (л). Тогда М (л) и 1(л) совпадают с точностью до постоянного множителя. Д о к а з а т е л ь с т в о. Теорема 6.5 показывает, что 1(л)< <с,М (л) для некоторой постоянной с,.
Чтобы установить неравенство М(л)<с,/(л) для некоторой постоянной с„рассмотрим произвольные (пусп)-матрицы А и В. Так как 1 — А АВ1! О 1 — В1 О О И:1 то можно вычислить произведение АВ, обращая (Зпхйп)-матрицу, Следовательно, М (л)<1(Зл)<1(4п)<64 / (л). П 6.6. УМНОЖЕНИЕ ЕУЛЕВЫХ МАТРИЦ В равд. 5.9 изучалась задача умножения двух булевых матриц с элементами из замкнутого полукольца (О, ! ), в котором сложение и умножение определяются таблицами + О ! О ! О 1 ! ! О О О ! '! Если почти все элементы матрицы-произведения равны !, то можно перемножить две булевы матрицы в среднем за время 0(пэ), вычисляя каждую сумму Было показано, что умножение двух булевых матриц эквивалентно вычислению транзитивного замыкания графа.
К сожалению, замкнутое полукольцо (О, 1) не является кольцом, и поэтому к умножению булевых матриц неприменимы ни алгоритм Штрассена для умножения матриц, ни другие результаты, изложенные ранее в этой главе. Очевидно, что обычный алгоритм умножения матриц требует 0(п:) шагов '). Тем не менее известно по крайней мере два способа е.е. умножение нулевых млтпиц умножения булевых матриц менее чем за 0(п') шагов.
Первый из ннх асимптотически лучше, но второй, по-видимому, практичнее для умеренных и. Опишем сейчас первый способ. Теорема 6.9. Произведение двух булевых (пмп)-матриц можно вычислить за ОА(п'"') шагов. Д о к а з а т е л ь с т в о. Целые числа по модулю и-[-1 образуют кольцо Х„+ь Для умножения матриц А и В в Х„+, можно воспользоваться алгоритмом Штрассена. Пусть С вЂ” произведение матриц А и В в У„„н а 0 — их произведение как булевых матриц. Легко показать, что если 0 [1, !1=0, то С[1, !1=0, и если 0 [г, 11=1, то 1(С [1, !1(п.
Следовательно, 0 легко получается из С. Ез Следствие !. Если для умножения двух Ьразрядных двоичных чисел требуется т битовых операций, то две булевы матрицы можно перемножить за Ов(п'"' т 1ой и) шагов. Д о к а з а тел ь с т в о. Так как все арифметические операции можно проделать в Х „, для представления чисел достаточно [ 1од и )+1 разрядов. Умножение двух гаких чисел занимает не более Ое(т [онп) времени, а сложение и вычитание — не более Ое (1ой п)„что, разумеется, не превосходит Ов (т 1од и) П В гл.
7 мы обсудим алгоритм умножения чисел, для которого т(я)=0 (й 1ои й 1ой 1оя й). Учитывая этот результат, получаем такое следствие. Следствие 2. Для умножения булевых матриц требуется не более Ое (и'з г 1од и !ое! Од п !од 1од [ой и ) шагов. Второй метод, часто называемый алгоритмом четырех русских в честь его изобретателей, в какой-то мере "практичнее" алгоритма из теоремы 6.9. Кроме того, он легко переносится на вычисления с двоичными векторами, чего нельзя сказать об алгоритме из теоремы 6.9. Пусть надо перемножить две булевы (пусп)-матрицы А и В.
Для простоты будем считать, что и делится на !од и, Можно разбить А на (и к (!Оя п))-подматрицы, а  — на (([од и) ха))-подмат- л ~ллпгьзь! лишь до слагаемого, равного !. Сумма с таким слагаемым, кзк мы знаем, ь=! равна !. Если, например, каждый элемент и;ь нлн Ььу равен 1 с вероятностью р н зтн событня независимы, то среднее янсло слагаемых, которое надо просмотреть, не превосходит !4рз, что не зевнснт от л.
гл. а. имножяннв млтвнц Рис. 6Л. Раабиеаие булевых матриц Л и В. рицы, как показано на рнс. 6.5. Тогда «Лоа и АВ = ) АтВ,. г'О 0 1 1 0 1 1 1 1 1 0 0 0 0 0 1 1 О 0 0 0 0 ! 1 01011001 00010100 11010000 1УЬ Заметим, что каждое произведение А~В~ само является (ахп)- матрнцей. Если мы сможем вычислить каждое произведение А,В, за 0(п') епагов, то сможем вычислить АВ за 0(аа/1оя и) шагов, нбо всего пЛоя и таких произведений.
Займемся вычислением произведений А,Вь Каждое такое пронзведенне можно вычислить за О (аа 1оя и) шагов. Для этого вычнсляем атВ~ для каждой строки а! матрицы Аь Чтобы найти ауВо берем в матрице В~ все строки с такими номерами й, что в ау на й-м месте стоит 1. Затем складываем нх, обращаясь с ними как с п-мерными двоичными векторами. Например, пусть В.а умнОжение БулеВых матРи Тогда ! !о! !о! !о! о!о! оооо о!о! оооо !о! оооо !оо! ! !о! !оо! оооо ° !О1 оооо о!оо„ С,= А,В, Первая строка в С~ есть в точности третья строка в Вь поскольку в первой строке в А, 1 стоит только в третьем столбце.
Вторая строка в С, равна сумме первой и третьей строк в Вн поскольку во второй строке в А, 1 стоит в первом и третьем столбцах, и т. д. Вычисление а~В~ для каждой строки а! матрицы А~ занимает 0 (и 1оя п) времени. Так как в А, п строк, то общий объем работы при таком вычислении А,В~ составляет 0(п* 1оя п). Чтобы быстрее вычислить А,ВН заметим, что в каждой строке матрицы А, содержится 1од п элементов, каждый из которых равен О или 1. Поэтому все матрицы А, могут содержать в общей сложности не более 2"В" =и различных строк.
Таким образом, из строк матрицы В; можно составить лишь и различных сумм. Можно заранее заготовить таблицу всех возможных сумм строк матрицы В, и вместо вычисления ауВ, находить в ней по а> ответ. Этот метод тратит лишь 0(п') времени на вычисление А~Во Объясняется это так. Любое подмножество строк матрицы В, или пусто, или состоит из одного элемента, или равно объединению одноэлементного множества и множества, меньшего исходного. Выбрав правильный порядок, можно вычислять каждую сумму строк, прибавляя одну строку матрицы В, к уже сосчитанной сумме строк.
Так можно получить все л сумм строк матрицы В~ за 0(п') шагов. После вычисления сумм и расположения их в виде массива, можно выбирать нужную сумму для каждой из и строк матрицы Аь Алгоритм 6.2. Алгоритм четырех русских для умножения булевых матриц Вход. Две булевы (ахи) матрицы А и В. Выход. Произведение С=А В. Метод.
Положим т= ~ !Од и ). Разобьем А на матрицы Аь А„..., Аы~ ь где Аь 1(!<Гиlт ~, состоит из столбцов матрицы А с номерами от и(! — !)+! до т(, а А~„~„! — из оставшихся последних столбцов, к которым добавлены столбцы из нулей, если это нужно, чтобы в Анп |было и столбцов. Разобьем В на матрицы „„..., В!ю ь где Вь 1:!< Гп1т ), состоит из строк матрицы ГЛ б.
УМНОЖЕНИЕ МАТРИЦ Ьей!и 1, !ог ! — 1 нп!11 ~п~т ) б)о Ьей)п сопппеп! Вычисляем суммы строк Ь',", ..., Ь!" матрицы в;, 2. СУММАСТРОК[0] — [О, О, ..., 0]; 3. !ог ) — 1 цпВ! 2м — ! бо Ьей)п 4. пусть й таково, что 2" <! ( 2а+т; 5. СУММАСТРОК[!] — СУММАСТРОК[! — 2А) + Ь~,, ) епб 6. пусть С,— матрица, !Ця строка которой равна СУММАСТРОК[ЧИС(ау)], где а есть 1-я строка матрицы Аг, 1<!<и епд; Г бГм-! 7. пусть С= ~ С! г=! епд т! Здесь, коиечио, подразумевается пораарядиая булеза сумма.
Рис. 6.6. Алгоритм четырех русских. В с номерами от т(! — 1)+1 дот!', а Впи ! — из оставшихся строк, к которым добавлены строки из нулей, если зто необходимо для получения т строк. Эта ситуация, по существу, совпадает с изображенной на рис. 6.5. Вычисления приведены на рис. 6.6.
ЧИС(у) обозначает целое число, представленное двоичным вектором у, записанным в двоичной системе счисления с обратным порядком разрядов. Например, ЧИС((0, 1, 1))=6. П Теорема 6.10. Алгоритм 6.2 вычисляет С=АВ за 0(пбйояп! илггоа. До к а з а тел ь ство. Простая индукция по 1 показывает, что в строках 2 — 5 СУММАСТРОК(!) становится равной поразрядной булевой сумме таких строк Ь„матрицы Вг, что в двоичном представлении числа ) на й-м месте справа стоит 1.
Отсюда вытекает, что С!=А!В, в строке 6 и, значит, С=АВ в строке 7. Для подсчета временной сложности алгоритма сначала рассмотрим цикл, описанный строками 3 — 5. Оператор присваивания в 226 УПРАЖНЕНИЯ строке 5, очевидно, выполняется за 0(л) шагов. Вычисление значения й в строке 4 занимает время 0(т), меньшее 0(п), так что все тело цикла (строкн 4, 5) занимает время 0(п).
Цикл повторяется 2м — 1 раз, поэтому его сложность равна 0(п 2м). Так как т(!ои л, то цикл в строках 3 — 5 занимает время 0(п'). В строке б вычисление ЧИС(а/) имеет сложность 0(т), а копирование вектора СУММАСТРОК [ЧИС(ат)] — сложность 0(и), так что строка 6 выполняется заО(п ) шагов. Так как Гл/т [(2и/[од и, то цикл в строках 1 — 6, который повторяется Г п/т 1 раз, занимает время 0 (пзЛод п). Аналогично в строке 7 надо найти не более 2л/!ое л сумм (и х л)-матриц, что дает сложность 0 (иэЛод и). Таким образом, весь алгоритм требует 0(пзЛое л) шагов. П Интереснее, повидимому, то, что алгоритм 6 2 можно реализс вать за Одв(пэЛое п) вычислений с двоичными вектоРами, если в нашем распоряжении есть логические и арифметические операции над цепочками из О и 1. Теорема 6.11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
