Karim BELABAS on Mon, 19 May 2003 19:05:26 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: charpoly using too much stack space ! |
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]