1. Displacement Structure and Array Algorithms
T. Kailath · Society for Industrial and Applied Mathematics eBooks · 1999
1.1 INTRODUCTION Many problems in engineering and applied mathematics ultimately require the solution of n × n linear systems of equations. For small-size problems, there is often not much else to do except to use one of the already standard methods of solution such as Gaussian elimination. However, in many applications, n can be very large (n ∼ 1000, n ∼ 1,000,000) and, moreover, the linear equations may have to be solved over and over again, with different problem or model parameters, until a satisfactory solution to the original physical problem is obtained. In such cases, the burden, i.e., the number of flops required to solve an n × n linear system of equations, can become prohibitively large. This is one reason why one seeks in various classes of applications to identify special or characteristic structures that may be assumed in order to reduce the computational burden. Of course, there are several different kinds of structure. A special form of structure, which already has a rich literature, is sparsity; i.e., the coefficient matrices have only a few nonzero entries. We shall not consider this already well studied kind of structure here. Our focus will be on problems, as generally encountered in communications, control, optimization, and signal processing, where the matrices are not sparse but can be very large. In such problems one seeks further assumptions that impose particular patterns among the matrix entries. Among such assumptions (and we emphasize that they are always assumptions) are properties such as time-invariance, homogeneity, stationarity, and rationality, which lead to familiar matrix structures, such as Toeplitz, Hankel, Vandermonde, Cauchy, Pick, etc. Several fast algorithms have been devised over the years to exploit these special structures. The numerical (accuracy and stability) properties of several of these algorithms also have been studied, although, as we shall see from the chapters in this volume, the subject is by no means closed even for such familiar objects as Toeplitz and Vandermonde matrices.