403
правки
Изменения
Новая страница: «== Постановка задачи == Рассмотрим следующую задачу: «Дано две квадратных матрицы <tex>A_{[n \time…»
== Постановка задачи ==
Рассмотрим следующую задачу: «Дано две квадратных матрицы <tex>A_{[n \times n]}</tex> и <tex>B_{[n \times n]}</tex>,
Состоящие из нулей и единиц. Нужно найти их произведение по. При этом, все операции выполняются по модулю <tex>2</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>.
Хочется <s>большего</s> меньшего...
== Предподсчёт ==
Воспользуемся следующим {{TODO|t=ну не уместно здесь это словосочетание}} финтом ушами. Возьмём некоторое целое число <tex>k</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 \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>.
== Оценка трудоёмкости и выбор k ==
Оценим трудоёмкость данного алгоритма.
* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.
* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(N^2)</tex>
* Перемножение полученных матриц {{---}} <tex dpi=140>O(\frac{n^3}{k})</tex>
Итого: <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})</tex>
Рассмотрим следующую задачу: «Дано две квадратных матрицы <tex>A_{[n \times n]}</tex> и <tex>B_{[n \times n]}</tex>,
Состоящие из нулей и единиц. Нужно найти их произведение по. При этом, все операции выполняются по модулю <tex>2</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>.
Хочется <s>большего</s> меньшего...
== Предподсчёт ==
Воспользуемся следующим {{TODO|t=ну не уместно здесь это словосочетание}} финтом ушами. Возьмём некоторое целое число <tex>k</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 \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>.
== Оценка трудоёмкости и выбор k ==
Оценим трудоёмкость данного алгоритма.
* Предподсчёт скалярных произведений работает за <tex>O(2^{2k}k)</tex>.
* Создание матриц <tex>A'</tex> и <tex>B'</tex> {{---}} <tex>O(N^2)</tex>
* Перемножение полученных матриц {{---}} <tex dpi=140>O(\frac{n^3}{k})</tex>
Итого: <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})</tex>
