Processing math: 28%

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

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

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


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

Задача


 Алгоритм нужен чтобы решить систему линейных уравнений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)f_u(z)+r(z), deg r(z) < deg   f_u(z)
 то из равенств
0 = (u, f(A)b) = (u, q(A)f_u(A)b) + (u, r(A)b),
(u, f_u(A)A^jb) = 0, j = 0,1,2,...,
 и минимальности f_u(z) будет следовать, что r(z) = 0. Посколькусвободный член f(z) равен единице, то можно принять, что свободныйчлен f_u(z) равен единице.
 Минимальный многочлен f_u(z) для последовательности(u,A^ib), i = 0,1,2,..., может быть получен с помощью алгоритмаБерлекэмпа-Месси по первым её 2n членам. Существуют два метода решенияисходной системы.
Первый метод. Выбирается случайный вектор u(z). Строитсяf_u(z) и в предположении, что f(z) = f_u(z), находится x поформуле
x = -\sum^{d}_{i=1} {f[i]A^{i-1}b}
 Этим путём с достаточно высокой вероятностью можно найти решение.
Второй метод. Пусть b_0 = b, f_1 (z) = f_{u_1} (z) длянекоторого вектора u_1 . Если вектор b_1 = f_1(A)b_0 равен 0, тонаходится x по формуле
x = -\sum^{d}_{i=1} {f[i]A^{i-1}b} (так как тогда f_1(z) = f(z) ).
 Если же b_1 \ne 0, то повторяется процедура, то есть выбираетсяслучайный вектор u_2 и строится минимальный многочленf_2(z) = f_{u_2}(z) для последовательности (u_2, A_ib_1). Еслиb_2 = f_2(A)b_1 = 0, то f(z) = f_1(z)f_2(z) и можно найти решение xпо формуле
x = -\sum^{d}_{i=1} {f[i]A^{i-1}b},
 иначе выбирается u_3 и так далее.
 Докажем, что если сделано k итераций, то f_1(z)...f_k(z) делитf(z). Выше было показано, что f-1(z)|f(z). Далее, если предположитьчто f_1(z)...f_{k-1}(z) делит f(z), то поскольку f_k(z) -минимальный многочлен для последовательности\left\{ (u_k,A^ib_{k-1}) \right\}_i = \left\{ (u_k,f_{k-1}(A)...f_{1}(A^j)b)\right\}_j,а многочлен \frac{f(z)}{f_1(z)...f_{k-1}(z)} её аннулирует, то{f_k(z)}|{\frac{f(z)}{f_1(z)...f_{k-1}(z)}}, что и требовалосьдоказать.
 Теперь очевидно, что если b_x = f_k(A)...f_1(A)b = 0, тоf(x) = f_1(x)...f_k(x). То есть, как только будет найден нулевойвектор b_k = f_k(A)b_{k-1}, то можно найти решение исходной системы поформуле
x = -\sum^{d}_{i=1} {f[i]A^{i-1}b}.

Алгоритм1


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

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


1 этап. Приравнивается b_0 = b, k = 0, y_0 = 0, d_0 = 0.
2 этап. Если b_k = 0, то решение равно x = -y_k, и алгоритмпрекращает работу.
3 этап. Выбирается случайный векторu_{k+1} \in \Kappa^n , u_{k+1} \ne 0.
4 этап. Вычислить первые 2(n-d_k) членов последовательности\left\{ {{(u_{k+1} , A^i b_k)}} \right\}_{i=0,1,2}.
5 этап. Вычислить минимальный многочлен f_{k+1} (z)последовательности из 4-го этапа, причём нормализовать его так, чтобыего свободный член равнялся единице. Это можно осуществить с помощьюалгоритма Берлекэмпа-Месси.
6 этап. Присвоить
y_{k+1} = y_k + {\hat{f}}_{k+1}(A)b_k, где\hat{f}(z) = \frac{f(z)-f(0)}{z}
b_{k+1} = b_0 + Ay_{k+1},
d_{k+1} = d_k + deg  f_{k+1} (z).
7 этап. Присвоить k = k+1 и вернуться на второй этап.

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


\hat{f}(z) = \frac{f(z)-f(0)}{z} соответствует правой части формулыx = -\sum^{d}_{i=1} {f[i]A^{i-1}b} без знака минус. При k = 0выбирается u_1, рассматривается 2n членов последовательности\left\{ {{(u_1 , A^i b_0)}} \right\}_{i=0,1,2} и находится f_1(x) поалгоритму Берлекэмпа-Месси. Тогда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).
 Пусть после k проходов алгоритма выполнены равенства
y_k = \frac{f_k(A)...f_1(A)-1}{A}b
b_k = f_k(A)...f_1(A)b
 Тогда после k+1 прохода
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,
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
 То есть формулы для y_k и b_k сохраняются. Теперь корректностьалгоритма следует из раздела теория.

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


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


1 этап. Найти значение A^i b, i = 0,1,...,2n-1.
2 этап. Приравнять нулю k, а g_0(z) единице.
3 этап. Присвоить u_{k+1} = (0,...,0,1,0,...,0)(единицанаходится на k+1 месте).
4 этап. Найти последовательность(u_{k+1}, A^i b), i = 0,1,...,2n-1 при помощи первого этапа.
5 этап. Найти последовательность(u_{k+1}, g_k(A) A^i b), i = 0,1,...,2n-1-deg g_k(z), можноиспользовать дискретное преобразование Фурье.
6 этап. Найти минимальный многочлен f_{k+1}(z) со свободнымчленом равным единице с помощью алгоритма Берлекэмпа-Месси.
7 этап. Присвоить g_{k+1}(z) = f_{k+1}(z)g_k(z).
8 этап. Увеличить k на единицу. Если deg g_k(z) < n иk < n, то возвратиться на 3 этап.
9 этап. Для многочлена f(z) = g_k(z) с помощью найденных напервом этапе значений A^i b отыскать решение x системы с помощьюформулы
x = -\sum^{d}_{i=1} {f[i]A^{i-1}b}.

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


 Обратим внимание, что фактически алгоритм работает также, как и алгоритм1, только векторы u_k выбираются не случайно, а идёт перебор единичныхвекторов (0,...,0,1,0,...,0). Очевидно, чтоg_k(z) = f_k(z)...f_1(z), где f_k(z) — минимальный многочлен дляпоследовательности
(u_k, f_{k-1}(A)...f_1(A) A^i b), i = 0,1,...,2n-1-deg(f_{k-1}...f_1).
 Алгоритм закончил работу при некотором значении параметра k.Предположим, что k < n, deg g_k(z) = n. Так как deg f(z) \leqslant nи g_k(z) | f(z), то g_k(z) = f(z). Отсюда следует, что на этапе 9решение исходной системы точно будет найдено.
 Теперь рассмотрим случай k = n. Поскольку был совершён перебор всехединичных векторов u_1,...,u_n, то вектор g_n(A)b ортогоналенu_1,...,u_n. Следовательно, g_n(A)b = 0. Так как g_n(z)|f(z) иf(z) -минимальный многочлен, то g_k(z) = f(z). Поэтому и в данномслучае подтверждена корректность работы алгоритма.

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


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

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


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