From: magnus@Fisher.Stanford.EDU (Magnus Nordborg)
Subject: SUMMARY: Best way to factor out roots
Keywords: factor, polynomial, algebra, memory
Organization: DSO, Stanford University
Date: Fri, 11 Sep 92 06:49:55 GMT

Some time ago now, I posted the following question to this group:

> Given an enormous multivariate polynomial and a number of *known* 
> factors, which is the best way to factor them out of the polynomial? I 
> have access to MACSYMA, Mathematica, and Maple, but have had very little 
> success with all. Just asking the programs to "factor" does not work due  
> to the size of the expression, but there must be some way of telling 
> these programs *which* factors to look for.

I recieved many suggestions, and I am sorry I took so long to summarize; I  
wanted to try them all out first.

The best way seems to be the following: Use exact polynomial division  
(long division) to remove one factor at a time, and then factor what is  
left. In terms of the three packages mentioned above, the commands are:

MACSYMA: DIVIDE(enormous_poly, known_factor);
Mathematica: PolynomialDivision[enormous_poly, known_factor, variable]
Maple: divide(enormous_poly, known_factor,'enormous_poly');

For MACSYMA, using "ratsimp" was also suggested, and for Maple, "normal",  
but these seem suboptimal in comparison.

Additional cleverness came from: t68@nikhefh.nikhef.nl (Jos Vermaseren)
> One way to factor out 'known' roots from a large polynomial is by
> 'substitution'.
> Suppose you know that 5 is a root. Then you replace
> x-5 by y, or x -> y+5 or whatever the syntax demands.
> This operation involves an amount of work which is related to the
> sum of all powers in your polynomial (plus some extra for the fact that
> the binomial coefficients can become large).
> The new polynomial should have a root at y = 0, so it is rather easy
> to divide it out. After that you go to the next 'known root'.
> Other methods are variations of this. If you divide by (x-5) the
> partial fractioning involved is equivalent to the above procedure.
> 
> Jos Vermaseren

The number of respondents is too large for me to mention everyone  
individually, so thank you all collectively! :-)

Unfortunately, NONE of the solutions suggested worked in my case.  The  
polynomial involved simply seems to be too large.  All three programs give  
up, sometimes by telling me that they are out of memory and aborting the  
job, and sometimes by just crashing...

If there are any generalizations from my various tests, it is that Maple  
is without comparison fastest, but that it also seems to suffer from  
internal constraints that causes it to give up when the other two swapon  
(pun) and sometimes come up with an answer.  More often than not they also  
crash, however, but later... Does anyone have similar observations, or  
comments?

I have introduced all simplifications I could think of, but my problem  
still seems too large.  I tested all three programs on HP's, NeXT's, and  
Sparc's with up to 64 MB RAM and plenty of swap space.  In addition, I  
tried an old Mathematica (1.1 or something) on an SGI server which has one  
of the highest MIPS ratings around, and 256 MB RAM. After 10 days the job  
was almost a GB, and showed no sign of doing anything useful so I was  
forced to let it go...

I anyone has further suggestions, or comments, please let me know.  Once  
again, I wish to thank all that replied.
--


		Magnus Nordborg
		Department of Biological Sciences
		Stanford University
		magnus@fisher.stanford.edu (NeXT mail preferred)
Newsgroups: sci.math.symbolic