A parallel algorithm for solving Toeplitz linear systems

DOI10.1016/S0096-3003(98)00028-9MaRDI QIDQ1294265zbMATH OpenOpenAlexFDO

Authors K. Appert, L. E. Garey, Ruth E. Shaw

Publication date 1 February 2000

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0096-3003(98)00028-9

zbMATH Keywords

algorithmcyclic reductionparallel computationToeplitz linear systemsToeplitz matrix

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Parallel numerical computation (65Y05)

Review text

For solving Toeplitz linear systems it is considered a cyclic reduction of the system by solving a system which contains the Toeplitz tridiagonal part and then correcting by accounting for the remaining elements in the coefficient matrix. The total number of operations for the sequential solution is given by \(6n+5\log_2n+4t\), where \(t\) is the number of components that needed to be corrected.

Recommendations

• Parallel Processing and Applied Mathematics
• scientific article; zbMATH DE number 17430
• scientific article; zbMATH DE number 4039117
• Parallel Solution of Certain Toeplitz Linear Systems

Cites work

• A fast algorithm for solving special tridiagonal systems
• A fast method for solving second Order boundary value volterra Integro-differential equations
• A new method for solving symmetric circulant tridiagonal systems of linear equations
• An approximate solution for a system with a symmetric matrix
• Efficient algorithms for solving nonlinear Volterra integro-differential equations with two point boundary conditions
• scientific article; zbMATH DE number 52113 (Why is no real title available?)

Cited in

(26)

• Parallel solution of symmetric positive definite systems with hyperbolic rotations
• Highly concurrent algorithm for the solution of \(\rho\)-Toeplitz system of equations
• Efficient solution of block linear systems with Toeplitz entries using a channel decomposition technique
• A direct method for solving circulant tridiagonal block systems of linear equations
• A parallel numerical algorithm for near symmetric and banded systems
• An efficient algorithm for a model with a bidiagonal coefficient matrix
• Parallel algorithms for solving tridiagonal and near-circulant systems.
• A communication-less parallel algorithm for tridiagonal Toeplitz systems
• scientific article; zbMATH DE number 4215256 (Why is no real title available?)
• scientific article; zbMATH DE number 4151711 (Why is no real title available?)
• scientific article; zbMATH DE number 5762985 (Why is no real title available?)
• scientific article; zbMATH DE number 4039117 (Why is no real title available?)
• scientific article; zbMATH DE number 17430 (Why is no real title available?)
• scientific article; zbMATH DE number 17447 (Why is no real title available?)
• scientific article; zbMATH DE number 529791 (Why is no real title available?)
• A structure-preserving algorithm for linear systems with circulant pentadiagonal coefficient matrices
• Computational Science – ICCS 2005
• Error analysis of an APA algorithm for the parallel solution of some special Toeplitz linear systems
• Parallel Processing and Applied Mathematics
• The parallel multisplitting TOR (MTOR) method for linear systems
• A parallel method for linear equations with tridiagonal Toeplitz coefficient matrices
• Numerical solution of block circulant tridiagonal linear systems originating from convolution equations
• A parallel algorithm solving a tridiagonal Toeplitz linear system
• A parallel iterative method for solving periodical block-tridiagonal linear equations
• A multilevel parallel algorithm to solve symmetric Toeplitz linear systems
• A fast algorithm for solving diagonally dominant symmetric pentadiagonal Toeplitz systems

This page was built for publication: A parallel algorithm for solving Toeplitz linear systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1294265)