Bill Allombert on Sun, 18 May 2003 00:23:30 +0200


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

Re: charpoly using too much stack space !


On Sat, May 17, 2003 at 01:21:53PM -0500, Gonzalo Tornaria wrote:
> When computing the characteristic polynomial of big matrices (not so
> much, in the example 50x50), PARI uses A LOT of stack space, which I
> believe is not really necesary. I've written a gp function for
> computing the characteristic polynomial (matrix_charpoly), using what
> I believe is the same algorithm of charpoly (computing traces, etc.)
> 
> What's surprising is that, if I compile the GP function (with GP2C),
> it doesn't get any faster, but it needs more stack space (even with -g)!!!

GP allocate memory in the heap (using malloc) but gp2c compiled programs
allocate all the memory on the PARI stack, so they require more
room on the stack and less on the heap than GP script.

This also hold for libpari but here there is something wrong.

Here a patch that should fix the problem

Index: src/basemath/alglin2.c
===================================================================
RCS file: /home/megrez/cvsroot/pari/src/basemath/alglin2.c,v
retrieving revision 1.85
diff -u -r1.85 alglin2.c
--- src/basemath/alglin2.c      2003/04/23 15:36:11     1.85
+++ src/basemath/alglin2.c      2003/05/17 22:22:17
@@ -204,7 +204,7 @@
     }
     gptr[0]=&y; gptr[1]=&t;
     gerepilemanysp(av,tetpil,gptr,2);
-    p[l-k+1]=(long)t; av=avma;
+    p[l-k+1]=(long)t; av=(pari_sp)y;
   }

   t=gzero;

Cheers,
Bill.