Daniel Fetchinson <fetchin...@googlemail.com> writes: > > 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. -- [mdw] -- http://mail.python.org/mailman/listinfo/python-list
