Power Series Remainder Sequences and Pade' Fractions Over an Integral Domain

S. Cabay and P. Kossowski

Abstract

For univariate power series with coefficients over an integral domain, the notions of power series pseudo-division and power series remainder sequences are introduced and developed. By appealing to the theory of resultants, an algorithm is developed for constructing power series remainder sequences in which the sizes of the coefficients of successive remainders grow linearly, only.

The algorithm computes also a cofactor sequence, which is shown to be associated with a given power series remainder sequence. The cofactor sequence yields directly all the Pade' fractions along some specific off-diagonal path of the Pade' table for a pair of power series ( A(z), B(z) ). When the sizes of the coefficients of A(z) and B(z) are bounded by k, in the normal case, the algorithm computes Pade' fractions of type (m , n) in time
O(k^2*(m + n)^4). In the abnormal case, and depending on the nature of abnormalities, the time complexity can reach O(k^2*( m + n )^5). For computing Pade' fractions, the algorithm compares favorably with fraction-free methods, which have a time complexity O(k^2*( m + n )^5) even in the normal case.

When applied to polynomials, rather than to power series, the algorithm, for one specific off-diagonal path, corresponds to Euclid's extended algorithm for computing the greatest common divisor of two polynomials.

[University of Alberta]
University of Alberta 		[Department of Computing Science]
Computing Science 		[Stan Cabay's home page]
Home