Re: charpoly using too much stack space !

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

On Mon, 19 May 2003, Gonzalo Tornaria wrote:
> 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.
>
> It's consistently 15% faster for me (in a P4 2.00GHz),
> and it seems to use even less stack than Bill's patch.

Taking heap space into account, I'm using about as much space as Bill.

By killing a clone a bit earlier, I can reduce memory use by a further 30%,
but that wouldn't work in the presence of t_INTMOD / t_PADIC / t_POLMOD
because in general such objects obtained from out-of-stack data (such as
clones) contain pointers to that data, not copies. So I can't delete the
initial clone before creating the new one [ which transforms all such
pointers into hard copies ].

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

This is an interesting observation. I have tweaked general matrix
multiplication so as to take advantage of many zero entries [ there's still
no specialized treatment and representation for sparse matrices ! ]. It has a
negligible impact on dense multiplication and a huge one on very sparse
matrices. This rather improves the charpoly() routine, though not to the
extent you mention. Committed to CVS.

A further optimization for +1 entries is complicated/unsafe ( there are many
things which can be "equal to 1" and still not be neutral wrt multiplication ),
and only yields marginal improvements ( say 15% at most ), so I've not
committed this one.

Can you update from CVS and check the speed improvement your GP
implementation provides ? [ and could you post the latter in the case it
still outperforms the native routine ? ]

    Karim.
-- 
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dép. de Mathématiques, Bât. 425   Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud              http://www.math.u-psud.fr/~belabas/
F-91405 Orsay (France)            http://www.parigp-home.de/  [PARI/GP]