research-article

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

Authors:

Stavros Birmpilis,

Arne StorjohannAuthors Info & Claims

ACM Transactions on Algorithms, Volume 19, Issue 4

Article No.: 37, Pages 1 - 36

https://doi.org/10.1145/3617996

Published: 14 October 2023 Publication History

Abstract

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(n³ (log n + log ||A||)²(log n)²) bit operations, where ||A||= max _ij |A_ij| 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 (n³ log ||A||)^1+o(1) bit operations, where the exponent “+ o(1)” captures additional factors c₁ (log n)^c2 (loglog||A||)^c3 for positive real constants c₁,c₂,c₃.

References

[1]

J. Alman and V. V. Williams. 2021. A refined laser method and faster matrix multiplication. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA’21), 522–539. DOI:

[2]

E. Bach and J. Shallit. 1996. Algorithmic Number Theory, volume 1: Efficient Algorithms. MIT Press.

Digital Library

[3]

B. Beckermann and G. Labahn. 1994. A uniform approach for the fast computation of matrix–type Padé approximants. SIAM J. Matrix Anal. Appl. 15, 3 (1994), 804–823.

Digital Library

[4]

B. Beckermann, G. Labahn, and G. Villard. 1999. Shifted normal forms of polynomial matrices. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC’99), S. Dooley (Ed.). ACM Press, New York, 189–196.

[5]

S. Birmpilis, G. Labahn, and A. Storjohann. 2020. A Las Vegas algorithm for computing the Smith form of a nonsingular integer matrix. In Proceedings International Symposium on Symbolic and Algebraic Computation: ISSAC’20, New York, NY, USA, ACM, 38–45.

[6]

S. Birmpilis, G. Labahn, and A. Storjohann. 2023. A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrix. J. Symbol. Comput. 116 (2023), 146–182.

Digital Library

[7]

T.-W. J. Chou and G. E. Collins. 1982. Algorithms for the solutions of systems of linear diophantine equations. SIAM J. Comput. 11 (1982), 687–708.

Digital Library

[8]

G. E. Collins. 1968. Computing Time Analyses for Some Arithmetic and Algebraic Algorithms. Technical Report 36, University of Wisconsin—Madison.

[9]

P. D. Domich, R. Kannan, and L. E. Trotter, Jr. 1987. Hermite normal form computation using modulo determinant arithmetic. Math. Operat. Res. 12, 1 (1987), 50–59.

Digital Library

[10]

J. L. Hafner and K. S. McCurley. 1989. A rigorous subexponential algorithm for computation of class groups. J. Am. Math. Soc., 2 (1989), 837–850.

[11]

D. Harvey and J. van der Hoeven. 2021. Integer multiplication in time \({O}(n \log n)\). Ann. Math. 193 (2021), 563–617.

[12]

C. Hermite. 1851. Sur l’introduction des variables continues dans la théorie des nombres. J. Reine Angew. Math. 41 (1851), 191–216.

[13]

J. A. Howell. 1986. Spans in the module \((\mathbb {Z}_m)^s\). Lin. Multilin. Algebr. 19 (1986), 67—77.

[14]

E. Hubert and G. Labahn. 2013. Scaling invariants and symmetry reduction of dynamical systems. Found. Comput. Math. 13, 4 (2013), 479–516.

Digital Library

[15]

C. S. Iliopoulos. 1989. Worst-case complexity bounds on algorithms for computing the canonical structure of finite abelian groups and the Hermite and Smith normal forms of an integer matrix. SIAM J. Comput. 18, 4 (1989), 658–669.

Digital Library

[16]

R. Kannan and A. Bachem. 1979. Polynomial algorithms for computing the Smith and Hermite normal forms of and integer matrix. SIAM J. Comput. 8, 4 (1979), 499–507.

Digital Library

[17]

G. Labahn, V. Neiger, and W. Zhou. 2017. Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix. J. Complex 42 (2017), 44–71.

[18]

R. Liu and Y. Pan. 2019. Computing Hermite normal form faster via solving system of linear equations. In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC’19). ACM, New York, NY, 283–290.

[19]

