Extended GCD and Hermite Normal Form Algorithms via Lattice Basis Reduction (Q4228028)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1247901
Language Label Description Also known as
default for all languages
No label defined
    English
    Extended GCD and Hermite Normal Form Algorithms via Lattice Basis Reduction
    scientific article; zbMATH DE number 1247901

      Statements

      Extended GCD and Hermite Normal Form Algorithms via Lattice Basis Reduction (English)
      0 references
      0 references
      0 references
      0 references
      23 August 1999
      0 references
      extended gcd computation
      0 references
      lattice base reduction
      0 references
      Hermite normal form computation
      0 references
      0 references
      0 references
      0 references
      The extended gcd problem is to find, given integers \(s_1,\ldots,s_m\), an integer multiplier vector \(x=(x_1,\ldots,x_m)\) of small Euclidean length such that \(x_1 s_1 + \cdots + x_m s_m = \gcd(s_1,\ldots,s_m)\). The paper proposes an algorithm based on LLL lattice basis reduction [\textit{A. K. Lenstra, H. W. Lenstra jun.} and \textit{L. Lovász}, Math. Ann. 261, 515-534 (1982; Zbl 0488.12001)]. The algorithm does not always produce the shortest multiplier, even when \(m=3\). However, for \(m=3\) the algorithm can be modified to a practical polynomial algorithm for finding an optimal solution. Generally, the solution \(x\) produced satisfies \[ | x| ^2 \leq 1 + \tfrac 14(m-1)y^{m-2}| s| ^2 \] where \(y\geq 4/3\). The method is generalized to the problem of producing small unimodular transformation matrices for computing the Hermite normal form of an integer matrix.
      0 references

      Identifiers