Structured Matrices and Polynomials: Unified Superfast Algorithms

Structured matrices serve as a natural bridge between the areas of

algebraic computations with polynomials and numerical matrix

computations, allowing cross-fertilization of both fields. 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 and fast sine and cosine

transforms.

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

The primary intended readership for this work 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 graduate students and

new researchers who wish to study the rapidly exploding area of

computations with structured matrices and polynomials. Examples,

tables, figures, exercises, extensive bibliography, and index lend

this text to classroom use or self-study.