Stable row recurrences for the Padé table and generically superfast lookahead solvers for non-Hermitian Toeplitz systems

AbstractWe present general recurrences for the Padé table that allow us to skip ill- conditioned Padé approximants while we proceed along a row of the table. In conjunction with a certain inversion formula for Toeplitz matrices, these recurrences form the basis for fast algorithms for solving non-Hermitian Toeplitz systems. Under the assumption that the lookahead step size (i.e., the number of successive skipped approximants) remains bounded, we give both O(N2) and O(N log2N) algorithms which are (presumably) weakly stable. With little additional work, still in O(N2) operations, we can also obtain a decomposition of the Toeplitz matrix T according to TR = LD, where R is upper triangular, L is unit lower triangular, and D is block-diagonal. The relation to continued fractions is also discussed