Алгоритм Видемана

Алгоритм Видемана — алгоритм, позволяющий получить решение системы линейных уравнений Ax=b,b0 над конечным полем K=GF(q). Был предложен Дугласом Видеманом в 1986 году. В течение некоторого времени после опубликования статьи, алгоритм не получил большой поддержки и считался пригодным только для получения наилучших оценок сложности. Но позже алгоритмы Видемана были реализованы на компьютере и использовались, например, для поиска разложения многочленов на множители над конечными полями.

История возникновения


 Алгоритмы Видемана были представлены общественности в прошлом столетии. В 1986 году в январском выпуске журнала IEEE Transactions on Information Theory была опубликована статья Дугласа Видемана под названием «Решение разреженной системы линейных уравнений над конечным полем» . В ней были описаны алгоритмы для решения системы линейных уравнений над конечным полем в случае когда матрица системы является разреженной. Причём в статье были рассмотрены случаи с различными разреженными матрицами. Также в статье было опубликовано обоснование алгоритмов и оценка сложности их работы.

Задача


 Алгоритм нужен чтобы решить систему линейных уравнений Ax=b,b0. Матрица A имеет размерность n×n и предполагается разреженной, количество ненулевых элементов в ней равно w.

Теория


 С помощью матрицы A определяется невырожденное линейное отображение(которое обозначается также A) на пространстве \Kappan. Рассматривается пространство S, порождённое множеством векторов {(Aibk)}i=0,1,2 и определяется AS=A|S - линейное отображение S на S.
 Обозначим fz\Kappan — минимальный многочлен AS, то есть ненулевой многочлен наименьшей степени, такой, что f(As) является нулевым отображением S, при чём нормализованный так, что его свободный член равен единице. Отметим, что если g(z)\Kappa[z], то g(As) - нулевое отображение тогда и только тогда, когда g(A)b=0. Кроме того, f(z) делит многочлен det(zlnA), и поэтому degf(z)n.
 Обозначим d=degf(z),f(z)=di=0f[i]zi, где f[i]\Kappan - коэффициенты f(z). Если можно найти f(z), то решение системы Ax=b,b0 также находится: так как f(A)b=0 и f[0]=1, то
x=di=1f[i]Ai1b
 Пусть u - какой-либо фиксированный вектор из \Kappan. Обозначим стандартное билинейное отображение \Kappan в \Kappa как (,) , то есть ((v1,...,vn),(w1,...,wn))=ni=1viwi.
 Так как f(A)b=0, то последовательность
(u,Aib),i=0,1,2,...,
 удовлетворяет линейному рекуррентному соотношению, характеристический многочлен которого равен f(z). Пусть fu(z) - характеристический многочлен самого короткого рекуррентного соотношения. Тогда f(z)|fu(z). Действительно, если разделить с остатком
f(z)=q(z)fu(z)+r(z), degr(z)<degfu(z)
 то из равенств
0=(u,f(A)b)=(u,q(A)fu(A)b)+(u,r(A)b),
(u,fu(A)Ajb)=0,j=0,1,2,...,
 и минимальности fu(z) будет следовать, что r(z)=0. Поскольку свободный член f(z) равен единице, то можно принять, что свободный член fu(z) равен единице.
 Минимальный многочлен fu(z) для последовательности (u,Aib),i=0,1,2,..., может быть получен с помощью алгоритма Берлекэмпа-Месси по первым её 2n членам. Существуют два метода решения исходной системы.
Первый метод. Выбирается случайный вектор u(z). Строится fu(z) и в предположении, что f(z)=fu(z), находится x по формуле
x=di=1f[i]Ai1b
 Этим путём с достаточно высокой вероятностью можно найти решение.
Второй метод. Пусть b0=b,f1(z)=fu1(z) для некоторого вектора u1 . Если вектор b1=f1(A)b0 равен 0, то находится x по формуле
x=di=1f[i]Ai1b (так как тогда f1(z)=f(z) ).
 Если же b10, то повторяется процедура, то есть выбирается случайный вектор u2 и строится минимальный многочлен f2(z)=fu2(z) для последовательности (u2,Aib1). Если b2=f2(A)b1=0, то f(z)=f1(z)f2(z) и можно найти решение x по формуле
x=di=1f[i]Ai1b,
 иначе выбирается u3 и так далее.
 Докажем, что если сделано k итераций, то f1(z)...fk(z) делит f(z). Выше было показано, что f1(z)|f(z). Далее, если предположить что f1(z)...fk1(z) делит f(z), то поскольку fk(z) - минимальный многочлен для последовательности {(uk,Aibk1)}i={(uk,fk1(A)...f1(Aj)b)}j, а многочлен f(z)f1(z)...fk1(z) её аннулирует, то fk(z)|f(z)f1(z)...fk1(z), что и требовалось доказать.
 Теперь очевидно, что если bx=fk(A)...f1(A)b=0, то f(x)=f1(x)...fk(x). То есть, как только будет найден нулевой вектор bk=fk(A)bk1, то можно найти решение исходной системы по формуле
x=di=1f[i]Ai1b.

Алгоритм 1


 В оригинальной статье алгоритм имеет такое название. На его основе строится детерминированный алгоритм, который в оригинальной статье называется алгоритм 2.

Описание алгоритма


