Complexity and Practicality in Computing with Integer Matrices
Mark Giesbrecht ( School of Computer Science Faculty of Mathematics University of Waterloo Waterloo, Ontario Canada )
Friday 26 May 2006, 15.00 sharp (s.t.), b-it 0.4
Contents
Exact computations with matrices of integers and rational numbers play a fundamental role in many mathematical computations. Highly tuned routines for solving such systems of equations, computing kernel bases, and determining invariants are at the heart of all modern symbolic computation systems.
Nonetheless, algorithms for these problems are far from completely understood and the last decade has seen many theoretical and practical improvements. Traditionally these algorithms have been viewed as a combination of an algebraic component (i.e., multiplication of n x n matrices) applied on integers of about n bits in length, and thus requiring O~(n4) machine operations overall. We will discuss recent algorithms which defy this dichotomy and require O~(n3) machine operations or less.
More recent work has focused on sparse matrices, for example where only O~(n) elements of an n by n integer matrix are non-zero. We demonstrate a new probabilistic method for solving such systems with cost O~(n2.5) machine operations. An implementation is presented in the generic linear algebra library LinBox, and demonstrates the practical benefits of this new method over the previous state of the art.