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

DOI10.1006/jcom.1998.0481zbMath0934.12005MaRDI 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 functions; partial fraction decomposition; complex coefficients; Newton's algorithm; bit complexity; asymptotic time bounds; factoring univariate polynomials; fast numerical algorithms; splitting circle algorithm

Mathematics Subject Classification ID

68W30: Symbolic computation and algebraic computation

65H05: Numerical computation of solutions to single equations

Related Items

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

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
• 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