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

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 59 промежуточных версий 4 участников)
Строка 1: Строка 1:
== Постановка задачи ==
+
{{Задача
 
+
|definition = Дано две квадратных матрицы <tex>A_{[n \times n]}</tex> и <tex>B_{[n \times n]}</tex>,  
Рассмотрим следующую задачу: «Дано две квадратных матрицы <tex>A_{[n \times n]}</tex> и <tex>B_{[n \times n]}</tex>,  
+
состоящие из нулей и единиц. Нужно найти их произведение. При этом, все операции выполняются по модулю <tex>2</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>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>.
+
Если мы будем считать произведение матриц <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>.
  
 
Сейчас будет показано, как немного уменьшить это время.
 
Сейчас будет показано, как немного уменьшить это время.
 
  
 
== Сжатие матриц ==  
 
== Сжатие матриц ==  
Строка 19: Строка 28:
 
Аналогично поступим с матрицей <tex>B</tex>, вместо строк деля столбцы. Получим матрицу <tex dpi=140>B'_{\lceil\frac nk\rceil\times n}</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 \frac nk \rceil</tex> вместо <tex>n</tex>, и время произведения матриц сократится с <tex>O(n^3)</tex> до <tex dpi=140>O(n^2 \cdot\frac nk) = O(\frac{n^3}{k}) </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 ==
+
== Оценка сложности алгоритма и выбор k ==
 +
[[Файл:exampleFourRussiansAlgoFinalPicture.png|500px|right]]
  
Оценим трудоёмкость данного алгоритма.
+
Оценим асимптотику данного алгоритма.
  
 
* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.
 
* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.
* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(n^2)</tex>
+
* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(n^2)</tex>.
* Перемножение полученных матриц {{---}} <tex dpi=140>O(\frac{n^3}{k})</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> A </tex> и <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>
 +
 
 +
<tex> k = \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> A' </tex> и <tex> B' </tex>:
  
Итого: <tex>O(2^{2k}k) + O(\frac{n^3}{k})</tex>.
+
<tex> A' = </tex>
Приведем анализ выбора числа <tex>k</tex> для получения оптимальной сложности алгоритма.
+
<tex>
 +
\left(\begin{array}{cccc}  
 +
          01 & 11 \\ 
 +
          01 & 00 \\ 
 +
          11 & 01 \\ 
 +
          10 & 01
 +
        \end{array}\right)
 +
</tex>
 +
,
 +
<tex> B' = </tex>
 +
<tex>
 +
\left(\begin{array}{cccc} 
 +
          10 & 00 & 01 & 11 \\   
 +
          10 & 01 & 10 & 01
 +
        \end{array}\right)
 +
</tex>
  
В силу возрастания функции <tex>f(k) = 2^{2k}k</tex> и убывания функции <tex>g(k) = \frac{n^3}{k}</tex> имеем, что сложность будет оптимальна при таком значении <tex>k</tex>, что <tex>f(k) = g(k)</tex>. Прологарифмируем обе части этого равенства:
+
Перемножим эти матрицы по модулю два с использованием нашего предпосчета:
  
<tex>k \ln 4 + \ln k= 3 \ln n - \ln k</tex>
+
<tex> C = A'  \times B' = </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>k = \frac{3 \ln n - 2 \ln k}{\ln 4} </tex>
+
Матрица <tex> C </tex> {{---}} искомая.
  
<tex> k  = 3 \log_4 n - 2 \log_4 k </tex>
+
== Источники информации ==
 +
* ''Gregory V. Bard'' — ''Accelerating Cryptanalysis with the Method of Four Russians''. July 22, 2006. Страница 5
  
В силу того, что <tex> \log_4 k </tex> пренебрежительно мал по сравнению с <tex> k </tex> имеем, что <tex> k </tex> с точностью до константы равен <tex> \log n </tex>
 
  
Таким образом, при подстановке <tex>k = \log n</tex>, получаем итоговую трудоёмкость <tex dpi=140>O(n^2 \log n) + O(\frac{n^3}{\log n}) = O(\frac{n^3}{\log n})</tex>
+
[[Категория: Дискретная математика и алгоритмы]]
== Код алгоритма ==
+
[[Категория: Динамическое программирование]]
<code>
+
[[Категория: Способы оптимизации методов динамического программирования]]
int n, cur;
 
vector <vector <int> > a, b, preculc, anew, bnew, ans;
 
int main() {
 
  freopen("input.txt", "r", stdin);
 
  freopen("output.txt", "w", stdout);
 
  cin >> n;
 
  a.resize(n);
 
  b.resize(n);
 
  ans.resize(n);
 
  // Чтение матриц
 
  for (int i = 0; i < n; i++)
 
      for (int j = 0; j < n; j++) {
 
        cin >> cur;
 
        a[i].push_back(cur);
 
      } 
 
  for (int i = 0; i < n; i++)
 
      for (int j = 0; j < n; j++) {
 
        cin >> cur;
 
        b[i].push_back(cur);
 
      } 
 
  // Предподсчёт скалярных произведений
 
  int k = ceil(log( (double) n));
 
  preculc.resize(1 << k);
 
  for (int i = 0; i < (1 << k); i++)
 
      for (int j = 0; j < (1 << k); j++) {
 
        int scalmul = 0;
 
        for (int pos = 0; pos < k; pos++)
 
            if (((1 << pos) & i) != 0 && ((1 << pos) & j) != 0) {
 
              scalmul = (scalmul + 1) % 2;
 
            }
 
        preculc[i].push_back(scalmul);
 
      }
 
  // Создание сжатых матриц
 
  int m = ceil(((double) n) / k);
 
  anew.resize(n);
 
  bnew.resize(m);
 
  for (int i = 0; i < n; i++) {
 
     
 
      for (int start = 0; start < n; start += k) {
 
        int cursuma = 0, cursumb = 0, curpos = start, deg = (1 << (k - 1));
 
        while (curpos < start + k && curpos < n) {
 
            cursuma += a[i][curpos] * deg;
 
            cursumb += b[curpos][i] * deg;
 
            deg /= 2;
 
            curpos++;
 
        }
 
        anew[i].push_back(cursuma);
 
        bnew[start / k].push_back(cursumb);
 
      }
 
  }
 
  //Перемножение полученных матриц
 
  for (int i = 0; i < n; i++)
 
      for (int j = 0; j < n; j++) {
 
        int curans = 0;
 
        for (int pos = 0; pos < m; pos++) {
 
            curans = (curans + preculc[anew[i][pos]][bnew[pos][j]]) % 2;
 
        }
 
        ans[i].push_back(curans);
 
      }
 
  // Вывод ответа
 
  for (int i = 0; i < n; i++) {
 
      for (int j = 0; j < n; j++) {
 
        cout << ans[i][j] << " ";
 
      }
 
      cout << endl;
 
  }
 
  return 0;
 
}
 
</code>
 

Текущая версия на 18:07, 8 октября 2019

Задача:
Дано две квадратных матрицы [math]A_{[n \times n]}[/math] и [math]B_{[n \times n]}[/math], состоящие из нулей и единиц. Нужно найти их произведение. При этом, все операции выполняются по модулю [math]2[/math].


Простое решение[править]

Если мы будем считать произведение матриц [math]C = A \cdot B[/math] по определению [math]\left(c_{i, j} = \sum\limits_{k = 1}^n a_{i,k}b_{k,j}\right)[/math], то сложность работы алгоритма составит [math]O(n^3)[/math] — каждый из [math]n^2[/math] элементов результирующей матрицы [math]C[/math] вычисляется за время, пропорциональное [math]n[/math].

Сейчас будет показано, как немного уменьшить это время.

Сжатие матриц[править]

Для выполнения сжатия матриц выполним следующий предподсчёт : для всех возможных пар двоичных векторов длины [math]k[/math] подсчитаем и запомним их скалярное произведение по модулю [math]2[/math].

Возьмём первую матрицу. разделим каждую её строку на куски размера [math]k[/math]. Для каждого куска определим номер двоичного вектора, который соответствует числам, находящимся на этом куске. Если кусок получился неравным по длине [math]k[/math](последний кусок строки), то будем считать, что в конце в нём идут не влияющие на умножение нули. Получим матрицу [math]A'_{n \times \lceil\frac{n}{k} \rceil}[/math].

Аналогично поступим с матрицей [math]B[/math], вместо строк деля столбцы. Получим матрицу [math]B'_{\lceil\frac nk\rceil\times n}[/math].

Теперь, если вместо произведения матриц [math]A[/math] и [math]B[/math] считать произведение новых матриц [math]A'[/math] и [math]B'[/math], воспользовавшись посчитанными скалярными произведениями, то каждый элемент матрицы [math]C[/math] будет получаться уже за время, пропорциональное [math]\lceil \dfrac{n}{k} \rceil[/math] вместо [math]n[/math], и время произведения матриц сократится с [math]O(n^3)[/math] до [math]O(n^2 \cdot\dfrac nk) = O(\dfrac{n^3}{k}) [/math].

Оценка сложности алгоритма и выбор k[править]

ExampleFourRussiansAlgoFinalPicture.png

Оценим асимптотику данного алгоритма.

  • Предподсчёт скалярных произведений работает за [math]O(2^{2k}k)[/math].
  • Создание матриц [math]A'[/math] и [math]B'[/math][math]O(n^2)[/math].
  • Перемножение полученных матриц — [math]O(\dfrac{n^3}{k})[/math].

Итого: [math]O(2^{2k}k) + O(\dfrac{n^3}{k})[/math]. Выбрав [math]k = \log n [/math], получаем требуемую асимптотику [math]O(n^2 \log n) + O(\dfrac{n^3}{\log n}) = O(\dfrac{n^3}{\log n})[/math]

Пример работы алгоритма[править]

Рассмотрим работу алгоритма на примере перемножения двух матриц [math] A [/math] и [math] B [/math], где

[math] A = [/math] [math] \left(\begin{array}{cccc} 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \end{array}\right) [/math] , [math] B = [/math] [math] \left(\begin{array}{cccc} 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{array}\right) [/math]

[math] k = \log_2 n = \log_2 4 = 2[/math], то предподсчитаем все скалярные произведения:

Для удобства каждому битовому вектору будет соответствовать двоичное число с ведущими нулями, т.е. в данном случае имеем числа [math] 00 [/math], [math] 01 [/math], [math] 10 [/math], [math] 11 [/math]. Ниже приведена таблица, в которой записаны все искомые произведения:

[math] \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} [/math]

Согласно соглашению относительно битовых векторов и двоичных чисел получим новые матрицы [math] A' [/math] и [math] B' [/math]:

[math] A' = [/math] [math] \left(\begin{array}{cccc} 01 & 11 \\ 01 & 00 \\ 11 & 01 \\ 10 & 01 \end{array}\right) [/math] , [math] B' = [/math] [math] \left(\begin{array}{cccc} 10 & 00 & 01 & 11 \\ 10 & 01 & 10 & 01 \end{array}\right) [/math]

Перемножим эти матрицы по модулю два с использованием нашего предпосчета:

[math] C = A' \times B' = [/math] [math] \left(\begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 \end{array}\right) [/math]

Матрица [math] C [/math] — искомая.

Источники информации[править]

  • Gregory V. BardAccelerating Cryptanalysis with the Method of Four Russians. July 22, 2006. Страница 5