| Home > Publications > Reports > Numerical Analysis and Applied Mathematics (TW) |
TW 336
M. Van Barel, G. Heinig, P. Kravanja
A superfast method for solving Toeplitz linear least squares problems
Abstract
In this paper we develop a superfast algorithm to solve the linear least squares problem for a Toeplitz matrix. The original problem is first transformed into solving a linear $2 \times 2$ block system where each block is a Toeplitz matrix. These Toeplitz blocks are extended into circulant blocks introducing new unknowns. Finally the block circulant linear system is transformed into an interpolation problem where a vector polynomial is sought satisfying certain tangential interpolation conditions for the roots of unity and having a specific degree for each of his components. This interpolation problem can be solved in a superfast way by a divide and conquer strategy. The effectiveness of the approach is demonstrated by several numerical examples.
report.pdf / mailto: M. Van Barel