Linear algebra and its applications vol:366 pages:441-457
In this paper we develop a superfast O((m + n) log(2)(m + n)) complexity algorithm to solve a linear least squares problem with an m x 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. (C) 2003 Elsevier Science Inc. All rights reserved.