A superfast method for solving Toeplitz linear least squares problems. (Q1874682)

Standard algorithms for solving linear least squares problems require \(O(mn^2)\) flops, algorithms that require only \(O(mn)\) flops are called fast, algorithms that require less operations are called superfast. In this paper a superfast \(O((m+n)\log(m+n))\) complexity algorithm for solving a least squares problem with an \(m\times n\) Toeplitz coefficient matrix is developed. It is based on the augmented matrix approach that relates the \(m\times n\) least squares problem with an equivalent \((m+ n)\times(m+ n)\) linear system. This system is transformed by means of the discrete Fourier transform into a Vandermonde block system (into a tangential interpolation problem) which is solved by a divide and conquer strategy in a superfast way. To avoid breakdowns and to guarantee a certain degree of stability ``difficult'' interpolation points are selected out during the execution of the algorithm and are treated in the standard fast (i.e. not superfast ) way at the end. The presented results of computational experiments show that the algorithm under discussion is indeed superfast (as long as the number of difficult points is small compared to the total number of interpolation points).