Polynomial division and its computational complexity
(i) First we show that all the known algorithms for polynomial division can be represented as algorithms for triangular Toeplitz matrix inversion. In spite of the apparent difference of the algorithms of these two classes, their strong equivalence is demonstrated. (ii) Then we accelerate parallel division of two polynomials with integer coefficients of degrees at most m by a factor of log m comparing with the parallel version of the algorithm of Sieveking and Kung. The result relies on the analysis of the recent algorithm of D. Bini adjusted to the division of polynomials over integers. (Some known parallel algorithms attain the same parallel time but use \(\geq m\) times more processors.) (iii) Finally the authors' new algorithm improves the estimates for sequential time complexity of division with a remainder of two integer polynomials by a factor of log m, m being the degree of the dividend. Under the parallel model, it attains Boolean logarithmic time, which is asymptotically optimum. The algorithm exploits the reduction of the problem to integer division; the polynomial remainder and quotient are recovered from integer remainder and quotient via binary segmentation. (iv) The latter approach is also extended to the sequential evaluation of the gcd of two polynomials over integers.
- \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
- Algebraic complexity of computing polynomial zeros
- Base tensorielle des matrices de Hankel (ou de Toeplitz). Applications
- Error analysis of an APA algorithm for the parallel solution of some special Toeplitz linear systems
- Evaluating Polynomials at Fixed Sets of Points
- Fast computation of GCDs
- Fast parallel matrix and GCD computations
- Fast parallel polynomial division via reduction to triangular Toeplitz matrix inversion and to polynomial inversion modulo a power
- Fast solution of toeplitz systems of equations and computation of Padé approximants
- How to multiply matrices faster
- scientific article; zbMATH DE number 3856407 (Why is no real title available?)
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- scientific article; zbMATH DE number 3782281 (Why is no real title available?)
- scientific article; zbMATH DE number 3471577 (Why is no real title available?)
- scientific article; zbMATH DE number 3566175 (Why is no real title available?)
- scientific article; zbMATH DE number 3624682 (Why is no real title available?)
- scientific article; zbMATH DE number 3628385 (Why is no real title available?)
- scientific article; zbMATH DE number 3383473 (Why is no real title available?)
- scientific article; zbMATH DE number 3408799 (Why is no real title available?)
- Logarithmic Depth Circuits for Algebraic Functions
- On the computational power of pushdown automata
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Parallel Solution of Certain Toeplitz Linear Systems
- The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented algorithms
- The bit-complexity of arithmetic algorithms
- The bit-operation complexity of approximate evaluation of matrix and polynomial products using modular arithmetic
- The bit-operation complexity of matrix multiplication and of all pair shortest path problem
- Fast parallel polynomial division via reduction to triangular Toeplitz matrix inversion and to polynomial inversion modulo a power
- Algebraic complexity of computing polynomial zeros
- Sequential and parallel complexity of approximate evaluation of polynomial zeros
- A logarithmic Boolean time algorithm for parallel polynomial division
- Matrix structures in parallel matrix computations
- Polynomial division using left shift register
- On the evaluation of the eigenvalues of a banded Toeplitz block matrix
- Polynomial division with a remainder by means of evaluation and interpolation
- Solving certain queueing problems modelled by Toeplitz matrices
- Computations with infinite Toeplitz matrices and polynomials
- Variations on computing reciprocals of power series
- Approximate real polynomial division via approximate inversion of real triangular Toeplitz matrices
- Algorithms for fast polynomial division
- 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
- Optimal and nearly optimal algorithms for approximating polynomial zeros
- 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
- Inversion in finite fields using logarithmic depth
- A new parallel polynomial division by a separable polynomial via Hermite interpolation with applications
- scientific article; zbMATH DE number 3924143 (Why is no real title available?)
- scientific article; zbMATH DE number 3958730 (Why is no real title available?)
- Efficient Algorithms for the Evaluation of the Eigenvalues of (Block) Banded Toeplitz Matrices
- A fast algorithm for the division of two polynomial matrices
- Improved Parallel Polynomial Division
- scientific article; zbMATH DE number 1256648 (Why is no real title available?)
- scientific article; zbMATH DE number 2034379 (Why is no real title available?)
- Toeplitz matrices for LTI systems, an illustration of their application to Wiener filters and estimators
- Fast parallel algorithms for polynomial division over an arbitrary field of constants
- A modular algorithm to compute the generalized Hermite normal form for \(\mathbb{Z}[x]\)-lattices
- Fast approximate inversion of a block triangular Toeplitz matrix with applications to fractional sub-diffusion equations.
- Fast inversion of triangular Toeplitz matrices
- Parallel algorithms for matrix polynomial division
This page was built for publication: Polynomial division and its computational complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1094135)
