Abstract

This paper considers the problem of effective algorithms for some problems having structured coefficient matrices. Examples of such problems include rational approximation and rational interpolation. The corresponding coefficient matrices include Hankel, Toeplitz and Vandermonde-like matrices. Effective implies that the algorithms studied are suitable for implementation in either a numeric environment or else a symbolic environment.

The paper includes two algorithms for the computation of rational interpolants which are both effective in symbolic environments. The algorithms use arithmetic that is free of fractions but at the same time control the growth of coefficients during intermediate computations. One algorithm computes along a path of closest normal points to an offdiagonal path while the second computes along an arbitrary path using a look--ahead strategy. Along an antidiagonal path the look--ahead recurrence is closely related to the Subresultant PRS algorithm for polynomial GCD computation. Both algorithms are an order of magnitude faster than alternate methods which are effective in symbolic environments.