ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

15. Numerical Analysis and Scientific Computing

1991 MS Classification: 65Y20, 68Q25, 65H05, 65G10 Kirrinnis, Peter, Universität Bonn, Germany Fast algorithms for partial fractions An approximate partial fraction decomposition (APFD) of a rational function f = q/p ∈ C(z) is given by approximate factors p_{1}, …, p_{l} of p and corresponding numerators q_{1}, …, q_{l}. Define p̃ and q̃ by p̃ = p_{1} ⋯ p_{l} and q̃/p̃ = ∑ q_{j}/p_{j}. The parameters s, t, γ ∈ N measure the quality of the APFD as follows: An (s, t, γ)-APFD fulfils ∥p − p̃∥ < 2^{−s} and ∥q − q̃∥ < 2^{−t} for a norm ∥ · ∥ on C[z], and for all j, any two roots of p_{j} have distance at most 2^{−γ}. We describe and analyze algorithms that compute an (s, t, γ)-APFD from the coefficients of q and p with deg q ≤ deg p ≤ n with O(n^{3} · γ + n · (s + t)) single precision operations (neglecting logarithmic factors). The relation to root finding algorithms is discussed. The author’s papers in Proc. ISSAC 1992, ACM (pp. 16–26) and Proc. ISSAC 1998, ACM (to appear) provide details.