Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)

DOI10.1006/jcom.1998.0481zbMath0934.12005OpenAlexW2097541598MaRDI QIDQ1273735

Peter Kirrinnis

Publication date: 11 April 1999

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

Full work available at URL: https://doi.org/10.1006/jcom.1998.0481

zbMATH Keywords

rational functionspartial fraction decompositioncomplex coefficientsNewton's algorithmbit complexityasymptotic time boundsfactoring univariate polynomialsfast numerical algorithmssplitting circle algorithm

Mathematics Subject Classification ID

Related Items (24)

Polynomial factorization through Toeplitz matrix computations ⋮ Filtering and smoothing formulas of AR(p)-modulated Poisson processes ⋮ A near-optimal subdivision algorithm for complex root isolation based on the Pellet test and Newton iteration ⋮ Fast Cauchy sum algorithms for polynomial zeros and matrix eigenvalues ⋮ Nearly optimal refinement of real roots of a univariate polynomial ⋮ Efficient polynomial root-refiners: a survey and new record efficiency estimates ⋮ Simple and Nearly Optimal Polynomial Root-Finding by Means of Root Radii Approximation ⋮ Fast matrix multiplication and its algebraic neighbourhood ⋮ Globally convergent, iterative path-following for algebraic equations ⋮ Transformations of matrix structures work again ⋮ Root-finding by expansion with independent constraints ⋮ Root refinement for real polynomials using quadratic interval refinement ⋮ Fast computation of contour integrals of rational functions ⋮ Approximating complex polynomial zeros: modified Weyl's quadtree construction and improved Newton's iteration. ⋮ Computing real roots of real polynomials ⋮ Newton's method and the Computational Complexity of the Fundamental Theorem of Algebra ⋮ Computing a Hurwitz factorization of a polynomial ⋮ On the complexity of computing with planar algebraic curves ⋮ Univariate polynomials: Nearly optimal algorithms for numerical factorization and root-finding ⋮ New progress in real and complex polynomial root-finding ⋮ On the geometry of Graeffe iteration ⋮ Nearly optimal computations with structured matrices ⋮ Computing Igusa class polynomials ⋮ Accelerated approximation of the complex roots and factors of a univariate polynomial

Cites Work

• Quasi-gcd computations
• Sequential and parallel complexity of approximate evaluation of polynomial zeros
• A unified approach to method for the simultaneous computation of all zeros of generalized polynomials
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• On the convergence of Newton's method
• Specified precision polynomial root isolation is in NC
• An optimal bound for path weights in Huffman trees
• Numerics of analytic functions and complexity
• Optimal and nearly optimal algorithms for approximating polynomial zeros
• A three-stage variable-shift iteration for polynomial zeros and its relation to generalized Rayleigh iteration
• Ein Gesamtschrittverfahren zur Berechnung der Nullstellen von Polynomen
• Fast multiplication of large numbers
• An efficient algorithm for the complex roots problem
• Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II
• A Machine Method for Solving Polynomial Equations
• The Computational Complexity of Continued Fractions
• A Globally Convergent Method for Simultaneously Finding Polynomial Roots
• On the cost of approximating all roots of a complex polynomial
• Computational complexity. On the geometry of polynomials and a theory of cost. I
• Storage Modification Machines
• The fundamental theorem of algebra and complexity theory
• On Grau’s Method for Simultaneous Factorization of Polynomials
• Complexity of Bezout's Theorem I: Geometric Aspects
• An Inequality About Factors of Polynomials
• Fast Multiple-Precision Evaluation of Elementary Functions
• Fast Algorithms for Manipulating Formal Power Series
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Iteration Methods for Finding all Zeros of a Polynomial Simultaneously
• A Numerical Method for Locating the Zeros of an Analytic Function
• The Simultaneous Newton Improvement of a Complete Set of Approximate Factors of a Polynomial
• 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

This page was built for publication: Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\)