Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\) (Q1273735): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Normalize DOI. |
||
Property / DOI | |||
Property / DOI: 10.1006/jcom.1998.0481 / rank | |||
Property / DOI | |||
Property / DOI: 10.1006/JCOM.1998.0481 / rank | |||
Normal rank |
Latest revision as of 17:14, 10 December 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\) |
scientific article |
Statements
Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z]}\) (English)
0 references
11 April 1999
0 references
This paper presents fast numerical algorithms for factoring univariate polynomials with complex coefficients and for computing partial decomposition (PFDs) of rational functions in one complex variable. Rigorous proofs for the correctness of the algorithms and for favourable asymptotic time bounds with respect to bit complexity are given. Numerically stable and computationally feasible versions of PFD are specified first for the special case of rational functions with all singularities in the unit disk (the bounded case) and then for rational functions with arbitrarily distributed singularities. Two major algorithms for computing PFDs are presented. The first one is an extension of the splitting method by A. Schönhage (1982). The second algorithm is a Newton iteration for simultaneously improving the accuracy of all factors in an approximate PFD of a rational function. Algorithmically useful starting value conditions for the Newton algorithm are provided. Three subalgorithms are of independent interest. They compute the product of a sequence of polynomials, the sum of a sequence of rational functions, and the modular representation of a polynomial. All algorithms are described in a great detail, and numerous technical auxiliaries are provided which are also useful for the design and analysis of other algorithms in computational complex analysis. Combining the splitting circle method with simultaneous Newton iteration yields favourable time bounds, measured in bit iterations, for PFD, polynomial factoring, and root calculation. In particular, the time bounds for computing high accuracy PFDs, high accuracy factorizations, and high accuracy approximations for zeros of squarefree polynomials are linear in the output size, and hence optimal, up to logarithmic factors.
0 references
fast numerical algorithms
0 references
partial fraction decomposition
0 references
factoring univariate polynomials
0 references
rational functions
0 references
Newton's algorithm
0 references
splitting circle algorithm
0 references
complex coefficients
0 references
asymptotic time bounds
0 references
bit complexity
0 references
0 references
0 references
0 references
0 references