Simple Matrix class

[Gabriel Genellina]

At Tuesday 23/1/2007 22:33, Paul McGuire wrote:

>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).
> >
>
>Well "3" is an exponent isn't it? :)

But constant!
x**2 is a "power" (or quadratic, or polynomial) function. 2**x is an 
"exponential" function. They're quite different.

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

Nope, such semilog plot shows that time grows exponentially, like 
t=3*exp(n), and that's really bad! :(
The points should be aligned on a log-log plot to be a power function.
As Robert Kern stated before, this problem should be not worse than 
O(n**3) - how have you implemented it?


-- 
Gabriel Genellina
Softlab SRL 


	

	
		
__________________________________________________ 
Preguntá. Respondé. Descubrí. 
Todo lo que querías saber, y lo que ni imaginabas, 
está en Yahoo! Respuestas (Beta). 
¡Probalo ya! 
http://www.yahoo.com.ar/respuestas