>> > I wouldn't do it that way. Let M be your matrix. Work out the LCM l of >> > the denominators, and multiply the matrix by that to make it an integer >> > matrix N = l M. Then work out the determinant d of that integer matrix. >> > Next, the big step: use Gaussian elimination to find a matrix A (the >> > `adjugate matrix') such that A N = d I. This should be doable entirely >> > using integer arithmetic, and I think without needing any divisions. >> > Finally, we have l A M = d I, so (l/d A) M = I and l/d A is the inverse >> > you seek. >> > >> > Does that make sense? >> >> Absolutely! But there is nothing wrong with working out the inverse >> directly using fractions.Fraction arithmetic, I'd think. > > It'll work, certainly; but the Fraction implementation will have to do a > buttload of GCD computations that it wouldn't need to do if you worked > with plain integers. And GCDs are relatively hard, as arithmetical > computations go: the usual algorithms require either a number of > divisions (which are themselves rather costly) or a bitwise traversal of > one of the operands. > > A million entries seems nontrivial for a matrix, and Gaussian > elimination has cubic running time if I remember rightly; I suspect that > the transformations I describe would reduce the running time by a fair > amount. Of course, I might be drastically underestimating the > performance of modern hardware -- I often do -- so this may not be > especially relevant. Anyway, the possibility's there.
Okay, I see your point and I completely agree. Surely it will be faster to do it with integers, will give it a shot. Cheers, Daniel -- Psss, psss, put it down! - http://www.cafepress.com/putitdown -- http://mail.python.org/mailman/listinfo/python-list
