Title 



A superfast method for solving Toeplitz linear least squares problems


Author 





Abstract 



In 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.  

Language 



English


Source (journal) 



Linear algebra and its applications.  New York, N.Y. 

Publication 



New York, N.Y. : 2003


ISSN 



00243795


Volume/pages 



366(2003), p. 441457


ISI 



000182667200025


Full text (Publishers DOI) 


 

Full text (publishers version  intranet only) 


 
