PhD Seminar • Symbolic Computation — Fast Computation of the Smith Form of a Nonsingular Integer Matrix

Wednesday, July 8, 2020 3:00 pm - 3:00 pm EDT (GMT -04:00)

Please note: This PhD seminar will be given online.

Stavros Birmpilis, PhD candidate
David R. Cheriton School of Computer Science

Any nonsingular matrix $A \in \mathbb{Z}^{n\times n}$ is unimodularly equivalent to a unique diagonal matrix $S = diag(s_1, s_2, \ldots, s_n)$ in Smith form. The diagonal entries, the invariant factors of $A$, are positive with $s_1 \mid s_2 \mid \cdots \mid s_n$, and unimodularly equivalent means that there exist unimodular (with determinant ±1) matrices $U, V \in \mathbb{Z}^{n\times n}$ such that $UAV = S$.

We present a Las Vegas randomized algorithm to compute the Smith normal form of a nonsingular integer matrix. For an $A \in \mathbb{Z}^{n \times n}$, the algorithm requires $O(n^3 (\log n + \log ||A||)^2 (\log n)^2)$ bit operations using standard integer and matrix arithmetic, where $||A||= \max_{ij} |A_{ij}|$ denotes the largest entry in absolute value. Fast integer and matrix multiplication can also be used, establishing that the Smith form can be computed in about the same number of bit operations as required to multiply two matrices of the same dimension and size of entries as the input matrix.