Bonn-Aachen International Center
for Information Technology





city life
cosec >students >Teaching >Summer 2006 

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


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.

Imprint, webmaster & more