D. Micciancio and B. Warinschi. 2001. A linear space algorithm for computing the Hermite normal form. In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC’01). B. Mourrain (Ed.), ACM Press, New York, NY, 231—236.

[20]

C. Pauderis and A. Storjohann. 2013. Computing the invariant structure of integer matrices: Fast algorithms into practice. In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC’13). ACM, New York, NY, 307–314.

[21]

C. Pernet and W. Stein. 2010. Fast computation of Hermite normal forms of integer matrices. J. Number Theory 130, 7 (2010), 1675–1683.

[22]

A. Schrijver. 1998. Theory of Linear and Integer Programming. John Wiley & Sons.

Digital Library

[23]

A. Storjohann. 2000. Algorithms for Matrix Canonical Forms. PhD thesis, Swiss Federal Institute of Technology, ETH–Zurich.

[24]

A. Storjohann. 2015. On the complexity of inverting integer and polynomial matrices. Comput. Complex. 24, 4 (2015), 777—821.

Digital Library

[25]

A. Storjohann and G. Labahn. 1996. Asymptotically fast computation of Hermite normal forms of integer matrices. In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC’96), Y. N. Lakshman (Ed.). ACM Press, New York, NY, 259–266.

[26]

A. Storjohann and T. Mulders. 1998. Fast algorithms for linear algebra modulo N. In Proceedings of the European Symposium on Algorithms (ESA’98), G. Bilardi, G. F. Italiano, A. Pietracaprina, and G. Pucci (Eds.), LNCS 1461, Springer Verlag, Berlin, 139–150.

[27]

W. Zhou and G. Labahn. 2012. Efficient algorithms for order basis computation. J. Symbol. Comput. 47, 7 (2012), 793–819.

Digital Library

[28]

W. Zhou and G. Labahn. 2013. Computing column bases of polynomial matrices. In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC’13). ACM Press, Boston, MA, 379–388.

[29]

W. Zhou, G. Labahn, and A. Storjohann. 2012. Computing minimal nullspace basis. In Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC’12), J. van der Hoeven and M. van Hoeij (Eds.), ACM Press, New York, NY, 366–373.

Cited By

Cheng YFeng YPan Y(2024)Embedding Integer Lattices as Ideals into Polynomial RingsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669688(170-179)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669688

Index Terms

A Cubic Algorithm for Computing the Hermite Normal Form of a Nonsingular Integer Matrix
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Linear algebra algorithms
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Integer matrix rank certification
ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation

Let M = [A B/C D] be a 2n x 2n integer matrix with the principal block A square and nonsingular. An algorithm is presented to determine if the Schur complement D--CA^--1 B is equal to the zero matrix in O~(n^ω log ||M||) bit operations. Here, ω is the ...
On the complexity of inverting integer and polynomial matrices

An algorithm is presented that probabilistically computes the exact inverse of a nonsingular n n integer matrix A using $${({n^3(\log||A||+\log \kappa(A)))}^{1+o(1)}}$$(n3(log||A||+log (A)))1+o(1) bit operations. Here, $${||A||= \max_{ij}|A_{ij}|}$$||A||...
A Las Vegas algorithm for computing the smith form of a nonsingular integer matrix
ISSAC '20: Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation

We present a Las Vegas randomized algorithm to compute the Smith normal form of a nonsingular integer matrix. For an A ∈ Z^n×n, the algorithm requires O(n³(log n + log ||A||)² (log n)²) bit operations using standard integer and matrix arithmetic, where ||...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 19, Issue 4

October 2023

255 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3614237

Editor:
Edith Cohen
Google Research, USA and Tel Aviv University, Israel

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 October 2023

Online AM: 31 August 2023

Accepted: 26 August 2023

Revised: 16 August 2023

Received: 23 September 2022

Published in TALG Volume 19, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
107
Total Downloads

Downloads (Last 12 months)70
Downloads (Last 6 weeks)2

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cheng YFeng YPan Y(2024)Embedding Integer Lattices as Ideals into Polynomial RingsProceedings of the 2024 International Symposium on Symbolic and Algebraic Computation10.1145/3666000.3669688(170-179)Online publication date: 16-Jul-2024
https://dl.acm.org/doi/10.1145/3666000.3669688

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents