Fast algorithms for Toeplitz and Hankel matrices

The paper gives a self-contained survey of fast algorithms for solving linear systems of equations with Toeplitz or Hankel coefficient matrices. It is written in the style of a textbook. Algorithms of Levinson-type and Schur-type are discussed. Their connections with triangular factorizations, Padè recursions and Lanczos methods are demonstrated. In the case in which the matrices possess additional symmetry properties, split algorithms are designed and their relations to butterfly factorizations are developed.