Русская Википедия:Алгоритм Видемана
Алгоритм Видемана — алгоритм, позволяющий получить решение системы линейных уравнений <math>Ax = b, b \ne 0</math> над конечным полем <math> K = GF(q)</math>. Был предложен Дугласом Видеманом (Шаблон:Lang-en) в 1986 году. В течение некоторого времени после опубликования статьи, алгоритм не получил большой поддержки и считался пригодным только для получения наилучших оценок сложностиШаблон:Sfn. Но позже алгоритмы Видемана были реализованы на компьютере и использовались, например, для поиска разложения многочленов на множители над конечными полями.
История возникновения
Алгоритмы Видемана были представлены общественности в прошлом столетии. В 1986 году в январском выпуске журнала IEEE Transactions on Information Theory была опубликована статья Дугласа Видемана под названием «Решение разреженной системы линейных уравнений над конечным полем» (Шаблон:Lang-en). В ней были описаны алгоритмы для решения системы линейных уравнений над конечным полем в случае когда матрица системы является разреженной. Причём в статье были рассмотрены случаи с различными разреженными матрицами. Также в статье было опубликовано обоснование алгоритмов и оценка сложности их работыШаблон:Sfn.
Задача
Алгоритм нужен чтобы решить систему линейных уравнений <math>Ax = b, b \ne 0</math>. Матрица <math>A</math> имеет размерность <math>n \times n</math> и предполагается разреженной, количество ненулевых элементов в ней равно <math>w</math>Шаблон:Sfn.
Теория
С помощью матрицы <math>A</math> определяется невырожденное линейное отображение(которое обозначается также <math>A</math>) на пространстве <math>\Kappa^n</math>. Рассматривается пространство <math>S</math>, порождённое множеством векторов <math> \left\{ Шаблон:(A^i b k) \right\}_{i=0,1,2} </math> и определяется <math>A_S = A|_S</math> - линейное отображение <math>S</math> на <math>S</math>.
Обозначим <math>f_z \in \Kappa^n</math> — минимальный многочлен <math>A_S</math>, то есть ненулевой многочлен наименьшей степени, такой, что <math>f(A_s)</math> является нулевым отображением <math>S</math>, при чём нормализованный так, что его свободный член равен единице. Отметим, что если <math>g(z) \in \Kappa[z]</math>, то <math>g(A_s) </math> - нулевое отображение тогда и только тогда, когда <math>g(A)b = 0</math>. Кроме того, <math>f(z)</math> делит многочлен <math>det(zl_n-A)</math>, и поэтому <math>deg f(z) \leqslant n</math>.
Обозначим <math>d = deg f(z), f(z) = \sum^{d}_{i=0} {f[i]z^i}</math>, где <math>f[i] \in \Kappa^n</math> - коэффициенты <math>f(z)</math>. Если можно найти <math>f(z)</math>, то решение системы <math>Ax = b, b \ne 0</math> также находится: так как <math>f(A)b = 0</math> и <math>f[0] = 1</math>, то
<math>x = -\sum^{d}_{i=1} {f[i]A^{i-1}b}</math>
Пусть <math>u</math> - какой-либо фиксированный вектор из <math>\Kappa^n</math>. Обозначим стандартное билинейное отображение <math>\Kappa^n</math> в <math>\Kappa</math> как <math>(,)</math> , то есть <math>((v_1,...,v_n),(w_1,...,w_n)) = \sum^{n}_{i=1} {v_i w_i}</math>.
Так как <math>f(A)b = 0</math>, то последовательность
<math>(u,A^ib), i = 0,1,2,...,</math>
удовлетворяет линейному рекуррентному соотношению, характеристический многочлен которого равен <math>f(z)</math>. Пусть <math>f_u(z)</math> - характеристический многочлен самого короткого рекуррентного соотношения. Тогда <math>f(z) | f_u(z)</math>. Действительно, если разделить с остатком
<math>f(z) = q(z)f_u(z)+r(z)</math>, <math> deg r(z) < deg ~ f_u(z)</math>
то из равенств
<math>0 = (u, f(A)b) = (u, q(A)f_u(A)b) + (u, r(A)b)</math>,
<math>(u, f_u(A)A^jb) = 0, j = 0,1,2,...,</math>
и минимальности <math>f_u(z)</math> будет следовать, что <math>r(z) = 0</math>. Поскольку свободный член <math>f(z)</math> равен единице, то можно принять, что свободный член <math>f_u(z)</math> равен единице.
Минимальный многочлен <math>f_u(z)</math> для последовательности <math>(u,A^ib), i = 0,1,2,...,</math> может быть получен с помощью алгоритма Берлекэмпа-МессиШаблон:Sfn по первым её <math>2n</math> членам. Существуют два метода решения исходной системы.
Первый метод. Выбирается случайный вектор <math>u(z)</math>. Строится <math>f_u(z)</math> и в предположении, что <math>f(z) = f_u(z)</math>, находится <math>x</math> по формуле
<math>x = -\sum^{d}_{i=1} {f[i]A^{i-1}b}</math>
Этим путём с достаточно высокой вероятностью можно найти решениеШаблон:Sfn.
Второй метод. Пусть <math>b_0 = b, f_1 (z) = f_{u_1} (z)</math> для некоторого вектора <math>u_1</math> . Если вектор <math>b_1 = f_1(A)b_0</math> равен 0, то находится <math> x</math> по формуле
<math>x = -\sum^{d}_{i=1} {f[i]A^{i-1}b}</math> (так как тогда <math> f_1(z) = f(z)</math> ).
Если же <math>b_1 \ne 0</math>, то повторяется процедура, то есть выбирается случайный вектор <math>u_2</math> и строится минимальный многочлен <math>f_2(z) = f_{u_2}(z)</math> для последовательности <math>(u_2, A_ib_1)</math>. Если <math>b_2 = f_2(A)b_1 = 0</math>, то <math>f(z) = f_1(z)f_2(z)</math> и можно найти решение x по формуле
<math>x = -\sum^{d}_{i=1} {f[i]A^{i-1}b}</math>,
иначе выбирается <math>u_3</math> и так далее.
Докажем, что если сделано <math>k</math> итераций, то <math>f_1(z)...f_k(z)</math> делит <math>f(z)</math>. Выше было показано, что <math>f-1(z)|f(z)</math>. Далее, если предположить что <math>f_1(z)...f_{k-1}(z)</math> делит <math>f(z)</math>, то поскольку <math>f_k(z)</math> - минимальный многочлен для последовательности <math> \left\{ (u_k,A^ib_{k-1}) \right\}_i = \left\{ (u_k,f_{k-1}(A)...f_{1}(A^j)b)\right\}_j</math>, а многочлен <math>\frac{f(z)}{f_1(z)...f_{k-1}(z)}</math> её аннулирует, то <math>{f_k(z)}|{\frac{f(z)}{f_1(z)...f_{k-1}(z)}}</math>, что и требовалось доказать.
Теперь очевидно, что если <math>b_x = f_k(A)...f_1(A)b = 0</math>, то <math>f(x) = f_1(x)...f_k(x)</math>. То есть, как только будет найден нулевой вектор <math>b_k = f_k(A)b_{k-1}</math>, то можно найти решение исходной системы по формуле
<math>x = -\sum^{d}_{i=1} {f[i]A^{i-1}b}</math>Шаблон:Sfn.
Алгоритм 1
В оригинальной статье алгоритм имеет такое название. На его основе строится детерминированный алгоритм, который в оригинальной статье называется алгоритм 2Шаблон:Sfn.
Описание алгоритма
1 этап. Приравнивается <math>b_0 = b, k = 0, y_0 = 0, d_0 = 0</math>.
2 этап. Если <math>b_k = 0</math>, то решение равно <math>x = -y_k</math>, и алгоритм прекращает работу.
3 этап. Выбирается случайный вектор <math>u_{k+1} \in \Kappa^n , u_{k+1} \ne 0 </math>.
4 этап. Вычислить первые <math>2(n-d_k) </math> членов последовательности <math> \left\{ {{(u_{k+1} , A^i b_k)}} \right\}^\infty_{i=0} </math>.
5 этап. Вычислить минимальный многочлен <math>f_{k+1} (z)</math> последовательности из 4-го этапа, причём нормализовать его так, чтобы его свободный член равнялся единице. Это можно осуществить с помощью алгоритма Берлекэмпа-Месси.
6 этап. Присвоить
<math>y_{k+1} = y_k + {\hat{f}}_{k+1}(A)b_k</math>, где <math>\hat{f}(z) = \frac{f(z)-f(0)}{z}</math>
<math>b_{k+1} = b_0 + Ay_{k+1} </math>,
<math>d_{k+1} = d_k + deg ~f_{k+1} (z)</math>.
7 этап. Присвоить <math>k = k+1</math> и вернуться на второй этапШаблон:Sfn.
Обоснование корректности алгоритма с помощью метода математической индукции
<math>\hat{f}(z) = \frac{f(z)-f(0)}{z}</math> соответствует правой части формулы <math>x = -\sum^{d}_{i=1} {f[i]A^{i-1}b}</math> без знака минус. При <math>k = 0</math> выбирается <math>u_1</math>, рассматривается <math>2n</math> членов последовательности <math> \left\{ Шаблон:(u 1 , A^i b 0) \right\}_{i=0,1,2} </math> и находится <math>f_1(x)</math> по алгоритму Берлекэмпа-Месси. Тогда <math>y_1 = \hat{f}_1(A)b, b_1 = b_0 + Ay_1 = b + A\frac{f_1(A)-1}{A}b = f_1(A)b, d_1 = deg f_1(z)</math>.
Пусть после <math>k</math> проходов алгоритма выполнены равенства
<math>y_k = \frac{f_k(A)...f_1(A)-1}{A}b</math>
<math>b_k = f_k(A)...f_1(A)b</math>
Тогда после <math>k+1</math> прохода
<math>y_{k+1} = y_k + \hat{f}_{k+1}(A)b_k = \frac{f_k(A)...f_1(A)-1}{A}b+ \frac{f_{k+1}(A)-1}{A}f_k(A)...f_1(A)b = \frac{f_{k+1}(A)...f_1(A)-1}{A}b</math>,
<math>b_{k+1} = b_k + A \frac{f_{k+1}(A)...f_1(A)-1}{A}b = f_{k+1}(A)...f_1(A)b</math>
То есть формулы для <math>y_k</math> и <math>b_k</math> сохраняются. Теперь корректность алгоритма следует из раздела теорияШаблон:Sfn.
Детерминированный алгоритм
Описание алгоритма
1 этап. Найти значение <math>A^i b, i = 0,1,...,2n-1</math>.
2 этап. Приравнять нулю <math>k</math>, а <math>g_0(z)</math> единице.
3 этап. Присвоить <math>u_{k+1} = (0,...,0,1,0,...,0) </math>(единица находится на <math>k+1</math> месте).
4 этап. Найти последовательность <math>(u_{k+1}, A^i b), i = 0,1,...,2n-1</math> при помощи первого этапа.
5 этап. Найти последовательность <math>(u_{k+1}, g_k(A) A^i b), i = 0,1,...,2n-1-deg~g_k(z)</math>, можно использовать дискретное преобразование ФурьеШаблон:Sfn.
6 этап. Найти минимальный многочлен <math>f_{k+1}(z)</math> со свободным членом равным единице с помощью алгоритма Берлекэмпа-Месси.
7 этап. Присвоить <math>g_{k+1}(z) = f_{k+1}(z)g_k(z)</math>.
8 этап. Увеличить <math>k</math> на единицу. Если <math>deg~g_k(z) < n</math> и <math>k < n</math>, то возвратиться на 3 этап.
9 этап. Для многочлена <math>f(z) = g_k(z)</math> с помощью найденных на первом этапе значений <math>A^i b</math> отыскать решение <math>x</math> системы с помощью формулы
<math>x = -\sum^{d}_{i=1} {f[i]A^{i-1}b}</math>Шаблон:Sfn.
Обоснование корректности алгоритма
Обратим внимание, что фактически алгоритм работает также, как и алгоритм 1, только векторы <math>u_k</math> выбираются не случайно, а идёт перебор единичных векторов <math>(0,...,0,1,0,...,0)</math>. Очевидно, что <math>g_k(z) = f_k(z)...f_1(z)</math>, где <math>f_k(z)</math> — минимальный многочлен для последовательности
<math>(u_k, f_{k-1}(A)...f_1(A) A^i b), i = 0,1,...,2n-1-deg(f_{k-1}...f_1)</math>.
Алгоритм закончил работу при некотором значении параметра <math>k</math>. Предположим, что <math>k < n, deg~g_k(z) = n</math>. Так как <math>deg~f(z) \leqslant n</math> и <math>g_k(z) | f(z)</math>, то <math>g_k(z) = f(z)</math>. Отсюда следует, что на этапе 9 решение исходной системы точно будет найдено.
Теперь рассмотрим случай <math>k = n</math>. Поскольку был совершён перебор всех единичных векторов <math>u_1,...,u_n</math>, то вектор <math>g_n(A)b</math> ортогонален <math>u_1,...,u_n</math>. Следовательно, <math>g_n(A)b = 0</math>. Так как <math>g_n(z)|f(z)</math> и <math>f(z)</math> -минимальный многочлен, то <math>g_k(z) = f(z)</math>. Поэтому и в данном случае подтверждена корректность работы алгоритмаШаблон:Sfn.
Оценка сложности алгоритма
Для детерминированного алгоритма Видеманом была получена следующая оценка сложности: <math>O(n(w + n~log(n)log(log (n))))</math>Шаблон:Sfn. Полученная оценка сложности является наилучшей среди известных. Благодаря алгоритму Видемана возможно улучшение оценки сложности в других алгоритмах, использующих методы решения линейных системШаблон:Sfn.
Аналогичные алгоритмы
Где может пригодится решение системы линейных уравнений над конечным полем? Потребность в их решении возникает при использовании алгоритмов факторизации и при решении задач дискретного логарифмирования, использующих факторные базыШаблон:Sfn. Существует большое количество алгоритмов для получения решения системы линейных уравнений над конечными полямиШаблон:Sfn. Помимо алгоритмов Видемана можно использовать гауссово и структурное гауссово исключения, алгоритм Ланцоша, метод сопряжённых градиентов Шаблон:Sfn . Также известны алгоритмы основанные на быстром умножении матриц, например на алгоритмах Штрассена и Копперсмита-ВиноградаШаблон:Sfn. Свои алгоритмы были предложены КоновальцевымШаблон:Sfn и БриллхартомШаблон:SfnШаблон:Sfn.
В общем случае (матрица системы не является разреженной) в последнее время чаще используется алгоритм Ланцоша(вероятно, вместе со структурированным гауссовым исключением для получения более плотной матрицы подсистемы)Шаблон:Sfn. Но в случае разреженной матрицы эффективнее всего использовать алгоритмы Видемана, так как оценки их сложности являются наилучшими из известных. Не сразу алгоритмы Видемана получили признание, но позже всё-таки были реализованы на компьютере. Алгоритмы использовались, например, для разложения многочленов на множители над конечными полямиШаблон:Sfn.
Позже появились различные модификации оригинального алгоритма, например блочный алгоритм ВидеманаШаблон:Sfn.
Примечания
Литература
Шаблон:^ Шаблон:Теоретико-числовые алгоритмы
