Indeed we know of no prior discussion of fast exact methods for this problem in the sparse case. Sufficient background will be provided for the talk to be useful to those with modest background in linear algebra. Let A be a matrix with rational entries in a black box representation. A over the rational numbers. However, correctness is assured.
Bad luck can only affect the run time.
The method involves computations over finite fields. We'll discuss the issues that arise concerning the choice of primes, and the construction of unitary preconditioners. Work is under way to apply this technique to a very sparse integer matrix whose size is about 250 by 300,000 . It is possible that the solution in this case will resolve a 40 year old conjecture concerning the existence of a certain block design. With this example in mind, we'll offer a variant of the algorithm for the case when the rank of the matrix is small.