|
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
|
|
|
|
0024-3795
|
|
|
DOI
|
|
|
|
10.1016/S0024-3795(02)00495-0
|
|
|
Volume/pages
|
|
|
|
366
(2003)
, p. 441-457
|
|
|
ISI
|
|
|
|
000182667200025
|
|
|
Full text (Publisher's DOI)
|
|
|
|
|
|
|
Full text (publisher's version - intranet only)
|
|
|
|
|
|