At Tuesday 23/1/2007 22:33, Paul McGuire wrote:
On Jan 23, 6:59 pm, Robert Kern <[EMAIL PROTECTED]> 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
--
http://mail.python.org/mailman/listinfo/python-list
