A superfast method for solving Toeplitz linear least squares problems.
type: Item
instance of: scholarly article
title: A superfast method for solving Toeplitz linear least squares problems.
zbMATH Open document ID: 1044.65033
DOI: 10.1016/S0024-3795(02)00495-0
author: Marc van Barel
author: G. Heinig
author: Peter Kravanja
published in: Linear Algebra and its Applications
publication date: 2003-05-25T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 65F20
zbMATH DE Number: 1915818
zbMATH Keywords: Toeplitz matrices
zbMATH Keywords: superfast algorithm
zbMATH Keywords: block circulant matrices
zbMATH Keywords: divide and conquer strategy
zbMATH Keywords: vector polynomial interpolation
zbMATH Keywords: numerical examples
zbMATH Keywords: least squares problem
zbMATH Keywords: discrete Fourier transform
zbMATH Keywords: Vandermonde block system
zbMATH Keywords: tangential interpolation problem
reviewed by: Otu Vaarmann
MaRDI profile type: Publication
cites work: Downdating of Szegö polynomials and data-fitting applications
cites work: Superfast Solution of Real Positive Definite Toeplitz Systems
cites work: Numerical experience with a superfast real Toeplitz solver
cites work: Asymptotically fast solution of Toeplitz and related systems of linear equations
cites work: QR factorization of Toeplitz matrices
cites work: Fast solution of toeplitz systems of equations and computation of Padé approximants
cites work: Linear algebra, rational approximation and orthogonal polynomials
cites work: A Fast Stable Solver for Nonsymmetric Toeplitz and Quasi-Toeplitz Systems of Linear Equations
cites work: Fast Parallel Algorithms for QR and Triangular Factorization
cites work: A General Orthogonalization Technique with Applications to Time Series Analysis and Signal Processing
cites work: Fast Toeplitz Orthogonalization Using Inner Products
cites work: A new algorithm for solving Toeplitz systems of equations
cites work: High performance algorithms for Toeplitz and block Toeplitz matrices
cites work: Fast Gaussian Elimination with Partial Pivoting for Matrices with Displacement Structure
cites work: Stable and Efficient Algorithms for Structured Systems of Linear Equations
cites work: New Fast Algorithms for Structured Linear Least Squares Problems
cites work: Q4840532
cites work: Solving Toeplitz systems after extension and transformation
cites work: Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. I: Transformations
cites work: Transformation techniques for Toeplitz and Toeplitz-plus-Hankel matrices. II: Algorithms
cites work: A fast block Hankel solver based on an inversion formula for block Loewner matrices
cites work: A fast Hankel solver based on an inversion formula for Loewner matrices
cites work: Hybrid algorithm for fast Toeplitz orthogonalization
cites work: Fast Toeplitz orthogonalization
cites work: A general module theoretic framework for vector M-Padé and matrix rational interpolation
cites work: Q4312943
cites work: A stabilized superfast solver for nonsymmetric Toeplitz systems
cites work: The prolate matrix
description: scientific article; zbMATH DE number 1915818