Двумерные линейные повторения немного сложнее алгебраически.
Понятие, соответствующее линейной сложности, в некотором смысле было бы степенью $(н,м)$ производящего многочлена минимальной степени вида
$$
x^{n}y^m- \sum_{0\leq i\leq n-1} \sum_{0\leq j\leq m-1} a_{i,j} x^i y^j
$$
что соответствовало бы двумерному линейному повторению
$$
s_{t+n,t'+m}=\sum_{0\leq i\leq n-1} \sum_{0\leq j\leq m-1} a_{i,j} s_{t+i, т'+j}
$$
куда $т,т'$ являются индексами в двух измерениях.
Саката обобщил алгоритм Берлекэмпа Мэсси (BMA) до 2, а затем и до N измерений; Видеть здесь (кажется общедоступным). Из аннотации:
Мы представляем алгоритм нахождения минимального набора двумерных линейных рекуррентных отношений, способных генерировать заданный конечный двумерный массив. Это двумерное расширение алгоритма Берлекампа-Месси для синтеза кратчайшего регистра сдвига с линейной обратной связью, способного генерировать заданную конечную последовательность. Сложность вычислений для массива размером $n$ является $ О (п ^ 2) $ при некоторых разумных предположениях. Кроме того, мы проясняем некоторую связь между нашим алгоритмом и базами Грёбнера двумерных полиномиальных идеалов, где многочлены взаимно однозначно соответствуют линейным рекуррентным отношениям.
Причина, по которой они сложны, заключается в том, что (с точностью до некоторого махания рукой) для конечного поля $\mathbb{F}$ кольцо полиномов одной переменной $\mathbb{F}[x]$ все идеалы главные (имеют одну полиномиальную образующую). Таким образом, для работы БМА достаточно найти один образующий минимальной степени. При многих переменных не все идеалы $\mathbb{F}[x_1,\ldots,x_n]$ являются главными.
Определение степени двух переменных и упорядочение степеней терминов - это еще одна проблема, но это можно сделать, например, с помощью лексикографического упорядочения.
