Scrierea unui răspuns, astfel încât acesta să nu rămână fără răspuns, deși HNF a fost menționat în comentarii.
Forma normală Hermite este modalitatea standard de a reduce un grup electrogen la o bază.
Aceasta înseamnă că este modalitatea standard de a calcula mai multe operații pe rețele (care sunt ușor de exprimat în termeni de vectori de bază), de exemplu
$L+L'$ (din care exemplul dvs. este un caz special), sau
$L\cap L'$ (acest lucru este mai puțin evident și necesită dualitate).
Vedeți problemele ușoare ale grilajului aceste note.
Ai comentat
Se pare că calcularea eficientă a formei normale Hermite nu este banală...
Acest lucru este (un fel de) adevărat, dar non-trivial este departe de a fi „greu”.
citez din note
Nu este greu să găsești un algoritm care să calculeze HNF-ul unei matrice efectuând doar un număr polinomial de operații. Cu toate acestea, o soluție naivă la această problemă poate duce la un timp de rulare superpolinom, deoarece numerele din calculele intermediare pot deveni cu ușurință foarte mari.
Notele legate includ pseudocod pentru o implementare HNF acela al timpului de rulare polinomial (asigurându-vă că valorile intermediare rămân limitate).
Este poate puțin mai complex decât LLL, dar într-adevăr nu cu mult --- ambii sunt algoritmi pe care m-aș aștepta ca o licență junior/senior să poată implementa fără prea mult efort.
Desigur, puteți depune mai mult efort pentru a obține lucruri mai eficiente practic.
Vezi această lucrare de Pernet și Stein. Deoarece Stein este fondatorul Sage CAS, îmi imaginez că acest lucru este destul de aproape de ceea ce Sage a implementat, cel puțin în jurul anului 2011.
Acest algoritm este poate genul de algoritm „non-trivial” pe care l-ați avut în minte. Dar, pe de altă parte, implementările eficiente ale LLL devin în mod similar non-triviale (am auzit cu câțiva ani în urmă că LLL era simultan timp polinom și, probabil, greu de rulat pe rețele mari, să zicem despre dimensiunea 1k+).
Merită menționat că se pare că există unele lucrări care calculează HNF-uri folosind LLL ca subrutină, vezi de exemplu acest.
