Structured Matrices and Polynomials

This book covers most fundamental numerical and algebraic computations with Toeplitz, Hankel, Vandermonde, Cauchy, and other popular structured matrices. Throughout the computations, the matrices are represented by their compressed images, called displacements, enabling both a unified treatment of various matrix structures and dramatic saving of computer time and memory. The resulting superfast algorithms allow further dramatic parallel acceleration using FFT. Included are specific applications to other fields, in particular, superfast solutions to: various fundamental problems of computer algebra * the tangential Nevanlinna-Pick and matrix Nehari problems * loss-resilient encoding/decoding problems. The primary intended readership includes researchers, algorithm designers, and advanced graduate students in the fields of computations with structured matrices, computer algebra, and numerical rational interpolation. The book goes beyond research frontiers and, apart from very recent research articles, includes yet unpublished results. To serve a wider audience, the presentation unfolds systematically and is written in a user-friendly engaging style. Only some preliminary knowledge of the fundamentals of linear algebra is required. This makes the material accessible to novices who wish to study the rapidly exploding area of computations with structured matrices and polynomials. Examples, tables, figures, exercises, and an extensive bibliography lend this text to classroom use or self-study.