Matrix and polynomial computations are fundamental to the theory and practice of computing. The authors present a systematic treatment of algorithms and complexity in these two related areas. Their study of computations with Toeplitz matrices and other dense structured matrices demonstrates the links between numerical and algebraic approaches to computation, both of which are extensively applied. Primarily a text for advanced graduate students in mathematics and computer science, but also useful for designers of algorithms and software and for researchers in algebraic computing, numerical computational mathematics, and numerical analysis.