Fully efficient systolic arrays for the solution of Toeplitz matrices using Schur algorithm [1] have been obtained. By applying clustering mapping method [2], the complexity of the algorithm is 0(n) and it requires n/2 processing elements as opposed to n processing elements developed elsewhere [1]. The motivation of this thesis is to obtain efficient pipeline arrays by using the synthesis procedure to implement Toeplitz matrix solution. Furthermore, we will examine pipeline structures for the Toeplitz system factorization and back-substitution by obtaining clustering and Multi-Rate Array structures. These methods reduce the number of processing elements and enhance the computational speed. Comparison and advantage of these methods to other method will be presented. / Graduation date: 1992

University of Macau / Faculty of Science and Technology / Department of Mathematics

This paper is devoted to asymptotic estimates for the condition numbers $\kappa(T_n(a))=||T_n(a)|| ||T_n^(-1)(a)||$ of large $n\cross n$ Toeplitz matrices $T_N(a)$ in the case where $\alpha \element L^\infinity$ and $Re \alpha \ge 0$ . We describe several classes of symbols $\alpha$ for which $\kappa(T_n(a))$ increases like $(log n)^\alpha, n^\alpha$ , or even $e^(\alpha n)$ . The consequences of the results for singular values, eigenvalues, and the finite section method are discussed. We also consider Wiener-Hopf integral operators and multidimensional Toeplitz operators.

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.

We implement an eigenvalue solving algorithm proposed by Ng and Trench, specialized for Toeplitz(-like) matrices, utilizing root finding in conjunction with an iteratively calculated version of the characteristic polynomial. The solver also yields corresponding eigenvectors as a free bi-product. We combine the algorithm with matrix-less methods in order to yield eigenvector approximations, and examine its behavior both regarding demands for time and computational power. The algorithm is fully parallelizable, and although solving of all eigenvalues to the bi-Laplacian discretization matrix - which we used as a model matrix - is not superior to standard methods, we see promising results when using it as an eigenvector solver, using eigenvector approximations from standard solvers or a matrix-less method. We also note that an advantage of the algorithm we examine is that it can calculate singular, specific eigenvalues (and the corresponding eigenvectors), anywhere in the spectrum, whilst standard solvers often have to calculate all eigenvalues, which could be a useful feature. We conclude that - while the algorithm shows promising results - more experiments are needed, and propose a number of topics which could be studied further, e.g. different matrices (Toeplitz-like, full), and looking at even larger matrices.

We consider random symmetric Toeplitz matrices of size n. Assuming that the entries on the diagonals are independent centered random variables with finite γ-th moment (γ>2), a law of large numbers is established for the largest eigenvalue. Following the approach of Sen and Virág (2013), in the limit of large n, the largest rescaled eigenvalue is shown to converge to the limit 0.8288... . The background theory is explained and some symmetry results on the eigenvectors of the Toeplitz matrix and an auxiliary matrix are presented. A numerical investigation illustrates the rate of convergence and the oscillatory nature of the eigenvectors of the Toeplitz matrix. Finally, the possibility of proving a limiting distribution for the largest eigenvalue is discussed, and suggestions for future research are made. / Vi betraktar stokastiska Toeplitz-matriser av storlek n. Givet att elementen på diagonalerna är oberoende, centrerade stokastiska variabler med ändligt γ-moment (γ>2), fastställer vi ett stora talens lag för det största egenvärdet. Med metoden från Sen och Virág (2013) visar vi att det största omskalade egenvärdet konvergera mot gränsen 0.8288... . Bakgrundsteorin förklaras och några symmetriresultat för Toeplitz-matrisens egenvektorer presenteras. En numerisk undersökning illustrerar konvergenshastigheten och Toeplitz-matrisens egenvektorers periodiska natur. Slutligen diskuteras möjligheten att bevisa en asymptotisk fördelning för de största egenvärderna och förslag för fortsatt forskning läggs fram.

An isospectral algorithm is one which manipulates a matrix without changing its spectrum. In this thesis we study three interrelated examples of isospectral algorithms, all pertaining to Toeplitz matrices in some fashion, and one directly involving orthogonal polynomials. The first set of algorithms we study come from discretising a continuous isospectral flow designed to converge to a symmetric Toeplitz matrix with prescribed eigenvalues. We analyse constrained, isospectral gradient flow approaches and an isospectral flow studied by Chu in 1993. The second set of algorithms compute the spectral measure of a Jacobi operator, which is the weight function for the associated orthogonal polynomials and can include a singular part. The connection coefficients matrix, which converts between different bases of orthogonal polynomials, is shown to be a useful new tool in the spectral theory of Jacobi operators. When the Jacobi operator is a finite rank perturbation of Toeplitz, here called pert-Toeplitz, the connection coefficients matrix produces an explicit, computable formula for the spectral measure. Generalisation to trace class perturbations is also considered. The third algorithm is the infinite dimensional QL algorithm. In contrast to the finite dimensional case in which the QL and QR algorithms are equivalent, we find that the QL factorisations do not always exist, but that it is possible, at least in the case of pert-Toeplitz Jacobi operators, to implement shifts to generate rapid convergence of the top left entry to an eigenvalue. A fascinating novelty here is that the infinite dimensional matrices are computed in their entirety and stored in tailor made data structures. Lastly, the connection coefficients matrix and the orthogonal transformations computed in the QL iterations can be combined to transform these pert-Toeplitz Jacobi operators isospectrally to a canonical form. This allows us to implement a functional calculus for pert-Toeplitz Jacobi operators.

This paper is devoted to asymptotic estimates for the condition numbers $\kappa(T_n(a))=||T_n(a)|| ||T_n^(-1)(a)||$ of large $n\cross n$ Toeplitz matrices $T_N(a)$ in the case where $\alpha \element L^\infinity$ and $Re \alpha \ge 0$ . We describe several classes of symbols $\alpha$ for which $\kappa(T_n(a))$ increases like $(log n)^\alpha, n^\alpha$ , or even $e^(\alpha n)$ . The consequences of the results for singular values, eigenvalues, and the finite section method are discussed. We also consider Wiener-Hopf integral operators and multidimensional Toeplitz operators.

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.

This research develops efficient solution methods for linear systems with scalar and multi-level Toeplitz structure. Toeplitz systems are common in one-dimensional signal-processing applications, and typically correspond to temporal- or spatial-invariance in the underlying physical phenomenon. Over time, a number of algorithms have been developed to solve these systems economically by exploiting their structure. These developments began with the Levinson-Durbin recursion, a classical fast method for solving Toeplitz systems that has become a standard algorithm in signal processing. Over time, more advanced routines known as superfast algorithms were introduced that are capable of solving Toeplitz systems with even lower asymptotic complexity. For multi-dimensional signals, temporally- and spatially-invariant systems have linear-algebraic descriptions characterized by multi-level Toeplitz matrices, which exhibit Toeplitz structure on multiple levels. These matrices lack the same algebraic properties and structural simplicity of their scalar analogs. As a result, it has proven exceedingly difficult to extend the existing scalar Toeplitz algorithms for their treatment. This research presents algorithms to solve scalar and two-level Toeplitz systems through a constructive approach, using methods devised for specialized cases to build more general solution methods. These methods extend known scalar Toeplitz inversion results to more general scalar least-squares problems and to multi-level Toeplitz problems. The resulting algorithms have the potential to provide substantial computational gains for a large class of problems in signal processing, such as image deconvolution, non-uniform resampling, and the reconstruction of spatial volumes from non-uniform Fourier samples.