Computing bases in Hermite normal form of lattices of integer relations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917473095254016 |
|---|---|
| author | Labahn, George Storjohann, Arne |
| author_facet | Labahn, George Storjohann, Arne |
| contents | Given a full column rank $M \in \Z^{\ell \times m}$ and an $F \in \Z^{n \times m}$ we present an algorithm to compute the $n \times n$ basis in Hermite form of the integer lattice comprised of all rows $p \in \Z^{1 \times n}$ such that $pF \in \Z^{1 \times m}$ is in the integer lattice generated by the rows of $M$. The algorithm is randomized of the Las Vegas type, that is, it can fail with probability at most $1/2$, but if fail is not returned it guarantees to produce the correct result. When $M$ is square and $F=I_m$, then the computed basis is the Hermite normal form of $M$, and the algorithm uses about the same number of bit operations as required to multiply together two matrices of the same dimension and size of entries as $M$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_07784 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Computing bases in Hermite normal form of lattices of integer relations Labahn, George Storjohann, Arne Data Structures and Algorithms Computational Complexity Symbolic Computation Rings and Algebras 68Q25, 68W30, 15A21, 15A36 I.1.2; F.2.2 Given a full column rank $M \in \Z^{\ell \times m}$ and an $F \in \Z^{n \times m}$ we present an algorithm to compute the $n \times n$ basis in Hermite form of the integer lattice comprised of all rows $p \in \Z^{1 \times n}$ such that $pF \in \Z^{1 \times m}$ is in the integer lattice generated by the rows of $M$. The algorithm is randomized of the Las Vegas type, that is, it can fail with probability at most $1/2$, but if fail is not returned it guarantees to produce the correct result. When $M$ is square and $F=I_m$, then the computed basis is the Hermite normal form of $M$, and the algorithm uses about the same number of bit operations as required to multiply together two matrices of the same dimension and size of entries as $M$. |
| title | Computing bases in Hermite normal form of lattices of integer relations |
| topic | Data Structures and Algorithms Computational Complexity Symbolic Computation Rings and Algebras 68Q25, 68W30, 15A21, 15A36 I.1.2; F.2.2 |
| url | https://arxiv.org/abs/2605.07784 |