Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

FAST SOLUTION OF TOEPLITZ SYSTEMS OF EQUATIONS AND COMPUTATION OF PADE APPROXIMANTS

IP.com Disclosure Number: IPCOM000148841D
Original Publication Date: 1980-Jan-08
Included in the Prior Art Database: 2007-Mar-30
Document File: 36 page(s) / 2M

Publishing Venue

Software Patent Institute

Related People

Brent, Richard P.: AUTHOR [+4]

Abstract

Richard P. Brent Fred G. Gustavson David Y.Y. YunDept. of Computer Science Mathematical Sciences Dept. Mathematical Sciences Dept. Australian National University IBM Watson Research Center IBM Watson Research Center Box 4 P.O. Box 218 P.O. Box 218Canberra, ACT 2600, Australia Yorktown Heights, NY 10598 Yorktown Heights, NY 10598 Typed by: Margaret M. Casey, Fred G. Gustavson, Nancy G. Perry and David Y.Y. Yun Abstract: We present two new algorithms, ADT and MDT, for solving order-n Toeplitz systems of linear 2 equations Tz b in time O(n log n) and space O(n). The fastest algorithms previously known, such as Trench's algorithm, require time &3(n2) and require that all principal submatrices of T be nonsingular. Our algorithm ADT requires only that T be nonsingular. Both our algorithms for Toeplitz systems are derived from algorithms for computing entries in the Pad6 Table for a given power series. We prove that entries in the Pad6 Table can be computed by the Extended Euclidean algorithm. We describe an algorithm EMGCD (Extended Middle GCD) which is faster than the algorithm HGCD of Aho, Hopcroft and ~llman, althou5 both require time O(n log2n), and we generalize EMGCD to produce PRSDC (Polynomial Remainder Sequence Divide and

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 6% of the total text.

Page 1 of 36

RC 81 73 (fj34952) 1/8/80 Mathematics 36 pages

FAST SOLUTION OF TOEPLITZ SYSTEMS OF EQUATIONS AND COMPUTATION OF PADE APPROXIMANTS

Richard P. Brent Fred G. Gustavson David Y.Y. Yun
Dept. of Computer Science Mathematical Sciences Dept. Mathematical Sciences Dept. Australian National University IBM Watson Research Center IBM Watson Research Center Box 4 P.O. Box 218 P.O. Box 218
Canberra, ACT 2600, Australia Yorktown Heights, NY 10598 Yorktown Heights, NY 10598

Typed by: Margaret M. Casey, Fred G. Gustavson, Nancy G. Perry and David Y.Y. Yun

Abstract:

We present two new algorithms, ADT and MDT, for solving order-n Toeplitz systems of linear
2

equations Tz = b in time O(n log n) and space O(n). The fastest algorithms previously known, such as Trench's algorithm, require time &3(n2) and require that all principal submatrices of T be nonsingular. Our algorithm ADT requires only that T be nonsingular.

   Both our algorithms for Toeplitz systems are derived from algorithms for computing entries in the Pad6 Table for a given power series. We prove that entries in the Pad6 Table can be computed by the Extended Euclidean algorithm. We describe an algorithm EMGCD (Extended Middle GCD) which is faster than the algorithm HGCD of Aho, Hopcroft and ~llman, althou5 both require time O(n log2n), and we generalize EMGCD to produce PRSDC (Polynomial Remainder Sequence Divide and -

Conquer) which produces any iterate in the PRS, not just t?;e middle term, in tim&(n log2?.

   Applying PRSDC to the polynomials Uo(x) = x2"+' and U,(x) = a. + alx + ... + aZnx?n gives algorithm AD (Anti-Diagonal), which computes any (m,p) entry along the antidiagonal m + p = 2n of the Pad6 ~ableTor in time O(n log2n). Our other algorithm, MD (Main-Diagonal), computes any diagonal entry (n,n) in the Pad6 Table for a normal power series, alsoin t&e O(n log2n). MD is related to Schonhage's fast continued fraction algorithm.

   A Toeplitz matrix T is naturally associated with U1, and the (n,n) Pad6 approximation to U1
gives the first column of T1.

                    We show how a formula due to Trench can be used to compute the solution z of Tz = b in time O(n log n) from the first row and column of T-l. Thus, the Pad6 Table algorithms AD and MD give O(n log2n) Toeplitz algorithms ADT and MDT.

   Trench's formula breaks down in certain degenerate cases, but in such cases a companion formula, the discrete analog of the Christoffel-Darboux formula, is valid and may be used to compute z in time O(n log2n) via the fast computation (by algorithm AD) of at most four Pad6 approximants. We also apply our results to obtain new complexity bounds for the solution of banded Toeplitz systems and for BCH decoding via Berlekamp's algorithm.

[This page contains 1 picture or other non-text object]

Page 2 of 36

1. Introduction

   We present two new algorithms for solving (n+l) by (n+l) Toeplitz systems of line...