inverse of a matrix with Fraction entries
mdw at distorted.org.uk
Thu Nov 25 21:56:54 CET 2010
Daniel Fetchinson <fetchinson at 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.
More information about the Python-list