1 этап. Приравнивается b0=b,k=0,y0=0,d0=0.
2 этап. Если bk=0, то решение равно x=yk, и алгоритм прекращает работу.
3 этап. Выбирается случайный вектор uk+1\Kappan,uk+10.
4 этап. Вычислить первые 2(ndk) членов последовательности {(uk+1,Aibk)}i=0,1,2.
5 этап. Вычислить минимальный многочлен fk+1(z) последовательности из 4-го этапа, причём нормализовать его так, чтобы его свободный член равнялся единице. Это можно осуществить с помощью алгоритма Берлекэмпа-Месси.
6 этап. Присвоить
yk+1=yk+f^k+1(A)bk, где f^(z)=f(z)f(0)z
bk+1=b0+Ayk+1,
dk+1=dk+degfk+1(z).
7 этап. Присвоить k=k+1 и вернуться на второй этап.

Обоснование корректности алгоритма с помощью метода математической индукции


f^(z)=f(z)f(0)z соответствует правой части формулы x=di=1f[i]Ai1b без знака минус. При k=0 выбирается u1, рассматривается 2n членов последовательности {(u1,Aib0)}i=0,1,2 и находится f1(x) по алгоритму Берлекэмпа-Месси. Тогда y1=f^1(A)b,b1=b0+Ay1=b+Af1(A)1Ab=f1(A)b,d1=degf1(z).
 Пусть после k проходов алгоритма выполнены равенства
yk=fk(A)...f1(A)1Ab
bk=fk(A)...f1(A)b
 Тогда после k+1 прохода
yk+1=yk+f^k+1(A)bk=fk(A)...f1(A)1Ab+fk+1(A)1Afk(A)...f1(A)b=fk+1(A)...f1(A)1Ab,
bk+1=bk+Afk+1(A)...f1(A)1Ab=fk+1(A)...f1(A)b
 То есть формулы для yk и bk сохраняются. Теперь корректность алгоритма следует из раздела теория.

Детерминированный алгоритм


Описание алгоритма


1 этап. Найти значение Aib,i=0,1,...,2n1.
2 этап. Приравнять нулю k, а g0(z) единице.
3 этап. Присвоить uk+1=(0,...,0,1,0,...,0)(единица находится на k+1 месте).
4 этап. Найти последовательность (uk+1,Aib),i=0,1,...,2n1 при помощи первого этапа.
5 этап. Найти последовательность (uk+1,gk(A)Aib),i=0,1,...,2n1deggk(z), можно использовать дискретное преобразование Фурье.
6 этап. Найти минимальный многочлен fk+1(z) со свободным членом равным единице с помощью алгоритма Берлекэмпа-Месси.
7 этап. Присвоить gk+1(z)=fk+1(z)gk(z).
8 этап. Увеличить k на единицу. Если deggk(z)<n и k<n, то возвратиться на 3 этап.
9 этап. Для многочлена f(z)=gk(z) с помощью найденных на первом этапе значений Aib отыскать решение x системы с помощью формулы
x=di=1f[i]Ai1b.

Обоснование корректности алгоритма


 Обратим внимание, что фактически алгоритм работает также, как и алгоритм 1, только векторы uk выбираются не случайно, а идёт перебор единичных векторов (0,...,0,1,0,...,0). Очевидно, что gk(z)=fk(z)...f1(z), где fk(z) — минимальный многочлен для последовательности
(uk,fk1(A)...f1(A)Aib),i=0,1,...,2n1deg(fk1...f1).
 Алгоритм закончил работу при некотором значении параметра k. Предположим, что k<n,deggk(z)=n. Так как degf(z)n и gk(z)|f(z), то gk(z)=f(z). Отсюда следует, что на этапе 9 решение исходной системы точно будет найдено.
 Теперь рассмотрим случай k=n. Поскольку был совершён перебор всех единичных векторов u1,...,un, то вектор gn(A)b ортогонален u1,...,un. Следовательно, gn(A)b=0. Так как gn(z)|f(z) и f(z) -минимальный многочлен, то gk(z)=f(z). Поэтому и в данном случае подтверждена корректность работы алгоритма.

Оценка сложности алгоритма


 Для детерминированного алгоритма Видеманом была получена следующая оценка сложности: O(n(w+nlog(n)log(log(n)))). Полученная оценка сложности является наилучшей среди известных. Благодаря алгоритму Видемана возможно улучшение оценки сложности в других алгоритмах, использующих методы решения линейных систем.

Аналогичные алгоритмы


 Где может пригодится решение системы линейных уравнений над конечным полем? Потребность в их решении возникает при использовании алгоритмов факторизации и при решении задач дискретного логарифмирования, использующих факторные базы. Существует большое количество алгоритмов для получения решения системы линейных уравнений над конечными полями. Помимо алгоритмов Видемана можно использовать гауссово и структурное гауссово исключения, алгоритм Ланцоша, метод сопряжённых градиентов . Также известны алгоритмы основанные на быстром умножении матриц, например на алгоритмах Штрассена и Копперсмита-Винограда. Свои алгоритмы были предложены Коновальцевым и Бриллхартом.
 В общем случае (матрица системы не является разреженной) в последнее время чаще используется алгоритм Ланцоша(вероятно, вместе со структурированным гауссовым исключением для получения более плотной матрицы подсистемы). Но в случае разреженной матрицы эффективнее всего использовать алгоритмы Видемана, так как оценки их сложности являются наилучшими из известных. Не сразу алгоритмы Видемана получили признание, но позже всё-таки были реализованы на компьютере. Алгоритмы использовались, например, для разложения многочленов на множители над конечными полями.
 Позже появились различные модификации оригинального алгоритма, например блочный алгоритм Видемана.