Studies in algorithms for fast structured matrices computations and their applications

Dense structured matrices are special matrices that arise in numerous applications such as control, signal and image processing, coding, partial differential and integral equations, and a variety of algebraic computations. Scaling and displacement operators associated to structured matrices help us exploit the underlying structure of a matrix when we devise fast and numerical reliable algorithms for various computational problems. The underlying characteristic properties of the structured matrices, which distinguish them from unstructured matrices, in particular from general matrices, is the dramatic decrease of the rank of the associated matrices obtained as the images of scaling and displacement operators applied to the given matrices.; Such image matrices are called scaling and displacement generators. They relate the three parts of this dissertation to each other.; In part I, for a Toeplitz or Toeplitz-like matrix T, we define a preconditioning applied to the matrix {dollar}Tsp{lcub}H{rcub}T.{dollar} This enables us to accelerate the conjugate gradient algorithm for solving Toeplitz and Toeplitz-like linear systems, thus extending the previous results of (PS).; In part II, we specify some initial assumptions that guarantee rapid refinement of a rough initial approximation to the inverse of a Cauchy-like matrix, by means of our new modifications of Newton's iteration.; Finally, in part III, we extend the algorithm of (PSLT) by using the properties of various classes of structured matrices and the known correlations among them, to solve the problems of multipoint polynomial evaluation and interpolation. Unlike (R88) and (P95), this approach allows complex input points {dollar}xsb0,cdots,xsb{lcub}n-1{rcub},{dollar} the nodes of evaluation and interpolation.