inverse of a matrix with Fraction entries

[Daniel Fetchinson]

>> > 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