Simple Matrix class

Paul McGuire ptmcg at austin.rr.com
Wed Jan 24 02:33:31 CET 2007


On Jan 23, 6:59 pm, Robert Kern <robert.k... at gmail.com> wrote:
> Paul McGuire wrote:
> > I've posted a simple Matrix class on my website as a small-footprint
> > package for doing basic calculations on matrices up to about 10x10 in
> > size (no theoretical limit, but performance on inverse is exponential).
>
> Why is that? A simple and robust LU decomposition should be no more than O(n**3).
>
> --
> Robert Kern

Well "3" is an exponent isn't it? :)

In truth, in my laziness, I didn't *actually* test the performance.
But after measuring inversion times for nxn matrices for n=2 to 12, I
get these results (run on Python 2.4.2, on a 2GHz CPU):

n  seconds                ln(seconds)
2 0.000411225449045 -7.79636895604
3 0.00102247632031 -6.88552782893
4 0.00437541642862 -5.43175358002
5 0.0146999129778 -4.21991370509
6 0.0507813143849 -2.98022681913
7 0.143077961026 -1.94436561528
8 0.39962257773 -0.917234732978
9 1.14412558021 0.134640659841
10 3.01953516439 1.10510290046
11 8.76039971561 2.17024153354
12 21.8032182861 3.0820575867

Plotting n vs. ln(seconds) gives a fairly straight line of slope about
1.09, and exp(1.09) = 2.97, so your big-O estimate seems to line up
nicely with the experimental data - I couldn't have fudged it any
better.

-- Paul




More information about the Python-list mailing list