This thesis describes improvements of the periodic QZ algorithm and several variants of the Schur algorithm for block Toeplitz matrices. Documentation of the available software is included.

In this thesis, we present the O(n(log n)^2) superfast linear least squares Schur algorithm (ssschur). The algorithm we will describe illustrates a fast way of solving linear equations or linear least squares problems with low displacement rank. This program is based on the O(n^2) Schur algorithm speeded up via FFT. The algorithm solves a ill-conditioned Toeplitz-like system using Tikhonov regularization. The regularized system is Toeplitz-like of displacement rank 4. We also show the effect of choice of the regularization parameter on the quality of the image reconstructed.

The Pick–Nevanlinna interpolation problem, in its fullest generality, is as follows: Given domains D1, D2 in complex Euclidean spaces, and a set f¹ zi; wiº : 1 i N g D1 D2, where zi are distinct and N 2 š+, N 2, find necessary and sufficient conditions for the existence of a holomorphic map F : D1 ! D2 such that F¹ziº = wi, 1 i N. When such a map F exists, we say that F is an interpolant of the data. Of course, this problem is intractable at the above level of generality. However, two special cases of the problem — which we shall study in this thesis — have been of lasting interest: Interpolation from the polydisc to the unit disc. This is the case D1 = „n and D2 = „, where „ denotes the open unit disc in the complex plane and n 2 š+. The problem itself originates with Georg Pick’s well-known theorem (independently discovered by Nevanlinna) for the case n = 1. Much later, Sarason gave another proof of Pick’s result using an operator-theoretic approach, which is very influential. Using this approach for n 2, Agler–McCarthy provided a solution to the problem with the restriction that the interpolant is in the Schur– Agler class. This is notable because, when n = 2, the latter result completely solves the problem for the case D1 = „2; D2 = „. However, Pick’s approach can also be effective for n 2. In this thesis, we give an alternative characterization for the existence of a 3-point interpolant based on Pick’s approach and involving the study of rational inner functions. Cole–Lewis–Wermer lifted Sarason’s approach to uniform algebras — leading to a char-acterization for the existence of an interpolant in terms of the positivity of a large, rather abstractly-defined family of N N matrices. McCullough later refined their result by identifying a smaller family of matrices. The second result of this thesis is in the same vein, namely: it provides a characterization of those data that admit a „n-to-„ interpolant in terms of the positivity of a family of N N matrices parametrized by a class of polynomials. Interpolation from the unit disc to the spectral unit ball. This is the case D1 = „ and D2 = n , where n denotes the set of all n n matrices with spectral radius less than 1. The interest in this arises from problems in Control Theory. Bercovici–Foias–Tannenbaum adapted Sarason’s methods to give a (somewhat hard-to-check) characterization for the existence of an interpolant under a very mild restriction. Later, Agler–Young established a relation between the interpolation problem in the spectral unit ball and that in the symmetrized polydisc — leading to a necessary condition for the existence of an interpolant. Bharali later provided a new inequivalent necessary condition for the existence of an interpolant for any n and N = 2. In this thesis, we shall present a necessary condition for the existence of an interpolant in the case when N = 3. This we shall achieve by adapting Pick’s approach and applying the aforementioned result of Bharali.

This thesis describes improvements of the periodic QZ algorithm and several variants of the Schur algorithm for block Toeplitz matrices. Documentation of the available software is included.