inverse of a matrix with Fraction entries

[John Nagle]

On 11/24/2010 10:30 AM, Robert Kern wrote:
> On 11/24/10 12:07 PM, Daniel Fetchinson wrote:
>
>> The whole story is that I have a matrix A and matrix B both of which
>> have rational entries and they both have pretty crazy entries too.
>> Their magnitude spans many orders of magnitude, but inverse(A)*B is an
>> okay matrix and I can deal with it using floating point numbers. I
>> only need this exact fraction business for inverse(A)*B (yes, a
>> preconditioner would be useful :))
>>
>> And I wouldn't want to write the whole matrix into a file, call Maple
>> on it, parse the result, etc.
>>
>> So after all I might just code the inversion via Gauss elimination
>> myself in a way that can deal with fractions, shouldn't be that hard.
>
> +1000. This is almost always the right thing to do whether you have
> floats or rationals.

    Right.

    Inverting a matrix of rationals works fine.  There's even a standard
use for that, in theorem proving.  See

    G. Nelson and D. C. Oppen. Simplification by cooperating
decision procedures. ACM Transactions on Programming
Languages and Systems, 1(2):245–257, 1979.

    It turns out that theorem proving for problems in
rational arithmetic which use only addition, subtraction,
multiplication by constants, comparisons for equal, greater and
less, and the boolean operators is completely decidable.
(This covers most of what programs do, especially in the
parts that affect control flow.)  There's a neat
algorithm for solving such problems; you either get "True"
or a counterexample.  The algorithm uses the simplex method
from linear programming, but with rational arithmetic.

    But that's an exotic application.  For ordinary number crunching,
rational arithmetic is completely inappropriate.

				John Nagle