Polynomial and Matrix Computations

This title is a reference for a graduate course in symbolic computation or computer algebra.

---

'We strongly recommend this book as a reference for a graduate course in symbolic computation or computer algebra. The book...is an excellent companion for researchers and advanced students. Given, moreover, that it is a handy reference book, it should be present in every good library.' --- SIGSAM Bulletin (on Volume I) Polynomial and matrix computations are the backbone of modern sciences, engineering, and communication. In Volume II of this two- part work, the authors continue their systematic treatment of fundamental algorithms and complexity in these two related areas. As in Volume I ("Fundamental Algorithms"), the present work demonstrates the correlation among matrix and other polynomial computations as well as between numerical and algebraic approaches to computation. Unlike the universal coverage of the two fields of polynomial and matrix computations in Volume I, the focus in Volume II is on several major specialized topics such as matrix multiplication and polynomial rootfinding. For each subject, the treatment begins with classical fundamental problems and gradually brings the reader to and beyond the frontiers of current research.
This includes a study of the most recent and currently most effective practical algorithms (by I. Kaporin) for fast, numerically stable, and memory efficient matrix multiplication (by the POSSO-FRISCO international project) for user- friendly, multi-purpose, fast, and reliable polynomial rootfinding. Furthermore, the authors demonstrate how fundamental theoretical advances enable dramatic improvement of some major practical computations for queueing, Markov chains, and image restoration. The book is designed as a text for advanced graduate students in