Fast Reliable Algorithms for Matrices with Structure

T. Kailath and A. H. Sayed, Fast Reliable Algorithms for Matrices with Structure, SIAM, PA, 1999.


This book is the first to pay special attention to the combined issues of speed and numerical reliability in algorithm development. These two requirements have often been regarded as competitive, so much so that the design of fast and numerically reliable algorithms for large-scale structured systems of linear equations, in many cases, remains a significant open issue. Fast Reliable Algorithms for Matrices with Structure helps bridge this gap by providing the reader with recent contributions written by leading experts in the field.

The authors deal with both the theory and the practice of fast numerical algorithms for large-scale structured linear systems. Each chapter covers in detail different aspects of the most recent trends in the theory of fast algorithms, with emphasis on implementation and application issues. Both direct and iterative methods are covered.

This book is not merely a collection of articles. The editors have gone to considerable lengths to blend the individual papers into a consistent presentation. Each chapter exposes the reader to some of the most recent research while providing enough background material to put the work into proper context.


Engineers with interest in fast computational methods, especially for large-scale design problems in signal processing, estimation, control, system identification, and adaptive systems, will find the book essential. Applied mathematicians, numerical analysts, and computer scientists will want this book in their libraries.

About the Editors

Thomas Kailath is Hitachi America Professor in Engineering at Stanford University. He is the author of Linear Systems (Prentice-Hall, 1980) and coauthor of Discrete Neural Computation: A Theoretical Foundation (Prentice-Hall, 1995), Indefinite Quadratic Estimation and Control (SIAM, 1999), and Linear Estimation (Prentice-Hall, in press). Among other honors, he has held Guggenheim and Churchill fellowships, was awarded the 1995 IEEE Education Medal, and is a member of the National Academy of Engineering and the American Academy of Arts and Sciences.

Ali H. Sayed is Associate Professor of Electrical Engineering at the University of California, Los Angeles. He is coauthor of Indefinite Quadratic Estimation and Control (SIAM, 1999) and Linear Estimation (Prentice-Hall, 2000). He serves on the editorial board of SIAM Journal on Matrix Analysis and Applications and is the co-recipient (with T. Kailath) of the 1996 IEEE Donald G. Fink Award.


Contributors; Preface; Notation; Chapter 1: Displacement Structure and Array Algorithms, Thomas Kailath; Chapter 2: Stabilized Schur Algorithms, Shivkumar Chandrasekaran and Ali H. Sayed; Chapter 3: Fast Stable Solvers for Structured Linear Systems, Ali H. Sayed and Shivkumar Chandrasekaran; Chapter 4: Stability of Fast Algorithms for Structured Linear Systems, Richard P. Brent; Chapter 5: Iterative Methods for Linear Systems with Matrix Structure, Raymond H. Chan and Michael K. Ng; Chapter 6: Asymptotic Spectral Distribution of Toeplitz-Related Matrices, Paolo Tilli; Chapter 7: Newton’s Iteration for Structured Matrices, Victor Y. Pan, Sheryl Branham, Rhys E. Rosholt, and Ai-Long Zheng; Chapter 8: Fast Algorithms with Applications to Markov Chains and Queueing Models, Dario A. Bini and Beatrice Meini; Chapter 9: Tensor Displacement Structures and Polyspectral Matching, Victor S. Grigorascu and Phillip A. Regalia; Chapter 10: Minimal Complexity Realization of Structured Matrices, Patrick Dewilde; Appendix A: Useful Matrix Results, Thomas Kailath and Ali H. Sayed; Appendix B: Elementary Transformations, Thomas Kailath and Ali H. Sayed; Bibliography; Index.

1999 / xvi + 342 pages / Softcover / ISBN 0-89871-431-1
List Price $59.50 / Member Price $47.60 / Order Code OT67