A superfast method for solving Toeplitz linear least squares problems

AbstractIn this paper we develop a superfast O((m+n)log2(m+n)) complexity algorithm to solve a linear least squares problem with an m×n Toeplitz coefficient matrix. The algorithm is based on the augmented matrix approach. The augmented matrix is further extended to a block circulant matrix and DFT is applied. This leads to an equivalent tangential interpolation problem where the nodes are roots of unity. This interpolation problem can be solved by a divide and conquer strategy in a superfast way. To avoid breakdowns and to stabilize the algorithm pivoting is used and a technique is applied that selects “difficult” points and treats them separately. The effectiveness of the approach is demonstrated by several numerical examples