[metapost] memory problem

Denis Roegel Denis.Roegel at loria.fr
Mon May 8 19:37:57 CEST 2006


On Mon, May 08, 2006 at 06:56:22PM +0200, Boguslaw Jackowski wrote:
> 
> Denis:
> > But this doesn't answer the slow solving of a large number
> > of independent equations. I think we should work on a non-metaobj
> > example and focus on it.
> 
> Taco:
> > Agreed. This is core functionality, and as such, its running time
> > should be x^3. 
> >
> > make that:
> >   should _not_ be x^3
> 
> Knuth applies ``the standard technique of Gaussian elimination''
> to convert a system of equations to the diagonal form. The complexity
> of this method is x^3. Is it possible ( practically, i.e., not
> using tricks of the kind of Strassen's fast matrix multiplication,
> http://mathworld.wolfram.com/StrassenFormulas.html ) to gain
> a significant speed-up? Sorry for a silly question, but I'm not
> ``au courant'' with respect to recent advances in numerical
> methods...

Obviously we can, if we know that there are independent systems
of equations. If 25 equations/unknowns take 25^3 time,
then 100 independent sets of 25 equations/unknown should take
100*25^3 time, and not (25*100)^3 time. Of course, splitting the
equations in independent sets will probably make us lose at least
what we gain on one side, but the/my point is not really to
automate this splitting, it is to somehow give hints to metapost
so that it could solve the system faster.

Denis


More information about the metapost mailing list