Polynomial division and its computational complexity

DOI10.1016/0885-064X(86)90001-4zbMath0629.68040OpenAlexW2071176954WikidataQ109673820 ScholiaQ109673820MaRDI QIDQ1094135

Dario Andrea Bini, Pan, Victor Y.

Publication date: 1986

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0885-064x(86)90001-4

zbMATH Keywords

algorithms for polynomial divisiongcd of two polynomialsparallel divisionsequential time complexitytriangular Toeplitz matrix inversion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials in general fields (irreducibility, etc.) (12E05)

Related Items

Binary segmentation for matrix and vector operations, A fast direct method for block triangular Toeplitz-like with tri-diagonal block systems from time-fractional partial differential equations, Solving certain queueing problems modelled by Toeplitz matrices, Algebraic complexity of computing polynomial zeros, Computations with infinite Toeplitz matrices and polynomials, Sequential and parallel complexity of approximate evaluation of polynomial zeros, Inversion in finite fields using logarithmic depth, An algebraic approach to approximate evaluation of a polynomial on a set of real points, Deterministic improvement of complex polynomial factorization based on the properties of the associated resultant, A logarithmic Boolean time algorithm for parallel polynomial division, Matrix structures in parallel matrix computations, Optimal and nearly optimal algorithms for approximating polynomial zeros, Fast inversion of triangular Toeplitz matrices, Toeplitz matrices for LTI systems, an illustration of their application to Wiener filters and estimators, On the evaluation of the eigenvalues of a banded Toeplitz block matrix, A modular algorithm to compute the generalized Hermite normal form for \(\mathbb{Z}[x\)-lattices], Polynomial division with a remainder by means of evaluation and interpolation, Fast approximate inversion of a block triangular Toeplitz matrix with applications to fractional sub‐diffusion equations, Approximate real polynomial division via approximate inversion of real triangular Toeplitz matrices, Efficient Algorithms for the Evaluation of the Eigenvalues of (Block) Banded Toeplitz Matrices, Parallel algorithms for matrix polynomial division, Variations on computing reciprocals of power series

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Error analysis of an APA algorithm for the parallel solution of some special Toeplitz linear systems
• How to multiply matrices faster
• Fast parallel polynomial division via reduction to triangular Toeplitz matrix inversion and to polynomial inversion modulo a power
• Algebraic complexity of computing polynomial zeros
• The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented \(\lambda\) algorithms
• The bit-operation complexity of matrix multiplication and of all pair shortest path problem
• The bit-operation complexity of approximate evaluation of matrix and polynomial products using modular arithmetic
• Base tensorielle des matrices de Hankel (ou de Toeplitz). Applications
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• On the computational power of pushdown automata
• Parallel Solution of Certain Toeplitz Linear Systems
• Parallel computation for well-endowed rings and space-bounded probabilistic machines
• Logarithmic Depth Circuits for Algebraic Functions
• The bit-complexity of arithmetic algorithms
• Fast solution of toeplitz systems of equations and computation of Padé approximants
• Fast computation of GCDs
• Evaluating Polynomials at Fixed Sets of Points
• Fast parallel matrix and GCD computations