A Cubic Algorithm for Computing the Hermite Normal Form of a Nonsingular Integer Matrix

A Las Vegas randomized algorithm is given to compute the Hermite normal form of a nonsingular integer matrix A of dimension n. The algorithm uses quadratic integer multiplication and cubic matrix multiplication and has running time bounded by O(n3 (log n + log ||A||)2(log n)2) bit operations, where...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on algorithms 2023-10, Vol.19 (4), p.1-36, Article 37
Main Authors: Birmpilis, Stavros, Labahn, George, Storjohann, Arne
Format: Article
Language:English
Subjects:
Computing methodologies
Design and analysis of algorithms
Linear algebra algorithms
Theory of computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A Las Vegas randomized algorithm is given to compute the Hermite normal form of a nonsingular integer matrix A of dimension n. The algorithm uses quadratic integer multiplication and cubic matrix multiplication and has running time bounded by O(n3 (log n + log ||A||)2(log n)2) bit operations, where ||A||= max ij |Aij| denotes the largest entry of A in absolute value. A variant of the algorithm that uses pseudo-linear integer multiplication is given that has running time (n3 log ||A||)1+o(1) bit operations, where the exponent “+ o(1)” captures additional factors c1 (log n)c2 (loglog||A||)c3 for positive real constants c1,c2,c3.
ISSN:1549-6325
1549-6333
DOI:10.1145/3617996