inverse of a matrix with Fraction entries
Daniel Fetchinson
fetchinson at googlemail.com
Thu Nov 25 22:28:29 CET 2010
>> > 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
More information about the Python-list
mailing list