Fast parallel algorithms for Graeffe's root squaring technique

DOI10.1016/S0898-1221(97)00280-0MaRDI QIDQ1129507zbMATH OpenFDO

Authors Prasanta K. Jana, Bhabani P. Sinha

Publication date 22 March 1999

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0898-1221(97)00280-0

zbMATH Keywords

Graeffe's methodparallel algorithmssystolic architecturestrees and multitreeszeros of polynomials

Mathematics Subject Classification ID

Real polynomials: location of zeros (26C10) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of solutions to single equations (65H05) Parallel numerical computation (65Y05) Numerical algorithms for specific classes of architectures (65Y10)

Review text

The authors propose two parallel implementations for an iteration step for the solution of an \(n\)-degree polynomial equation, where \(n\) can be very large. The algorithms are based on Graeffe's method for the calculation of the zeros of a polynomial. The parallel implementation of this method utilizes the special structure of the relevant matrix and is based on two different systolic architectures, built around mesh trees and multitrees. Estimates for the efficiency of the algorithms are also provided.

Recommendations

• scientific article; zbMATH DE number 880381
• A parallel algorithm for simple roots of polynomials
• Systolic designs for the root-squaring method
• On the parallel arithmetic complexity of the root-finding problem
• Parallel algorithms for some algebraic operations on polynomial equations

Cites work

• A highly parallel algorithm for root extraction
• A Survey of Parallelism in Numerical Analysis
• A Three-Stage Algorithm for Real Polynomials Using Quadratic Iteration
• scientific article; zbMATH DE number 3439855 (Why is no real title available?)
• scientific article; zbMATH DE number 3240705 (Why is no real title available?)
• Parallel iteration methods
• Parallel Methods for Approximating the Root of a Function
• Parallel numerical methods for the solution of equations
• Principles for Testing Polynomial Zerofinding Programs
• Sparse matrix vector multiplication techniques on the IBM 3090 VF
• The scheduling of sparse matrix-vector multiplication on a massively parallel DAP computer

Cited in

(3)

• scientific article; zbMATH DE number 880381 (Why is no real title available?)
• Computing one billion roots using the tangent Graeffe method
• On the geometry of Graeffe iteration

This page was built for publication: Fast parallel algorithms for Graeffe's root squaring technique

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