__ Page 1 of 4 __
**Fast Algorithm for Solving Toeplitz Systems of Equations **

Disclosed herein is the first 0(n log/2/n) method to solve

Toeplitz systems of equations which handles all degenerate and
special cases. (The symbol 0 used in formulas in this and subsequent
paragraphs refers to the constant "big Oh" defined in reference [4].)

Let matrix an consider solving Tz=b. Previous methods [1] require
0(n/2/) operations to solve Tz=b. Algorithm Toeplitz described
herein finds z, given T and b, in 0(n log/2/n).

A Toeplitz matrix is a generalization of the FFT (Fast Fourier Transform)
matrix (circulant matrix); indeed, if a(n+i) = a (i-1), i=1,...,n, then T is an FFT
matrix. The method described here~n consists of two main steps.

(A) Compute the first column x and the first row y of the inverse of T. If T =
x(0) = y(0) not equal 0, then append zero to each of the vectors x and y. If x(0) =
0, then compute x and y as the first column and row of T(B), where T(B) is a
Toeplitz matrix which is an augmented matrix of T(B) (defined below).

(B) Form polynomials X(t), Y(t), and B(t) from the vectors x,y, and b.
Compute the solution 2 as a combination of four polynomial products that are
formed with X,Y, and B as inputs.

The computations in steps (A) and (B) above will be carried out by algorithms
A (see (3) and B. Let a = (a(0),a(1),...a(2n)) describe the Toeplitz matrix T,
b=(b(0),...,b(n)) the right hand side vector, and z=(z(0),...,z(n)) the solution
vector. The algorithm Toeplitz is now presented.

The basis of step (B) above (see[2]) is the following:

Suppose Tx=e(0) and T/t/y=e(0) and x(0)=y(0)not equal 0. Then S, the
inverse of T, has the following representation Algorithm A is a computational
procedure which computes either x,y for See Original

The importance of formula (1) is that the solution z(=Sb) can
be computed in 0(n log n) operations by FFT if x and y are known.
Note that S in (1) is not explicitly calculated and it is the form
of S in (1) that is important. Now z can be computed in 0(n log

n) since all the matrices in (1) are Toeplitz and the product of a
Toeplitz matrix and a vector can be done, via FFT, in 0(n log n),
Indeed, the computation for z(=Sb) is done by forming a combination
of four products of polynomials of size n. The reason it is
necessary to consider the Toeplitz matrix T(B) is that occasionally
x(0)=0 and then formula (1) does not apply. However, when j1x(0)=0
for T, B is chosen so that x(0) not equal for T(B).

It has recently been shown that the solution Tx=e(09 and T(t)y=e(0) or
T(B)x=e(0) and T(B)y=e(0) are by-products of the extended Euclidean
computation.

1

__ Page 2 of 4 __
Algorithm A is a computational procedure which computes either x,y for T as
combinations of certain terms in the polynomial remainder sequence T(B) of the
two polynomials U(0)=t/2n+1/ and U(1)=a(0)+a(1)t+... +a(2n)t/2n/.

Algorithm A computes x and y in O(n log/2/n). Since the cost of Algorithm B
is O(n log n) the total cost of computing z, given T and b is O...