Parallel solution of Toeplitzlike linear systems
type: Item
instance of: scholarly article
title: Parallel solution of Toeplitzlike linear systems
zbMATH Open document ID: 0753.65022
DOI: 10.1016/0885-064X(92)90031-6
published in: Journal of Complexity
publication date: 1992-09-26T00:00:00Z
review text: This paper presents a weakly numerically stable parallel algorithm for the numerical solution of well-conditioned Toeplitz linear systems that supports the desired parallel polylogarithmic time bound and preserves a near optimum total work bound. It is shown how to compute the inversion of Toeplitz like matrices for any well-conditioned matrix. A modification of Newton's iteration is used to preserve the Toeplitz like structure of the auxiliary matrices. An estimation of the computational cost for the solution of such a Toeplitz like linear system is presented.
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65Y05
zbMATH DE Number: 55602
zbMATH Keywords: matrix inversion
zbMATH Keywords: parallel algorithm
zbMATH Keywords: well-conditioned Toeplitz linear systems
zbMATH Keywords: polylogarithmic time bound
zbMATH Keywords: Toeplitz like matrices
zbMATH Keywords: Newton's iteration
author: Victor Y. Pan
reviewed by: Dimitris Voukalis
MaRDI profile type: Publication
cites work: On the computational power of pushdown automata
cites work: Superfast Solution of Real Positive Definite Toeplitz Systems
cites work: Q3138975
cites work: Asymptotically fast solution of Toeplitz and related systems of linear equations
cites work: Fast parallel matrix and GCD computations
cites work: The Parallel Evaluation of General Arithmetic Expressions
cites work: Fast solution of toeplitz systems of equations and computation of Padé approximants
cites work: Stability of Methods for Solving Toeplitz Systems of Equations
cites work: The weak and strong stability of algorithms in numerical linear algebra
cites work: Divide-and-Conquer Solutions of Least-Squares Problems for Matrices with Displacement Structure
cites work: Fast Parallel Algorithms for QR and Triangular Factorization
cites work: Fast Parallel Matrix Inversion Algorithms
cites work: A new algorithm for solving Toeplitz systems of equations
cites work: Efficient solution of linear systems of equations with recursive structure
cites work: Q3359644
cites work: Q3787908
cites work: Q4733961
cites work: Displacement ranks of matrices and linear equations
cites work: Inverses of Toeplitz Operators, Innovations, and Orthogonal Polynomials
cites work: Q4385522
cites work: Complexity of parallel matrix computations
cites work: On Computations with Dense Structured Matrices
cites work: A new look at the Lanczos algorithm for solving symmetric systems of linear equations
cites work: An Adaptation of the Fast Fourier Transform for Parallel Processing
cites work: Q3773322
cites work: Q5674306
full work available at URL: 0885-064x(92)90031-6
OpenAlex ID: W2035714636
description: scientific article; zbMATH DE number 55602