Modular algorithm for reducing matrices to the Smith normal form

M. A. Cherepnev

Lomonosov Moscow State University

Abstract: The paper gives a complete justification of the modular algorithm for reducing matrices to the Hermitian normal form, which enables one to construct a new modular algorithm for reducing to the Smith normal form that may simultaneously calculate the left matrix of the transformations. The main term in the estimate of the number of operations is $2(n^3\log D)$, where $n$ is the size and $D$ is the determinant (or a multiple of it) of the matrix under consideration.

Keywords: matrix transformation algorithm, normal forms of matrices, complexity of algorithms.

UDC: 519.612

Received: 27.09.2015

DOI: 10.4213/dm1378

 English version: Discrete Mathematics and Applications, 2017, 27:3, 143–147

Bibliographic databases:

• 
• 
• 
•