Matrix and polynomial computations are fundamental to the theory and practice of computing. The authors present here a systematic treatment of algorithms and complexity in these two related areas. Its study of computations with Toeplitz matrices and other dense structured matrices demonstrates the links between numerical and algebraic approaches to computation. The authors begin with classical fundamental problems and gradually introduce the reader to current research. In particular, the book provides improved parallel algorithms for computations with structured matrices and their further applications to some fundamental computations with matrices and polynomials. The book is designed as a text for advanced graduates in mathematics and computer science.