Блочный алгоритм Видемана

Блочный Видемана для вычисления ядра векторов матрицы алгоритм над конечным полем является обобщением Дона Копперсмита алгоритма Дуга Видемана.

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

Позволять $M$ быть $n\times n$ квадратная матрица над некоторым конечным полем F, пусть $x_{\mathrm {base} }$ быть случайным вектором длины $n$, и пусть $x=Mx_{\mathrm {base} }$. Рассмотрим последовательность векторов $S=\left[x,Mx,M^{2}x,\ldots \right]$ получается путем многократного умножения вектора на матрицу $M$; позволять $y$ быть любым другим вектором длины $n$и рассмотрим последовательность элементов конечного поля $S_{y}=\left[y\cdot x,y\cdot Mx,y\cdot M^{2}x\ldots \right]$

Мы знаем, что матрица $M$ имеет минимальный полином ; по теореме Кэли–Гамильтона мы знаем, что этот многочлен имеет степень (которую мы будем называть $n_{0}$) не более $n$. Сказать $\sum _{r=0}^{n_{0}}p_{r}M^{r}=0$. Затем $\sum _{r=0}^{n_{0}}y\cdot (p_{r}(M^{r}x))=0$; поэтому минимальный полином матрицы аннулирует последовательность $S$ и, следовательно, $S_{y}$.

Но алгоритм Берлекэмпа–Мэсси позволяет относительно эффективно вычислить некоторую последовательность $q_{0}\ldots q_{L}$ с $\sum _{i=0}^{L}q_{i}S_{y}[{i+r}]=0\;\forall \;r$. Мы надеемся, что эта последовательность, которая по своей конструкции уничтожает $y\cdot S$, фактически уничтожает $S$; так что у нас есть $\sum _{i=0}^{L}q_{i}M^{i}x=0$. Затем мы воспользуемся первоначальным определением $x$ сказать $M\sum _{i=0}^{L}q_{i}M^{i}x_{\mathrm {base} }=0$ и так $\sum _{i=0}^{L}q_{i}M^{i}x_{\mathrm {base} }$ является, надеюсь, ненулевым вектором ядра $M$.

Блочный алгоритм Видемана (или Копперсмита-Видемана)

Естественная реализация арифметики с разреженной матрицей на компьютере позволяет легко вычислить последовательность S параллельно для числа векторов, равного ширине машинного слова - действительно, обычно вычисление для такого количества векторов не занимает больше времени, чем для вычисления один. Если у вас несколько процессоров, вы можете вычислить последовательность S для различного набора случайных векторов параллельно на всех компьютерах.

Оказывается, что благодаря обобщению алгоритма Берлекэмпа-Мэсси для получения последовательности небольших матриц можно взять последовательность, полученную для большого числа векторов, и сгенерировать вектор ядра исходной большой матрицы. Вам нужно вычислить $y_{i}\cdot M^{t}x_{j}$ для некоторых $i=0\ldots i_{\max },j=0\ldots j_{\max },t=0\ldots t_{\max }$ где $i_{\max },j_{\max },t_{\max }$ нужно удовлетворить $t_{\max }>{\frac {d}{i_{\max }}}+{\frac {d}{j_{\max }}}+O(1)$ и $y_{i}$ представляют собой серию векторов длины n; но на практике можно взять $y_{i}$ как последовательность единичных векторов и просто выпишите первые $i_{\max }$ записи в ваших векторах в каждый момент времени t .

Расчет инвариантного коэффициента

Блочный алгоритм Видемана можно использовать для вычисления ведущих инвариантных факторов матрицы, т. е. крупнейших блоков нормальной формы Фробениуса . Данный $M\in F_{q}^{n\times n}$ и $U,V\in F_{q}^{b\times n}$ где $F_{q}$ является конечным полем размера $q$, вероятность $p$ что ведущий $k<b$ инвариантные факторы $M$ сохраняются в $\sum _{i=0}^{2n-1}UM^{i}V^{T}x^{i}$ является

$p\geq {\begin{cases}1/64,&{\text{if }}b=k+1{\text{ and }}q=2\\\left(1-{\frac {3}{2^{b-k}}}\right)^{2}\geq 1/16&{\text{if }}b\geq k+2{\text{ and }}q=2\\\left(1-{\frac {2}{q^{b-k}}}\right)^{2}\geq 1/9&{\text{if }}b\geq k+1{\text{ and }}q>2\end{cases}}$.

Ссылки

• Видеманн, Д., «Решение разреженных линейных уравнений над конечными полями», IEEE Trans. Инф. Теория ИТ-32, стр. 54-62, 1986.

• Д. Копперсмит, Решение однородных линейных уравнений над GF (2) с помощью блочного алгоритма Видемана, Math. Комп. 62 (1994), 333-350.

• Отчет об исследовании Виллара 1997 года « Исследование блочного алгоритма Видемана Копперсмита с использованием матричных полиномов » (обложка на французском языке, но содержание на английском языке) является разумным описанием.

• В статье Томе « Субквадратичное вычисление векторных полиномов и улучшение блочного алгоритма Видемана » используется более сложный алгоритм на основе БПФ для вычисления векторных полиномов и описывается практическая реализация с i _max = j _max = 4, используемая для вычисления ядра. вектор матрицы элементов размером 484603 × 484603 по модулю 2 ⁶⁰⁷ −1 и, следовательно, для вычисления дискретных логарифмов в поле GF (2 ⁶⁰⁷ ).