This user-friendly, engaging textbook 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. The book goes beyond research frontiers and, apart from very recent research articles, includes previously unpublished results.

Our Subjects and Objectives. This book is about algebraic and symbolic computation and numerical computing (with matrices and polynomials). It greatly extends the study of these topics presented in the celebrated books of the seventies, [AHU] and [BM] (these topics have been under-represented in [CLR], which is a highly successful extension and updating of [AHU] otherwise). Compared to [AHU] and [BM] our volume adds extensive material on parallel com putations with general matrices and polynomials, on the bit-complexity of arithmetic computations (including some recent techniques of data compres sion and the study of numerical approximation properties of polynomial and matrix algorithms), and on computations with Toeplitz matrices and other dense structured matrices. The latter subject should attract people working in numerous areas of application (in particular, coding, signal processing, control, algebraic computing and partial differential equations). The au thors' teaching experience at the Graduate Center of the City University of New York and at the University of Pisa suggests that the book may serve as a text for advanced graduate students in mathematics and computer science who have some knowledge of algorithm design and wish to enter the exciting area of algebraic and numerical computing. The potential readership may also include algorithm and software designers and researchers specializing in the design and analysis of algorithms, computational complexity, alge braic and symbolic computing, and numerical computation.

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 toclassroom use or self-study.

Our Subjects and Objectives. This book is about algebraic and symbolic computation and numerical computing (with matrices and polynomials). It greatly extends the study of these topics presented in the celebrated books of the seventies, [AHU] and [BM] (these topics have been under-represented in [CLR], which is a highly successful extension and updating of [AHU] otherwise). Compared to [AHU] and [BM] our volume adds extensive material on parallel com putations with general matrices and polynomials, on the bit-complexity of arithmetic computations (including some recent techniques of data compres sion and the study of numerical approximation properties of polynomial and matrix algorithms), and on computations with Toeplitz matrices and other dense structured matrices. The latter subject should attract people working in numerous areas of application (in particular, coding, signal processing, control, algebraic computing and partial differential equations). The au thors' teaching experience at the Graduate Center of the City University of New York and at the University of Pisa suggests that the book may serve as a text for advanced graduate students in mathematics and computer science who have some knowledge of algorithm design and wish to enter the exciting area of algebraic and numerical computing. The potential readership may also include algorithm and software designers and researchers specializing in the design and analysis of algorithms, computational complexity, alge braic and symbolic computing, and numerical computation.