An overlapped two-way method for solving tridiagonal linear systems in a BSP computer
type: Item
instance of: scholarly article
title: An overlapped two-way method for solving tridiagonal linear systems in a BSP computer
zbMATH Open document ID: 1062.65030
author: Joan-Josep Climent
author: Carmen Perea
author: Leandro Tortosa
author: Antonio Zamora
published in: Applied Mathematics and Computation
publication date: 2005-02-22T00:00:00Z
review text: Given a tridiagonal linear system \(Ax = d\), where \(A\) is a diagonally dominant matrix, this paper considers parallel methods for computing \(x\). The first method decomposes \(A\) as follows: \[ A = \left[ \begin{matrix} L_{11} & 0 \\ L_{21} & U_{22} \end{matrix} \right] \left[\begin{matrix} D_{11} & 0 \\ 0 & D_{22} \end{matrix}\right] \left[\begin{matrix} U_{11} & U_{12} \\ 0 & L_{22} \end{matrix}\right], \] where \(L_{11},L_{22}\) are lower bidiagonal and \(U_{11}, U_{22}\) are upper bidiagonal matrices of roughly the same size with ones on the diagonals; \(D_{11}\) and \(D_{22}\) are diagonal; \(L_{21}\) and \(U_{12}\) are zero besides a non-zero entry in the top-right/bottom-left position. While \(L_{11}D_{11}U_{11}\) is computed from top-to-bottom, the decomposition \(U_{22}D_{22}U_{22}\) is computed from bottom-to-top. This admits the efficient parallel computation of the complete decomposition as well as the subsequent solution of the bidiagonal systems on two processors. For more processors, the authors propose an overlapping partitition of the matrix, very much in the spirit of Schwarz iterations. It is suggested to use the first method to solve each block diagonal subsystem of the partition on two processors. Numerical experiments demonstrate that the actual execution times of the described algorithms match the predicted times rather well. No comparison with one of the other existing parallel methods for solving a tridiagonal system is made.
reviewed by: Daniel Kressner
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65F50
Mathematics Subject Classification ID: 65Y05
Mathematics Subject Classification ID: 65Y10
zbMATH DE Number: 2136199
zbMATH Keywords: tridiagonal linear system
zbMATH Keywords: diagonally dominant matrix
zbMATH Keywords: Bulk synchronous parallelism
zbMATH Keywords: Schwarz iteration
zbMATH Keywords: parallel computation
zbMATH Keywords: overlapping partitions
zbMATH Keywords: two-way methods
zbMATH Keywords: numerical experiments
describes a project that uses: BSPlib
MaRDI profile type: Publication
full work available at URL: j.amc.2003.12.044
OpenAlex ID: W2084334648
cites work: Divide and conquer: A parallel algorithm for the solution of a tridiagonal linear system of equations
cites work: A Tricyclic Tridiagonal Equation Solver
cites work: BSP linear solvers for dense matrices
cites work: A Fast Direct Solution of Poisson's Equation Using Fourier Analysis
cites work: Review of general and Toeplitz vector bidiagonal solvers
cites work: Compact finite difference schemes with spectral-like resolution
cites work: Computer science today. Recent trends and developments
cites work: The parallel recursive decoupling algorithm for solving tridiagonal linear systems
cites work: An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations
cites work: Analysis of a parallel solution method for tridiagonal linear systems
cites work: A Parallel Method for Tridiagonal Equations
DOI: 10.1016/J.AMC.2003.12.044
description: scientific article; zbMATH DE number 2136199