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

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

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


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

Задача


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

Теория


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

Алгоритм1


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

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


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

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


ˆf(z)=f(z)f(0)zf^(z)=f(z)f(0)z соответствует правой части формулыx=di=1f[i]Ai1bx=di=1f[i]Ai1b без знака минус. При k=0k=0выбирается u1u1, рассматривается 2n2n членов последовательности{(u1,Aib0)}i=0,1,2{(u1,Aib0)}i=0,1,2 и находится f1(x)f1(x) поалгоритму Берлекэмпа-Месси. Тогдаy1=ˆf1(A)b,b1=b0+Ay1=b+Af1(A)1Ab=f1(A)b,d1=degf1(z)y1=f^1(A)b,b1=b0+Ay1=b+Af1(A)1Ab=f1(A)b,d1=degf1(z).
 Пусть после kk проходов алгоритма выполнены равенства
yk=fk(A)...f1(A)1Abyk=fk(A)...f1(A)1Ab
bk=fk(A)...f1(A)bbk=fk(A)...f1(A)b
 Тогда после k+1k+1 прохода
yk+1=yk+ˆfk+1(A)bk=fk(A)...f1(A)1Ab+fk+1(A)1Afk(A)...f1(A)b=fk+1(A)...f1(A)1Abyk+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)bbk+1=bk+Afk+1(A)...f1(A)1Ab=fk+1(A)...f1(A)b
 То есть формулы для ykyk и bkbk сохраняются. Теперь корректностьалгоритма следует из раздела теория.

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


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


1 этап. Найти значение Aib,i=0,1,...,2n1Aib,i=0,1,...,2n1.
2 этап. Приравнять нулю kk, а g0(z)g0(z) единице.
3 этап. Присвоить uk+1=(0,...,0,1,0,...,0)uk+1=(0,...,0,1,0,...,0)(единицанаходится на k+1k+1 месте).
4 этап. Найти последовательность(uk+1,Aib),i=0,1,...,2n1(uk+1,Aib),i=0,1,...,2n1 при помощи первого этапа.
5 этап. Найти последовательность(uk+1,gk(A)Aib),i=0,1,...,2n1deggk(z)(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)))). Полученная оценкасложности является наилучшей среди известных. Благодаря алгоритмуВидемана возможно улучшение оценки сложности в других алгоритмах,использующих методы решения линейных систем.

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


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