From: zhendong wan Date: Fri Jun 25, 2004 11:11:00 AM America/Denver Cc: Dave Saunders Subject: About Problem 7. I have a new fast exact solution to problem 7(the order 20000 matrix with primes on the diagonal, etc.). Recall that members of the LinBox group produced the exact rational solution twice, using parallel and sequential methods (with Chinese remaindering and Dixon lifting, respectively). The solution is a quotient of two 97,389 digit numbers. The sequential version required 12.5 days of computation. With a new algorithm the exact result has now been computed on one processor in 25 minutes on a 1.9GHz PC (and in 11 minutes on a higher performance Xeon machine). The best current time is over 1500 times better than that of 2 years ago! The new method is a numeric/symbolic combination which works by a careful successive refinement. If the full exact rational solution is not needed, the computing time can be in proportion to the number of digits desired. Given a matrix A and a numeric solver of Ax = b that gets some leading bits of x correct (for a suitable range of b's), the algorithm can produce the exact solution in O~(n) solver calls + O~(n^2) additional work. For problem 7, memory is not required for A inverse, a dense order 20000 matrix, as it was with the Dixon lifting method. Memory used was only a few megabytes (for the sparse representation of the input matrix, a few vectors, and a small matrix block), thus allowing computation on an ordinary PC. You can post this note at your website if you like. There's a paper in the works. I'll have a readable draft soon and send it to you. Best, Zhendong Wan