Parallel computation of polynomial GCD and some related parallel computations over abstract fields

DOI10.1016/0304-3975(96)00030-8zbMath0874.12010OpenAlexW2030911590WikidataQ127526100 ScholiaQ127526100MaRDI QIDQ1365930

Pan, Victor Y.

Publication date: 10 September 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(96)00030-8

zbMATH Keywords

ranksalgebraic codingToeplitz matricesgcdresultantHankel matricesparallel computationsVandermonde matriceslcmCauchy matricesnull-spacescoefficients of a linear recurrence sequencerandomized parallel arithmetic complexityrecursive Padé approximation

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Direct numerical methods for linear systems and matrix inversion (65F05) Distributed algorithms (68W15)

Related Items

Algebraic and numerical techniques for the computation of matrix determinants, Techniques for exploiting structure in matrix formulae of the sparse resultant, New techniques for the computation of linear recurrence coefficients, Nearly optimal solution of rational linear systems of equations with symbolic lifting and numerical initialization, Fast computation of special resultants, Fast rectangular matrix multiplication and applications, Sign determination in residue number systems, Symbolic and numeric methods for exploiting structure in constructing resultant matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simple algorithms for approximating all roots of a polynomial with real roots
• On computing the determinant in small parallel time using a small number of processors
• Matrix multiplication via arithmetic progressions
• A new algorithm for solving Toeplitz systems of equations
• Complexity of parallel matrix computations
• Parallel evaluation of the determinant and of the inverse of a matrix
• Displacement ranks of matrices and linear equations
• Asymptotically fast solution of Toeplitz and related systems of linear equations
• The parallel computation of minimum cost paths in graphs by stream contraction
• On fast multiplication of polynomials over arbitrary algebras
• Parallel solution of Toeplitzlike linear systems
• Parametrization of Newton's iteration for computations with structured matrices and applications
• An improved parallel processor bound in fast matrix inversion
• A probabilistic remark on algebraic program testing
• A new approach to fast polynomial interpolation and multipoint evaluation
• Fast and efficient parallel evaluation of the zeros of a polynomial having only real zeros
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• Root-squaring with DPR1 matrices
• On the computational power of pushdown automata
• Parallel Algorithms for Algebraic Problems
• Lattice filter parameterization and modeling of nonstationary processes
• Solving sparse linear equations over finite fields
• Fast Parallel Algorithms for QR and Triangular Factorization
• Superfast Solution of Real Positive Definite Toeplitz Systems
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• Complexity of Computations with Matrices and Polynomials
• Decreasing the Displacement Rank of a Matrix
• A view of three decades of linear filtering theory
• Fast Parallel Matrix Inversion Algorithms
• Inverses of Toeplitz Operators, Innovations, and Orthogonal Polynomials
• Improved Parallel Polynomial Division
• Fast Parallel Computation of the Polynomial Remainder Sequence via Bézout and Hankel Matrices
• The Parallel Evaluation of General Arithmetic Expressions
• Fast parallel computation of characteristic polynomials by Leverrier's power sum method adapted to fields of finite characteristic
• Fast parallel matrix and GCD computations
• Work-Preserving Speed-Up of Parallel Matrix Computations
• Subresultants and Reduced Polynomial Remainder Sequences
• On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors
• On Euclid's Algorithm and the Theory of Subresultants
• The Padé Table and Its Relation to Certain Algorithms of Numerical Analysis
• Divide-and-Conquer Solutions of Least-Squares Problems for Matrices with Displacement Structure
• Fast construction of irreducible polynomials over finite fields