A divide and conquer method for polynomial zeros

DOI10.1016/0377-0427(90)90006-LMaRDI QIDQ911228zbMATH OpenOpenAlexFDO

Authors T. L. Freeman, R. W. Brankin

Publication date 1990

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-0427(90)90006-l

zbMATH Keywords

block Toeplitz structurecomputational efficiencydivide and conquer methodfactorizationJacobian matrixNewton iterationpolynomial zeros

Mathematics Subject Classification ID

Polynomials in real and complex fields: factorization (12D05) Real polynomials: location of zeros (26C10) Numerical computation of solutions to single equations (65H05)

Review text

It is shown that the factorization of a polynomial with real coefficients into two polynomials permits the development of a divide and conquer method for numerical calculation of all the zeros of the polynomial. The proposed algorithm is based on a Newton iteration to solve the quadratic equations which relate the unknown coefficients of those two factors to the known coefficients of the given polynomial. In a Newton iteration, a system of linear equations with the Jacobian matrix of quadratic equations as the coefficient matrix is solved. By exploiting the block Toeplitz structure of the Jacobian matrix, the Newton iteration can be implemented very efficiently. Numerical performance of the proposed method is given to illustrate its computational efficiency.

Recommendations

• scientific article; zbMATH DE number 880382
• Newton Iteration Towards a Cluster of Polynomial Zeros
• On one method of factorization of polynomials
• Wiener-Hopf and spectral factorization of real polynomials by Newton's method
• scientific article; zbMATH DE number 4078649

Cites work

• A Divide and Conquer method for the symmetric tridiagonal eigenproblem
• A Fully Parallel Algorithm for the Symmetric Eigenvalue Problem
• A Generalization of a Theorem of Bôcher
• A method for computing all the zeros of a polynomial with real coefficients
• An Algorithm for the Inversion of Finite Toeplitz Matrices
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Associated Polynomials and Uniform Methods for the Solution of Linear Problems
• Corrections to numerical data on Q-D algorithm
• Eigenvalues of a symmetric tridiagonal matrix: A divide-and-conquer approach
• Finding zeros of a polynomial by the Q-D algorithm
• scientific article; zbMATH DE number 3886960 (Why is no real title available?)
• scientific article; zbMATH DE number 4033059 (Why is no real title available?)
• scientific article; zbMATH DE number 4093307 (Why is no real title available?)
• scientific article; zbMATH DE number 3892457 (Why is no real title available?)
• scientific article; zbMATH DE number 3393631 (Why is no real title available?)
• On Bairstow's Method for the Solution of Polynomial Equations
• Stability of Methods for Solving Toeplitz Systems of Equations
• The Solution of a Toeplitz Set of Linear Equations
• Toeplitz Matrix Inversion: The Algorithm of W. F. Trench

Cited in

(3)

• A polynomial-time algorithm for finding zero-sums.
• scientific article; zbMATH DE number 880382 (Why is no real title available?)
• Numerical factorization of a polynomial by rational Hermite interpolation

Describes a project that uses

Uses Software

• TOEPLITZ

This page was built for publication: A divide and conquer method for polynomial zeros

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911228)