Reduction of Smith normal form transformation matrices

DOI10.1007/S00607-004-0104-0MaRDI QIDQ2487958zbMATH OpenOpenAlexFDO

Authors Gerold Jäger

Publication date 17 August 2005

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00607-004-0104-0

zbMATH Keywords

algorithmlattice basis reductionlinear Diophantine equationsmatrices of integersnumerical resultsreduction matricesSmith normal form

Mathematics Subject Classification ID

Linear Diophantine equations (11D04) Canonical forms, reductions, classification (15A21) Matrices of integers (15B36) Direct numerical methods for linear systems and matrix inversion (65F05)

Review text

A matrix \(A\in \mathbb{Z}^{m\times n}\) can be reduced to Smith normal form \(C\) by unimodular matrices \(U\in GL_m(\mathbb{Z})\) and \(V\in GL_n(\mathbb{Z})\) such that \(A=UCV\). If \(A\) has rank \(r\), then \(C\) is zero except for the first \(r\) diagonal elements which satisfy: \(C_{ii}\) divides \(C_{i+1,i+1}\), \(i=1,\dots,r-1\). The \(U\) and \(V\) are not unique. For the application to the solution of linear Diophantine equations it is essential that the entries of \(U\) and \(V\) are as small as possible. In this paper, the sets of reduction matrices \(U\) and \(V\) are characterized, and an algorithm is given to reduce the size of a given pair of reduction matrices. The algorithm is based on optimization techniques studied by \textit{C. P. Schnorr, M. Euchner} [Math. Program. 66, No. 2(A), 181--199 (1994; Zbl 0829.90099)] and \textit{A. K. Lenstra, H. W. Lenstra} jun. and \textit{László Lovász} [Math. Ann. 261, 515--534 (1982; Zbl 0488.12001)]. Numerical results for a wide class of test matrices illustrate the performance of the algorithm.

Recommendations

• scientific article; zbMATH DE number 1118055
• scientific article; zbMATH DE number 3843067
• scientific article; zbMATH DE number 1254302
• Modular algorithm for reducing matrices to the Smith normal form
• Publication:4489154

Cites work

• Asymptotically Fast Triangularization of Matrices over Rings
• Extended GCD and Hermite Normal Form Algorithms via Lattice Basis Reduction
• Factoring polynomials with rational coefficients
• scientific article; zbMATH DE number 3987367 (Why is no real title available?)
• scientific article; zbMATH DE number 534859 (Why is no real title available?)
• Integer matrix diagonalization
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• Lattice basis reduction: Improved practical algorithms and solving subset sum problems
• On Systems of Linear Diophantine Equations
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Recognizing badly presented \(Z\)-modules

Cited in

(10)

• Recognizing badly presented \(Z\)-modules
• Modular algorithm for reducing matrices to the Smith normal form
• Smith meets Smith: Smith normal form of Smith matrix
• Reduction of a set of matrices over a principal ideal domain to the Smith normal forms by means of the same one-sided transformations
• Solving linear Diophantine matrix equations using the Smith normal form (more or less)
• scientific article; zbMATH DE number 3843922 (Why is no real title available?)
• Real and integer extended rank reduction formulas and matrix decompositions: A review
• scientific article; zbMATH DE number 1157643 (Why is no real title available?)
• Selected applications of LLL in number theory
• An algorithm for the arithmetic classification of multilattices

This page was built for publication: Reduction of Smith normal form transformation matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2487958)