Изменения

Перейти к: навигация, поиск

Метод четырёх русских для умножения матриц

3371 байт добавлено, 18:07, 8 октября 2019
Нет описания правки
{{Задача|definition =Дано две квадратных матрицы <tex>A_{[n \times n]}</tex> и <tex>B_{[n \times n]}</tex>, состоящие из нулей и единиц. Нужно найти их произведение. При этом, все операции выполняются по модулю <tex>2</tex>.}}</noinclude><includeonly>{{#if: {{{neat|}}}|<div style= Постановка задачи "background-color: #fcfcfc; float:left;"><div style="background-color: #ddd;">'''Задача:'''</div><div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;">{{{definition}}}</div></div>|<table border="0" width="100%"><tr><td style="background-color: #ddd">'''Задача:'''</td></tr><tr><td style="border:1px dashed #2f6fab; padding: 8px; background-color: #fcfcfc; font-style: italic;">{{{definition}}}</td></tr></table>}}</includeonly>== Простое решение ==
Рассмотрим следующую задачу: «Дано две квадратных матрицы Если мы будем считать произведение матриц <tex>A_{[n C = A \times n]}cdot B</tex> и по определению <texdpi=130>B_\left(c_{[n i, j} = \sum\times limits_{k = 1}^n]a_{i,k}b_{k,j}\right)</tex>, Состоящие то сложность работы алгоритма составит <tex>O(n^3)</tex> {{---}} каждый из нулей и единиц. Нужно найти их произведение. При этом<tex>n^2</tex> элементов результирующей матрицы <tex>C</tex> вычисляется за время, все операции выполняются по модулю пропорциональное <tex>2n</tex>.»
Сейчас будет показано, как немного уменьшить это время. == Простое решение Сжатие матриц == Для выполнения сжатия матриц выполним следующий предподсчёт : для всех возможных пар двоичных векторов длины <tex>k</tex> подсчитаем и запомним их скалярное произведение по модулю <tex>2</tex>. Возьмём первую матрицу. разделим каждую её строку на куски размера <tex>k</tex>. Для каждого куска определим номер двоичного вектора, который соответствует числам, находящимся на этом куске. Если кусок получился неравным по длине <tex>k</tex>(последний кусок строки), то будем считать, что в конце в нём идут не влияющие на умножение нули. Получим матрицу <tex dpi=140>A'_{n \times \lceil\frac{n}{k} \rceil}</tex>. Аналогично поступим с матрицей <tex>B</tex>, вместо строк деля столбцы. Получим матрицу <tex dpi=140>B'_{\lceil\frac nk\rceil\times n}</tex>. Теперь, если вместо произведения матриц <tex>A</tex> и <tex>B</tex> считать произведение новых матриц <tex>A'</tex> и <tex>B'</tex>, воспользовавшись посчитанными скалярными произведениями, то каждый элемент матрицы <tex>C</tex> будет получаться уже за время, пропорциональное <tex>\lceil \dfrac{n}{k} \rceil</tex> вместо <tex>n</tex>, и время произведения матриц сократится с <tex>O(n^3)</tex> до <tex>O(n^2 \cdot\dfrac nk) = O(\dfrac{n^3}{k}) </tex>. == Оценка сложности алгоритма и выбор k ==[[Файл:exampleFourRussiansAlgoFinalPicture.png|500px|right]] Оценим асимптотику данного алгоритма. * Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(n^2)</tex>.* Перемножение полученных матриц {{---}} <tex>O(\dfrac{n^3}{k})</tex>. Итого: <tex>O(2^{2k}k) + O(\dfrac{n^3}{k})</tex>.Выбрав <tex>k = \log n </tex>, получаем требуемую асимптотику <tex>O(n^2 \log n) + O(\dfrac{n^3}{\log n}) = O(\dfrac{n^3}{\log n})</tex>
Если мы будем считать произведение матриц <tex>C = A \cdot B</tex> по определению(<tex dpi=140>c_{i, j} Пример работы алгоритма = \sum\limits_{k = 1}^n a_{i,k}b_{k,j}</tex>), то трудоёмкость алгоритма составит <tex>O(n^3)</tex> {{---}} каждый из <tex>n^2</tex> элементов результирующей матрицы <tex>C</tex> вычисляется за время, пропорциональное <tex>n</tex>.
Хочется Рассмотрим работу алгоритма на примере перемножения двух матриц <stex>большегоA </stex> меньшего...и <tex> B </tex>, где
<tex> A =</tex><tex>\left(\begin{array}{cccc} 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \end{array}\right)</tex>, <tex> B = Предподсчёт ==</tex><tex>\left(\begin{array}{cccc} 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array}\right)</tex>
Воспользуемся следующим {{TODO|t=ну не уместно здесь это словосочетание}} финтом ушами. Возьмём некоторое целое число <tex>k</tex>. Для всех пар двоичных векторов длины <tex>k</tex> подсчитаем их скалярное произведение по модулю <tex>= \log_2 n = \log_2 4 = 2</tex>., то предподсчитаем все скалярные произведения:
== Сжатие матриц == Для удобства каждому битовому вектору будет соответствовать двоичное число с ведущими нулями, т.е. в данном случае имеем числа <tex> 00 </tex>, <tex> 01 </tex>, <tex> 10 </tex>, <tex> 11 </tex>. Ниже приведена таблица, в которой записаны все искомые произведения:
В прошлом пункте была посчитана какая-то непонятная муть. Вот сейчас-то мы ей и воспользуемся.<tex>\begin{array}{|c|c|c|c|c|} \hline & \textbf{00} & \textbf{01} & \textbf{10} & \textbf{11} \\ \hline \textbf{00} & 0 & 0 & 0 & 0 \\ \hline \textbf{01} & 0 & 1 & 0 & 1 \\ \hline \textbf{10} & 0 & 0 & 1 & 1 \\ \hline \textbf{11} & 0 & 1 & 1 & 0\\ \hline \end{array} </tex>
Возьмём первую матрицу. разделим каждую её строку на куски размера Согласно соглашению относительно битовых векторов и двоичных чисел получим новые матрицы <tex>k</tex>. В каждый кусок запишем номер двоичного вектора, который соответствует числам, которые находятся на этом куске. Если кусок получился неравным по длине <tex>kA' </tex>(последний кусок строки), то будем считать, что в нём в конце идут не влияющие на умножение нули. Получим матрицу и <tex dpi=140>AB'_{n \times \lceil\frac{n}{k} \rceil}</tex>.:
Аналогично поступим с матрицей <tex>BA' = </tex><tex>\left(\begin{array}{cccc} 01 & 11 \\ 01 & 00 \\ 11 & 01 \\ 10 & 01 \end{array}\right)</tex>, вместо строк деля столбцы. Получим матрицу <tex dpi=140>B'_= </tex><tex>\left(\begin{array}{cccc} 10 & 00 & 01 & 11 \lceil\frac nk 10 & 01 & 10 & 01 \rceilend{array}\times n}right)</tex>.
Теперь, если вместо произведения матриц <tex>A</tex> и <tex>B</tex> считать произведение новых матриц <tex>A'</tex> и <tex>B'</tex>, воспользовавшись посчитанными скалярными произведениями, то каждый элемент Перемножим эти матрицы <tex>C</tex> будет получаться уже за время, пропорциональное <tex>\lceil \frac nk \rceil</tex> вместо <tex>n</tex>, и время произведения матриц сократится по модулю два с <tex>O(n^3)</tex> до <tex>O(n^2 \cdot\frac nk) = O(\frac{n^3}{k}) </tex>.использованием нашего предпосчета:
<tex> C =A' \times B' = Оценка трудоёмкости и выбор k ==</tex><tex>\left(\begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array}\right)</tex>
Оценим трудоёмкость данного алгоритмаМатрица <tex> C </tex> {{---}} искомая.
== Источники информации ==* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>''Gregory V.* Создание матриц <tex>ABard'' — ''Accelerating Cryptanalysis with the Method of Four Russians'</tex> и <tex>B'</tex> {{---}} <tex>O(N^2)</tex>* Перемножение полученных матриц {{---}} <tex dpi=140>O(\frac{n^3}{k})</tex>. July 22, 2006. Страница 5
Итого: <tex>O(2^{2k}k) + O(\frac{n^3}{k})</tex>.
Взяв <tex>k = \log n</tex>, получаем итоговую трудоёмкость <tex>O(n^2 \log n) + O(\frac{n^3}{\log n}) = O(\frac{n^3}{\log n})</tex>[[Категория: Дискретная математика и алгоритмы]][[Категория: Динамическое программирование]][[Категория: Способы оптимизации методов динамического программирования]]
Анонимный участник
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/5544...71846»

Навигация