Recurențele liniare bidimensionale sunt puțin mai complexe din punct de vedere algebric.
Conceptul corespunzător complexității liniare ar fi într-un fel gradul $(n,m)$ a polinomului generator de grad minim al formei
$$
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
$$
care ar corespunde recurenței liniare 2D
$$
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, t'+j}
$$
Unde $t,t'$ sunt indicii în cele două dimensiuni.
Sakata a generalizat algoritmul Berlekamp Massey (BMA) la 2, iar apoi la N dimensiuni; Vedea Aici (pare a fi disponibil public). Din rezumat:
Prezentăm un algoritm pentru găsirea unui set minim de relații liniare recurente bidimensionale capabile să genereze o matrice bidimensională finită prescrisă. Aceasta este o extensie bidimensională a algoritmului Berlekamp-Massey pentru sintetizarea unui registru de deplasare cu feedback liniar cel mai scurt, capabil să genereze o anumită secvență finită. Complexitatea calculului pentru o serie de dimensiuni $n$ este $O(n^2)$ în baza unor ipoteze rezonabile. Mai mult, clarificăm o relație între algoritmul nostru și bazele Gröbner ale idealurilor polinomiale bivariate, unde polinoamele corespund unu-la-unu relațiilor liniare recurente.
Motivul pentru care sunt complexe este că (până la unele fluturi de mână) pentru un câmp finit $\mathbb{F}$ singurul inel polinom variabil $\mathbb{F}[x]$ toate idealurile sunt principale (au un singur generator de polinom). Deci, pentru ca BMA să funcționeze, este suficient să găsiți un generator de grad minim. În mai multe variabile, nu toate idealurile de $\mathbb{F}[x_1,\ldots,x_n]$ sunt principale.
Definiția a două grade variabile și ordonarea gradelor de termeni este o altă problemă, dar aceasta se poate face prin ordonarea lexicografică, de exemplu.
