🚀 go-pugleaf

In article <9227919.6924@mulga.cs.mu.OZ.AU>, yzhu@nairana.ee.mu.oz.au (Yan ZHU (yhua)) writes:
> 
>  
>  I am trying to solve non-linear problem by LP method.
>  And I am looking for an algorithm for the numerical
>  factorization of very high degree (500th-800th) polynomials 
>  with complex coefficients.
> 
>  ...stuff deleted 

NAG Fortran Library routine C02AFF finds all the roots of a complex
polynomial equation, usinmg a variant of Laguerre's method. Any degree
can be specified.

But I think many would question the wisdom of trying to compute all the roots
of a very high degree polynomial. Anybody else out there doing anything
similar?

Richard.
-- 
** R.W. Brankin -- Numerical Algorithms Group Ltd. -- nagrwb@vax.ox.ac.uk **
**   suggestions for sig. welcome   --   will need   include<std.discl>   **

In article <1992Oct6.094142.9281@vax.oxford.ac.uk> nagrwb@vax.oxford.ac.uk writes:
>In article <9227919.6924@mulga.cs.mu.OZ.AU>, yzhu@nairana.ee.mu.oz.au (Yan ZHU (yhua)) writes:
>> 
>>  
>>  I am trying to solve non-linear problem by LP method.
>>  And I am looking for an algorithm for the numerical
>>  factorization of very high degree (500th-800th) polynomials 
>>  with complex coefficients.
>> 
>>  ...stuff deleted 
>
>NAG Fortran Library routine C02AFF finds all the roots of a complex
>polynomial equation, usinmg a variant of Laguerre's method. Any degree
>can be specified.
>
	Another method that springs easily to mind is to find the roots
sequentially by the Newton-Raphson method within the synthetic division
algorithm. This of course converges very fast and on finding one root you
are automatically left with the coeffs. of the "deflated" polynomial and
of course, the method is perfectly suitable to polynomials with complex
coeffs. I have used this with considerable satisfaction on "moderately
large" polynomials - but certainly NOT of order 500-800. However I see no
reason why it should not work provided the calculations could be done in
"sufficiently high" precision (I doubt that COMPLEX*8 would be adequate!).

						W. Alan B. Evans
						[ wabe@ukc.ac.uk ]

In article <1787@eagle.ukc.ac.uk> wabe@ukc.ac.uk (W.A.B.Evans) writes:
>	Another method that springs easily to mind is to find the roots
>sequentially by the Newton-Raphson method within the synthetic division
>algorithm. This of course converges very fast and on finding one root you
>are automatically left with the coeffs. of the "deflated" polynomial and
>of course, the method is perfectly suitable to polynomials with complex
>coeffs. I have used this with considerable satisfaction on "moderately
>large" polynomials - but certainly NOT of order 500-800. However I see no
>reason why it should not work provided the calculations could be done in
>"sufficiently high" precision (I doubt that COMPLEX*8 would be adequate!).
>
>						W. Alan B. Evans
>						[ wabe@ukc.ac.uk ]

The problem is not so much computing in high precision as insuring
that the zeros are found and deflated in roughly ascending order.
This was first pointed out by the late Jim Wilkinson.  An alternative
to Newton's method is Laguerre's method, which has nice properties for
polynomials with real roots.  An algorithm due to Jenkins and Traub
is, I believe, available on netlib.  I am appending a very selective
bibliography (the literature is enormous).

Pete Stewart

\begin{thebibliography}{1}

\bibitem{jenk:69}
M.~A. Jenkins.
\newblock Three-stage variable-shift iterations for the solution solution of
  polynomial equations with a posteriori error bounds for the zeros.
\newblock Technical Report 138, Computer Science Department, Stanford
  University, 1969.

\bibitem{kaha:67a}
W.~Kahan.
\newblock {Laguerre's} method and a circle which contains at least one zero of
  a polynomial.
\newblock {\em SIAM Journal on Numerical Analysis}, 4:474--482, 1967.

\bibitem{parl:64}
B.~N. Parlett.
\newblock {Laguerre's} method applied to the matrix eigenvalue problem.
\newblock {\em Mathematics of Computation}, 18:464--485, 1964.

\bibitem{smit:67}
B.~T. Smith.
\newblock {ZERPOL}: A zero finding algorithm for polynomials using {Laguerre's}
  method.
\newblock Manuscript. Department of Computer Science, University of Toronto,
  1967.

\bibitem{smit:69}
B.~T. Smith.
\newblock Error bounds, based upon {Gerschgorin's} theorems for the zeros of a
  polynomial.
\newblock Technical Report~9, Department of Computer Science, University of
  Toronto, 1969.

\bibitem{stew:71a}
G.~W. Stewart.
\newblock Error analysis of the algorithm for shifting the zeros of a
  polynomial by synthetic division.
\newblock {\em Mathematics of Computation}, 25:135--139, 1971.

\bibitem{wilk:59}
J.~H. Wilkinson.
\newblock The evaluation of the zeros of ill-conditioned polynomials. {Part~I}.
\newblock {\em Numerische Mathematik}, 1:150--166, 1959.

\bibitem{wilk:63}
J.~H. Wilkinson.
\newblock {\em Rounding Errors in Algebraic Processes}.
\newblock Prentice-Hall, Englewood Cliffs, New Jersey, 1963.

\bibitem{wilk:65}
J.~H. Wilkinson.
\newblock {\em The Algebraic Eigenvalue Problem}.
\newblock Clarendon Press, Oxford, England, 1965.

\end{thebibliography}