Advertisement
Published in:
2014 | OriginalPaper | Chapter
Real Polynomial Root-Finding by Means of Matrix and Polynomial Iterations
Author : Victor Y. Pan
Published in: Computer Algebra in Scientific Computing
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Frequently one seeks approximation to all
r
real roots of a polynomial of degree
n
with real coefficients, which also has nonreal roots. We split a polynomial into two factors, one of which has degree
r
and has
r
real roots. We approximate them at a low cost, and then decrease the arithmetic time of the known algorithms for this popular problem by roughly a factor of
n
/
k
, if
k
iterations prepare splitting.
k
is a small integer unless some nonreal roots lie close to the real axis, but even if there nonreal roots near the real axis, we substantially accelerate the known algorithms. We also propose a dual algorithm, operating with the associated structured matrices. At the price of minor increase of the arithmetic time, it facilitates numerical implementation. Our analysis and tests demonstrate the efficiency of our approach.