inverse of a matrix with Fraction entries
casevh at gmail.com
Sat Nov 27 04:21:47 CET 2010
On Nov 26, 2:11 pm, Steven D'Aprano <steve
+comp.lang.pyt... at pearwood.info> wrote:
> On Fri, 26 Nov 2010 12:54:12 -0800, John Nagle wrote:
> > For ordinary number crunching,
> > rational arithmetic is completely inappropriate.
As you perform repeated calculations with rationals, the size of the
values (usually) keep growing. (Where size is measured as the length
of numerator and denominator.) The speed and memory requirements are
no longer constant.
I coded a quick matrix inversion function and measured running times
using GMPY2 rational and floating point types. For the floating point
tests, I used a precision of 1000 bits. With floating point values,
the running time grew as n^3. With rational values, the running time
grew as n^4*ln(n).
On my system, inverting a 1000x1000 matrix with 1000-bit precision
floating point would take about 30 minutes. Inverting the same matrix
using rationals would take a month or longer and require much more
memory. But the rational solution would be exact.
More information about the Python-list