Gonzalo Tornaria on Mon, 19 May 2003 09:18:50 -0500

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Re: charpoly using too much stack space !

On Sun, May 18, 2003 at 06:44:21PM +0200, Karim BELABAS wrote:
> This patch is quite correct. I have committed to CVS a different one, which
> fixed a number of minor annoyances [ stack leaks ], and handles stack usage
> in a less hackish way than previously.
> I have not noticed any efficiency loss.

It's consistently 15% faster for me (in a P4 2.00GHz),
and it seems to use even less stack than Bill's patch.

For a 100x100 matrix it worked with just 3:500.000 bytes in the stack
(and only 67,5 secs).

Notably, if the matrix has only 400 1's, and the rest 0's, it only
takes 8,5 secs; on the other hand, I can do it in 1,2 secs with a GP
program that "knows" how to deal with such a sparse matrix.

Just FYI, same thing with 200x200 matrix with 800 1's takes 133 secs with
the libpari charpoly, versus 8 secs for the "sparse-enabled" program,
and the charpoly of a 500x500 matrix with 2000 1's can be computed
in 138 secs (didn't try the libpari function, but I expect it to take
over an hour).

GM/CS/S d? a-- C++(+++)  UL+++(++++)  P++>+++  L+++>++++ E---
W-(+) N+(++) w--- O M-(--) V-(--) PGP(--) b++(+++) G++ e>++++

... A mathematician is a machine for converting coffee into theorems.