Divide-and-Conquer Solutions of Least-Squares Problems for Matrices with Displacement Structure
- 1 January 1991
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 12 (1) , 128-145
- https://doi.org/10.1137/0612010
Abstract
A divide-and-conquer implementation of a generalized Schur algorithm enables (exact and) least-squares solutions of various block-Toeplitz or Toeplitz-block systems of equations with $O ( \alpha ^3 n\log ^2 n )$ operations to be obtained, where the displacement rank $\alpha $ is a small constant (typically between two to four for scalar near-Toeplitz matrices) independent of the size of the matrices.
Keywords
This publication has 16 references indexed in Scilit:
- Fast solution of toeplitz systems of equations and computation of Padé approximantsPublished by Elsevier ,2004
- Superfast Solution of Real Positive Definite Toeplitz SystemsSIAM Journal on Matrix Analysis and Applications, 1988
- A new algorithm for solving Toeplitz systems of equationsLinear Algebra and its Applications, 1987
- Remarks on a displacement-rank inversion method for Toeplitz systemsLinear Algebra and its Applications, 1982
- A fast algorithm for normal incidence seismogramsGeophysics, 1982
- Asymptotically fast solution of toeplitz and related systems of linear equationsLinear Algebra and its Applications, 1980
- Displacement ranks of matrices and linear equationsJournal of Mathematical Analysis and Applications, 1979
- Inverses of Toeplitz Operators, Innovations, and Orthogonal PolynomialsSIAM Review, 1978
- An Algorithm for the Inversion of Finite Toeplitz MatricesJournal of the Society for Industrial and Applied Mathematics, 1964
- Über Potenzreihen, die im Innern des Einheitskreises beschränkt sind.Journal für die reine und angewandte Mathematik (Crelles Journal), 1917