2024/08/13 by Kim-Manuel Klein, Klein, Kim-Manuel, Janina Reuter +1
Computer Science · Engineering · Mathematics · #90C99 #Advanced Numerical Analysis Techniques #Algebraic Geometry (math.AG) #Algorithm #Artificial intelligence #Basis (linear algebra) #Computation #Computational Geometry and Mesh Generation #Computer science #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #Euclidean algorithm #Euclidean distance #Euclidean geometry #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Generalization #Geometry #Lattice (music) #Mathematical analysis #Mathematics #Physics
paper · pdf · doi:10.48550/arxiv.2408.06685
openalex publication_date 2024/08/13 · openalex created_date 2024/09/11 · openalex updated_date 2026/07/28
The Euclidean algorithm is the oldest algorithms known to mankind. Given two integral numbers a1 and a2, it computes the greatest common divisor (gcd) of a1 and a2 in a very elegant way. From a lattice perspective, it computes a basis of the sum of two one-dimensional lattices a1 ℤ and a2 ℤ as gcd(a1,a2) ℤ = a1 ℤ + a2 ℤ. In this paper, we show that the classical Euclidean algorithm can be adapted in a very natural way to compute a basis of a general lattice L(A1, … , An) given vectors A1, … , An ∈ ℤd with n> rank(a1, … ,ad). Similar to the Euclidean algorithm, our algorithm is very easy to describe and implement and can be written within 12 lines of pseudocode. As our main result, we obtain an algorithm to compute a lattice basis for given vectors A1, … , An ∈ ℤd in time (counting bit operations) LS + O((n-d)d2 ⋅ log(||A||), where LS is the time required to obtain the exact fractional solution of a certain system of linear equalities. The analysis of the running time of our algorithms relies on fundamental statements on the fractionality of solutions of linear systems of equations. So far, the fastest algorithm for lattice basis computation was due to Storjohann and Labhan [SL96] having a running time of O(ndωlog ||A||). For current upper bounds of LS, our algorithm has a running time improvement of a factor of at least d0.12 over [SL96]. Our algorithm is therefore the first general algorithmic improvement to this classical problem in nearly 30 years. At last, we present a postprocessing procedure which yields an improved size bound of √(d) ||A|| for vectors of the resulting basis matrix.