University of Waterloo
Deterministic Unimodularity Certification and Applications for Integer Matrices
Abstract
dc:description.abstractThe asymptotically fastest algorithms for many linear algebra problems on integer matrices, including solving a system of linear equations and computing the determinant, use high-order lifting. For a square nonsingular integer matrix A, high-order lifting computes B congruent to A^{-1} mod X^k and matrix R with AB = I + RX^k for non-negative integers X and k. Here, we present a deterministic method -- "double-plus-one" lifting -- to compute the high-order residue R as well as a succinct representation of B. As an application, we give a fully deterministic algorithm to certify the unimodularity of A. The cost of the algorithm is O((log n) n^{omega} M(log n + log ||A||)) bit operations, where ||A|| denotes the largest entry in absolute value, M(t) the cost of multiplying two integers bounded in bit length by t, and omega the exponent of matrix multiplication. Unimodularity certification is then applied to give a heuristic, but certified, algorithm for computing the determinant and Hermite normal form of a square, nonsingular integer matrix. Though most effective on random matrices, a highly optimized implementation of the latter algorithm demonstrates the techniques' effectiveness across a variety of inputs: empirical running times grow as O(n^3log n). A comparison against the fastest known Hermite normal algorithms -- those available in Sage and Magma -- show our implementation is, in all cases, highly competitive, and often surpasses existing, state-of-the-art implementations.
Degree
thesis:*- Grantor dc:publisher
- University of Waterloo
- Year dc:date.issued
- 2013
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Pauderis, Colton
Subjects
dc:subject × 1Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/10012/7895