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

Алгоритм Видемана — алгоритм, позволяющий получить решение системы линейных уравнений $A x = b, b \neq 0$ над конечным полем $K = G F (q)$ . Был предложен Дугласом Видеманом (Шаблон:Lang-en) в 1986 году. В течение некоторого времени после опубликования статьи, алгоритм не получил большой поддержки и считался пригодным только для получения наилучших оценок сложности Шаблон:Sfn. Но позже алгоритмы Видемана были реализованы на компьютере и использовались, например, для поиска разложения многочленов на множители над конечными полями.

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

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

Задача

Алгоритм нужен чтобы решить систему линейных уравнений $A x = b, b \neq 0$ . Матрица $A$ имеет размерность $n \times n$ и предполагается разреженной, количество ненулевых элементов в ней равно $w$ Шаблон:Sfn.

Теория

С помощью матрицы $A$ определяется невырожденное линейное отображение(которое обозначается также $A$ ) на пространстве $K^{n}$ . Рассматривается пространство $S$ , порождённое множеством векторов ${(A^{i} b_{k})}_{i = 0, 1, 2}$ и определяется $A_{S} = A |_{S}$ - линейное отображение $S$ на $S$ .

Обозначим $f_{z} \in K^{n}$ — минимальный многочлен $A_{S}$ , то есть ненулевой многочлен наименьшей степени, такой, что $f (A_{s})$ является нулевым отображением $S$ , при чём нормализованный так, что его свободный член равен единице. Отметим, что если $g (z) \in K [z]$ , то $g (A_{s})$ - нулевое отображение тогда и только тогда, когда $g (A) b = 0$ . Кроме того, $f (z)$ делит многочлен $d e t (z l_{n} - A)$ , и поэтому $d e g f (z) ⩽ n$ .

Обозначим $d = d e g f (z), f (z) = \sum_{i = 0}^{d} f [i] z^{i}$ , где $f [i] \in K^{n}$ - коэффициенты $f (z)$ . Если можно найти $f (z)$ , то решение системы $A x = b, b \neq 0$ также находится: так как $f (A) b = 0$ и $f [0] = 1$ , то

$x = - \sum_{i = 1}^{d} f [i] A^{i - 1} b$

Пусть $u$ - какой-либо фиксированный вектор из $K^{n}$ . Обозначим стандартное билинейное отображение $K^{n}$ в $K$ как $(,)$ , то есть $((v_{1}, . . ., v_{n}), (w_{1}, . . ., w_{n})) = \sum_{i = 1}^{n} v_{i} w_{i}$ .

Так как $f (A) b = 0$ , то последовательность

$(u, A^{i} b), i = 0, 1, 2, . . .,$

удовлетворяет линейному рекуррентному соотношению, характеристический многочлен которого равен $f (z)$ . Пусть $f_{u} (z)$ - характеристический многочлен самого короткого рекуррентного соотношения. Тогда $f (z) | f_{u} (z)$ . Действительно, если разделить с остатком

$f (z) = q (z) f_{u} (z) + r (z)$ , $d e g r (z) < d e g f_{u} (z)$

то из равенств

$0 = (u, f (A) b) = (u, q (A) f_{u} (A) b) + (u, r (A) b)$ ,

$(u, f_{u} (A) A^{j} b) = 0, j = 0, 1, 2, . . .,$

и минимальности $f_{u} (z)$ будет следовать, что $r (z) = 0$ . Поскольку свободный член $f (z)$ равен единице, то можно принять, что свободный член $f_{u} (z)$ равен единице.

Минимальный многочлен $f_{u} (z)$ для последовательности $(u, A^{i} b), i = 0, 1, 2, . . .,$ может быть получен с помощью алгоритма Берлекэмпа-МессиШаблон:Sfn по первым её $2 n$ членам. Существуют два метода решения исходной системы.

Первый метод. Выбирается случайный вектор $u (z)$ . Строится $f_{u} (z)$ и в предположении, что $f (z) = f_{u} (z)$ , находится $x$ по формуле

$x = - \sum_{i = 1}^{d} f [i] A^{i - 1} b$

Этим путём с достаточно высокой вероятностью можно найти решениеШаблон:Sfn.

Второй метод. Пусть $b_{0} = b, f_{1} (z) = f_{u_{1}} (z)$ для некоторого вектора $u_{1}$ . Если вектор $b_{1} = f_{1} (A) b_{0}$ равен 0, то находится $x$ по формуле

$x = - \sum_{i = 1}^{d} f [i] A^{i - 1} b$ (так как тогда $f_{1} (z) = f (z)$ ).

