Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am currently working on a Computer Algebra System and was wondering for suggestions on methods of finding roots/factors of polynomials. I am currently using the Numerical Durand-Kerner method but was wondering if there are any good non-numerical methods (primarily for simplifying fractions etc).

Ideally this should work for equations in multiple variables.

share|improve this question
    
Into factors with... integer coefficients? There is a big Wikipedia article on that subject. –  Qiaochu Yuan Jul 28 '10 at 0:32
    
Not necessarily - any unique factorisation into irreducible polynomials would do the job (I believe that the general formula of algebra states/implies that there should only be 1?). I have read multiple Wikipedia articles (wherein I found the Durand-Kerner method) around this subject but am looking for a more precise method. –  ternaryOperator Jul 28 '10 at 1:48

2 Answers 2

up vote 6 down vote accepted

If you are interested in the factorization algorithms employed in modern computer algebra systems such as Macsyma, Maple, or Mathematica, then see any of the standard introductions to computer algebra , e.g. Geddes et.al. "Algorithms for Computer Algebra"; Knuth, "TAOCP" v.2; von zur Gathen "Modern Computer Algebra"; Zippel "Effective Polynomial Computation". See also Kaltofen's surveys on polynomial factorization [116,68,56,7] in his publications list, which contains plenty of theory, history and literature references. Note: Kaltofen's home page appears to be temporarily down so instead see his paper [1] to get started (see comments)

1 Kaltofen, E. Factorization of Polynomials, pp. 95-113 in:
Computer Algebra, B. Buchberger, R. Loos, G. Collins, editors, Vienna, Austria, (1982).
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.39.7916&rep=rep1&type=pdf

share|improve this answer
    
Thank you, I will see how well I can implement some of these :-) –  ternaryOperator Jul 28 '10 at 21:25

If you're looking to factor exactly, then you'll need to use something that's not one of the fundamental operations of addition, subtraction, multiplication, division and extraction of roots. The Abel-Ruffini theorem says so for degree five and above. However, there are numerous other methods to find roots exactly, using more general functions, my favorite being theta functions, as explained in the appendix to Mumford's "Tata Lectures on Theta II"

share|improve this answer
    
Thanks, I will look into that. –  ternaryOperator Jul 28 '10 at 1:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.