Modular algorithm for reducing matrices to the Smith normal form
Mikhail Alekseevich Cherepnev · Discrete Mathematics and Applications · 2017
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.