Asymptotically fast solution of Toeplitz and related systems of linear equations

DOI10.1016/0024-3795(80)90161-5zbMath0458.65018OpenAlexW2041165203MaRDI QIDQ1151720

Brian D. O. Anderson, Bitmead, Robert R.

Publication date: 1980

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0024-3795(80)90161-5

zbMATH Keywords

computational complexity Toeplitz matrices asymptotically fast solution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items

A superfast method for solving Toeplitz linear least squares problems., Modify Levinson algorithm for symmetric positive definite Toeplitz system, Survey article: continued fractions associated with Wiener-Levinson filters, frequency analysis, moment theory and polynomials orthogonal on the unit circle, Minimal eigenvalue of a real symmetric positive definite Toeplitz matrix, A new algorithm for solving Toeplitz systems of equations, Every matrix is a product of Toeplitz matrices, A recursive partitioning algorithm for matrix inversion on parallel computers, The stability of inversion formulas for Toeplitz matrices, Discrete Riemann-Hilbert problems, interpolation of simply closed curves, and numerical conformal mapping, Stability analysis of a general Toeplitz system solver, The weak and strong stability of algorithms in numerical linear algebra, Parallel computation of polynomial GCD and some related parallel computations over abstract fields, New classes of matrix decompositions, Iterative inversion of structured matrices, Stabilité numérique de l'algorithme de Levinson, A stabilized superfast solver for indefinite Hankel systems, Classical foundations of algorithms for solving positive definite Toeplitz equations, The fast Slepian transform, On Matrices With Displacement Structure: Generalized Operators and Faster Algorithms, Matrix computations and polynomial root-finding with preprocessing, Randomized preprocessing versus pivoting, A finite elements approach for spread contract valuation via associated two-dimensional PIDE, Recursive self preconditioning method based on Schur complement for Toeplitz matrices, Algorithms for simultaneous Hermite-Padé approximations, Superfast solution of Toeplitz systems based on syzygy reduction, Preconditioned GMRES method for a class of Toeplitz linear systems in fractional eigenvalue problems, Matrix Structures in Queuing Models, Fast numerical solution of Fredholm integral equations with stationary kernels, Structured invariant spaces of vector valued rational functions, Hermitian matrices, and a generalization of the Iohvidov laws, Parallel and superfast algorithms for Hankel systems of equations, Remarks on a displacement-rank inversion method for Toeplitz systems, On the parallel arithmetic complexity of the root-finding problem, Derivation and Analysis of Fast Bilinear Algorithms for Convolution, Nearly optimal solution of rational linear systems of equations with symbolic lifting and numerical initialization, A class of iteration methods based on the HSS for Toeplitz systems of weakly nonlinear equations, Superfast algorithms for Cauchy-like matrix computations and extensions, Fast inversion of Hankel and Toeplitz matrices, DCT- and DST-based splitting methods for Toeplitz systems, On the stability of solution methods for band Toeplitz systems, Parallel solution of Toeplitzlike linear systems, Degeneration of structured integer matrices modulo an integer, Schur complements of Bézoutians and the inversion of block Hankel and block Toeplitz matrices, Recursive algorithms for unbalanced banded Toeplitz systems, Solving structured linear systems with large displacement rank, Asymptotics for Szegö polynomial zeros, Parametrization of Newton's iteration for computations with structured matrices and applications, A fast, preconditioned conjugate gradient Toeplitz solver, Iterative Toeplitz solvers with local quadratic convergence, Inversion components of block Hankel-like matrices, On a new class of reproducing kernel spaces and a new generalization of the Iohvidov laws, Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, Randomized preprocessing of homogeneous linear systems of equations, Estimation of covariance parameters in Kriging via restricted maximum likelihood, Chebyshev-Hankel matrices and the splitting approach for centrosymmetric Toeplitz-plus-Hankel matrices, Efficient parallel factorization and solution of structured and unstructured linear systems, An efficient solution for Cauchy-like systems of linear equations, Parallel output-sensitive algorithms for combinatorial and linear algebra problems, A modified T. Chan's preconditioner for Toeplitz systems, Approximate inverse-free preconditioners for Toeplitz matrices, Modification of Rissanen's method in linear memory, On Computations with Dense Structured Matrices, A new approach to fast polynomial interpolation and multipoint evaluation, Formally biorthogonal polynomials and a look-ahead Levinson algorithm for general Toeplitz systems, Stable row recurrences for the Padé table and generically superfast lookahead solvers for non-Hermitian Toeplitz systems, Power series remainder sequences and Padé fractions over an integral domain, Estimating the extremal eigenvalues of a symmetric matrix, Structure and arithmetic complexity of products and inverses of Toeplitz matrices, On the fast solution of a linear system arising in numerical conformal mapping, A fast but unstable orthogonal triangularization technique for Toeplitz matrices, Fast and efficient parallel evaluation of the zeros of a polynomial having only real zeros, Numerical experience with a superfast real Toeplitz solver, Rational interpolation via orthogonal plynomials, Anti-Hadamard matrices, Symmetry stabilization for fast discrete monomial transforms and polynomial evaluation, Applications of Szegö polynomials to digital signal processing, Robust Schur complement preconditioner for block-Toeplitz system and its application in image restoration, PARALLEL ALGORITHMS TO COMPUTE THE EIGENVALUES AND EIGENVECTORS OFSYMMETRIC TOEPLITZ MATRICES∗, A decomposition of Toeplitz matrices and optimal circulant preconditioning

Cites Work