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