Two fundamental problems in computational linear algebra.
Michael Monagan, CECM.Wednesday July 15th, 2009, in K9509 at 3:30pm.
We consider two fundamental computational problems in linear algebra. The first problem is how to compute the determinant of a matrix A where the entries of A are in an integral domain D. The algorithm I'll present is known as the Bareiss fraction-free algorithm. It was independently discovered by Edmonds in 1967 and Bareiss in 1968 although Bareiss states that it was known by Jordan. The second problem is how to solve the linear system Ax=b for x over the rationals. Here I'll present two modular methods. The first combines Chinese remaindering with Cramer's rule -- yes, Cramer's rule can actually be useful in computation! The second, the faster method, uses a p-adic lifting approach and rational number reconstruction that was introduced last time. Both of these computational problems have a very long history starting with Gauss and yet are still not completely solved.