Inverting integer and polynomial matrices
Arne Storjohann (University of Waterloo, Canada)
The exact inverse of an integer or polynomial matrix of dimension n can require a factor of n more space to write down than the input matrix. The cost of traditional inversion methods, such as Chinese remaindering or Newton iteration, cost a factor of n more than this. In this talk I survey three recent improvements in computing and representing the inverse. The first is the double-divide and conquer method of Jennearod & Villard (2005), the first nearly optimal algorithm in the case of generic polynomial matrices. The second is the sparse inverse expansion formula, which gives a representation as a straight line formula whose size is only a logarithmic factor larger than the input matrix. Finally, I will discuss the outer product adjoint formula, which gives a Las Vegas algorithm to compute the exact inverse of a well conditioned integer matrix in nearly optimial time.
Talk slides (PDF).