[metapost] memory problem

[Denis Roegel]

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