Если же $b_{1} \neq 0$ , то повторяется процедура, то есть выбирается случайный вектор $u_{2}$ и строится минимальный многочлен $f_{2} (z) = f_{u_{2}} (z)$ для последовательности $(u_{2}, A_{i} b_{1})$ . Если $b_{2} = f_{2} (A) b_{1} = 0$ , то $f (z) = f_{1} (z) f_{2} (z)$ и можно найти решение x по формуле

$x = - \sum_{i = 1}^{d} 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)$ - минимальный многочлен для последовательности ${(u_{k}, A^{i} b_{k - 1})}_{i} = {(u_{k}, f_{k - 1} (A) . . . f_{1} (A^{j}) b)}_{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_{i = 1}^{d} f [i] A^{i - 1} b$ Шаблон:Sfn.

Алгоритм 1

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

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

1 этап. Приравнивается $b_{0} = b, k = 0, y_{0} = 0, d_{0} = 0$ .

2 этап. Если $b_{k} = 0$ , то решение равно $x = - y_{k}$ , и алгоритм прекращает работу.

3 этап. Выбирается случайный вектор $u_{k + 1} \in K^{n}, u_{k + 1} \neq 0$ .

4 этап. Вычислить первые $2 (n - d_{k})$ членов последовательности ${(u_{k + 1}, A^{i} b_{k})}_{i = 0}^{\infty}$ .

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} + A y_{k + 1}$ ,

$d_{k + 1} = d_{k} + d e g f_{k + 1} (z)$ .

7 этап. Присвоить $k = k + 1$ и вернуться на второй этапШаблон:Sfn.

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

$\hat{f} (z) = \frac{f (z) - f (0)}{z}$ соответствует правой части формулы $x = - \sum_{i = 1}^{d} f [i] A^{i - 1} b$ без знака минус. При $k = 0$ выбирается $u_{1}$ , рассматривается $2 n$ членов последовательности ${(u_{1}, A^{i} b_{0})}_{i = 0, 1, 2}$ и находится $f_{1} (x)$ по алгоритму Берлекэмпа-Месси. Тогда $y_{1} = {\hat{f}}_{1} (A) b, b_{1} = b_{0} + A y_{1} = b + A \frac{f_{1} (A) - 1}{A} b = f_{1} (A) b, d_{1} = d e g 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}$ сохраняются. Теперь корректность алгоритма следует из раздела теория Шаблон:Sfn.

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

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

1 этап. Найти значение $A^{i} b, i = 0, 1, . . ., 2 n - 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, . . ., 2 n - 1$ при помощи первого этапа.

5 этап. Найти последовательность $(u_{k + 1}, g_{k} (A) A^{i} b), i = 0, 1, . . ., 2 n - 1 - d e g g_{k} (z)$ , можно использовать дискретное преобразование Фурье Шаблон:Sfn.

6 этап. Найти минимальный многочлен $f_{k + 1} (z)$ со свободным членом равным единице с помощью алгоритма Берлекэмпа-Месси.

7 этап. Присвоить $g_{k + 1} (z) = f_{k + 1} (z) g_{k} (z)$ .

8 этап. Увеличить $k$ на единицу. Если $d e g g_{k} (z) < n$ и $k < n$ , то возвратиться на 3 этап.

9 этап. Для многочлена $f (z) = g_{k} (z)$ с помощью найденных на первом этапе значений $A^{i} b$ отыскать решение $x$ системы с помощью формулы

$x = - \sum_{i = 1}^{d} f [i] A^{i - 1} b$ Шаблон:Sfn.

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

Обратим внимание, что фактически алгоритм работает также, как и алгоритм 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, . . ., 2 n - 1 - d e g (f_{k - 1} . . . f_{1})$ .

Алгоритм закончил работу при некотором значении параметра $k$ . Предположим, что $k < n, d e g g_{k} (z) = n$ . Так как $d e g f (z) ⩽ 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)$ . Поэтому и в данном случае подтверждена корректность работы алгоритмаШаблон:Sfn.

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

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

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

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

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

Позже появились различные модификации оригинального алгоритма, например блочный алгоритм Видемана Шаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Шаблон:^ Шаблон:Теоретико-числовые алгоритмы

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

Содержание

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

Задача

Теория

Алгоритм 1

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

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

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

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

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

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

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

Примечания

Литература

Навигация

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

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

Задача

Теория

Алгоритм 1

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

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

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

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

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

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

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

Примечания

Литература

Навигация

Поиск