ความซับซ้อนเชิงเส้นของรูปแบบจำกัดสองมิติ เช่น รหัส QR

การเกิดซ้ำเชิงเส้นสองมิตินั้นซับซ้อนกว่าเล็กน้อยในทางพีชคณิต

แนวคิดที่สอดคล้องกับความซับซ้อนเชิงเส้นในแง่หนึ่งก็คือระดับ $(n,m)$ ของพหุนามที่สร้างดีกรีน้อยที่สุดของฟอร์ม $$ 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 $$ ซึ่งจะสอดคล้องกับการเกิดซ้ำเชิงเส้น 2 มิติ $$ 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} $$ ที่ไหน $t,t'$ เป็นดัชนีในสองมิติ

Sakata ได้สรุปอัลกอริทึม Berlekamp Massey (BMA) เป็น 2 และจากนั้นเป็น N มิติ ดู ที่นี่ (ดูเหมือนจะเปิดเผยต่อสาธารณะ). จากบทคัดย่อ:

เรานำเสนออัลกอริทึมสำหรับการค้นหาชุดขั้นต่ำของความสัมพันธ์ที่เกิดซ้ำเชิงเส้นสองมิติที่สามารถสร้างอาร์เรย์สองมิติที่มีขอบเขตจำกัด นี่เป็นส่วนขยายสองมิติของอัลกอริทึม Berlekamp-Massey สำหรับการสังเคราะห์ shift-register ความซับซ้อนของการคำนวณสำหรับอาร์เรย์ที่มีขนาด $n$ เป็น $O(n^2)$ ภายใต้สมมติฐานที่สมเหตุสมผล นอกจากนี้ เรายังระบุความสัมพันธ์ที่ชัดเจนระหว่างอัลกอริทึมของเรากับฐานของ Gröbner ของอุดมคติพหุนามแบบทวินาม โดยที่พหุนามสอดคล้องกับความสัมพันธ์แบบหนึ่งต่อหนึ่งกับความสัมพันธ์ที่เกิดซ้ำเชิงเส้น

เหตุผลที่ซับซ้อนคือ (ขึ้นอยู่กับการโบกมือ) สำหรับฟิลด์ที่ จำกัด $\mathbb{F}$ วงแหวนพหุนามตัวแปรเดียว $\mathbb{F}[x]$ อุดมคติทั้งหมดเป็นหลัก (มีตัวสร้างพหุนามตัวเดียว) เพื่อให้ กทม. ทำงานได้ ก็เพียงพอแล้วที่จะหาเครื่องกำเนิดระดับขั้นต่ำหนึ่งเครื่อง ในหลายตัวแปร ไม่ใช่อุดมคติทั้งหมดของ $\mathbb{F}[x_1,\ldots,x_n]$ เป็นอาจารย์ใหญ่

คำจำกัดความของระดับตัวแปรสองระดับและการเรียงลำดับระดับของคำศัพท์เป็นอีกประเด็นหนึ่ง แต่สามารถทำได้ผ่านการเรียงลำดับพจนานุกรม