http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=83.239.81.22&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-29T14:14:18ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%87%D0%B5%D1%82%D1%8B%D1%80%D1%91%D1%85_%D1%80%D1%83%D1%81%D1%81%D0%BA%D0%B8%D1%85_%D0%B4%D0%BB%D1%8F_%D1%83%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BC%D0%B0%D1%82%D1%80%D0%B8%D1%86&diff=71846Метод четырёх русских для умножения матриц2019-10-08T15:07:53Z<p>83.239.81.22: </p>
<hr />
<div>{{Задача<br />
|definition = Дано две квадратных матрицы <tex>A_{[n \times n]}</tex> и <tex>B_{[n \times n]}</tex>, <br />
состоящие из нулей и единиц. Нужно найти их произведение. При этом, все операции выполняются по модулю <tex>2</tex>.<br />
}}<br />
</noinclude><br />
<includeonly>{{#if: {{{neat|}}}|<br />
<div style="background-color: #fcfcfc; float:left;"><br />
<div style="background-color: #ddd;">'''Задача:'''</div><br />
<div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;">{{{definition}}}</div><br />
</div>|<br />
<table border="0" width="100%"><br />
<tr><td style="background-color: #ddd">'''Задача:'''</td></tr><br />
<tr><td style="border:1px dashed #2f6fab; padding: 8px; background-color: #fcfcfc; font-style: italic;">{{{definition}}}</td></tr><br />
</table>}}<br />
</includeonly><br />
== Простое решение ==<br />
<br />
Если мы будем считать произведение матриц <tex>C = A \cdot B</tex> по определению <tex dpi=130>\left(c_{i, j} = \sum\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>n</tex>.<br />
<br />
Сейчас будет показано, как немного уменьшить это время.<br />
<br />
== Сжатие матриц == <br />
<br />
Для выполнения сжатия матриц выполним следующий предподсчёт : для всех возможных пар двоичных векторов длины <tex>k</tex> подсчитаем и запомним их скалярное произведение по модулю <tex>2</tex>.<br />
<br />
Возьмём первую матрицу. разделим каждую её строку на куски размера <tex>k</tex>. Для каждого куска определим номер двоичного вектора, который соответствует числам, находящимся на этом куске. Если кусок получился неравным по длине <tex>k</tex>(последний кусок строки), то будем считать, что в конце в нём идут не влияющие на умножение нули. Получим матрицу <tex dpi=140>A'_{n \times \lceil\frac{n}{k} \rceil}</tex>.<br />
<br />
Аналогично поступим с матрицей <tex>B</tex>, вместо строк деля столбцы. Получим матрицу <tex dpi=140>B'_{\lceil\frac nk\rceil\times n}</tex>.<br />
<br />
Теперь, если вместо произведения матриц <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>.<br />
<br />
== Оценка сложности алгоритма и выбор k ==<br />
[[Файл:exampleFourRussiansAlgoFinalPicture.png|500px|right]]<br />
<br />
Оценим асимптотику данного алгоритма.<br />
<br />
* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.<br />
* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(n^2)</tex>.<br />
* Перемножение полученных матриц {{---}} <tex>O(\dfrac{n^3}{k})</tex>.<br />
<br />
Итого: <tex>O(2^{2k}k) + O(\dfrac{n^3}{k})</tex>.<br />
Выбрав <tex>k = \log n </tex>, получаем требуемую асимптотику <tex>O(n^2 \log n) + O(\dfrac{n^3}{\log n}) = O(\dfrac{n^3}{\log n})</tex><br />
<br />
== Пример работы алгоритма ==<br />
<br />
Рассмотрим работу алгоритма на примере перемножения двух матриц <tex> A </tex> и <tex> B </tex>, где <br />
<br />
<tex> A = </tex><br />
<tex><br />
\left(\begin{array}{cccc} <br />
0 & 1 & 1 & 1 \\ <br />
0 & 1 & 0 & 0 \\ <br />
1 & 1 & 0 & 1 \\ <br />
1 & 0 & 0 & 1 <br />
\end{array}\right)<br />
</tex><br />
, <tex> B = </tex><br />
<tex><br />
\left(\begin{array}{cccc} <br />
1 & 0 & 0 & 1 \\ <br />
0 & 0 & 1 & 1 \\ <br />
1 & 0 & 1 & 0 \\ <br />
0 & 1 & 0 & 1 <br />
\end{array}\right)<br />
</tex><br />
<br />
<tex> k = \log_2 n = \log_2 4 = 2</tex>, то предподсчитаем все скалярные произведения:<br />
<br />
Для удобства каждому битовому вектору будет соответствовать двоичное число с ведущими нулями, т.е. в данном случае имеем числа <tex> 00 </tex>, <tex> 01 </tex>, <tex> 10 </tex>, <tex> 11 </tex>. Ниже приведена таблица, в которой записаны все искомые произведения:<br />
<br />
<tex><br />
\begin{array}{|c|c|c|c|c|} <br />
\hline <br />
& \textbf{00} & \textbf{01} & \textbf{10} & \textbf{11} \\<br />
\hline <br />
\textbf{00} & 0 & 0 & 0 & 0 \\ <br />
\hline <br />
\textbf{01} & 0 & 1 & 0 & 1 \\ <br />
\hline <br />
\textbf{10} & 0 & 0 & 1 & 1 \\ <br />
\hline <br />
\textbf{11} & 0 & 1 & 1 & 0\\ <br />
\hline <br />
\end{array} <br />
</tex><br />
<br />
Согласно соглашению относительно битовых векторов и двоичных чисел получим новые матрицы <tex> A' </tex> и <tex> B' </tex>:<br />
<br />
<tex> A' = </tex><br />
<tex><br />
\left(\begin{array}{cccc} <br />
01 & 11 \\ <br />
01 & 00 \\ <br />
11 & 01 \\ <br />
10 & 01 <br />
\end{array}\right)<br />
</tex><br />
,<br />
<tex> B' = </tex><br />
<tex><br />
\left(\begin{array}{cccc} <br />
10 & 00 & 01 & 11 \\ <br />
10 & 01 & 10 & 01 <br />
\end{array}\right)<br />
</tex><br />
<br />
Перемножим эти матрицы по модулю два с использованием нашего предпосчета:<br />
<br />
<tex> C = A' \times B' = </tex><br />
<tex><br />
\left(\begin{array}{cccc} <br />
1 & 1 & 0 & 0 \\ <br />
0 & 0 & 1 & 1 \\ <br />
1 & 1 & 1 & 1 \\ <br />
1 & 1 & 0 & 0 <br />
\end{array}\right)<br />
</tex><br />
<br />
Матрица <tex> C </tex> {{---}} искомая.<br />
<br />
== Источники информации ==<br />
* ''Gregory V. Bard'' — ''Accelerating Cryptanalysis with the Method of Four Russians''. July 22, 2006. Страница 5<br />
<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Динамическое программирование]]<br />
[[Категория: Способы оптимизации методов динамического программирования]]</div>83.239.81.22