An overlapped two-way method for solving tridiagonal linear systems in a BSP computer
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.
- scientific article; zbMATH DE number 2051109
- A BSP recursive divide and conquer algorithm to solve a tridiagonal linear system
- Overlapping block methods for solving tridiagonal systems on transputer arrays
- Parallelization and vectorization aspects of the solution of tridiagonal linear systems
- On the parallel solution of tridiagonal systems by wrap-around partitioning and incomplete LU factorization
- A Fast Direct Solution of Poisson's Equation Using Fourier Analysis
- A Parallel Method for Tridiagonal Equations
- A Tricyclic Tridiagonal Equation Solver
- An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations
- Analysis of a parallel solution method for tridiagonal linear systems
- BSP linear solvers for dense matrices
- Compact finite difference schemes with spectral-like resolution
- Computer science today. Recent trends and developments
- Divide and conquer: A parallel algorithm for the solution of a tridiagonal linear system of equations
- Review of general and Toeplitz vector bidiagonal solvers
- The parallel recursive decoupling algorithm for solving tridiagonal linear systems
- Overlapping block methods for solving tridiagonal systems on transputer arrays
- scientific article; zbMATH DE number 2051109 (Why is no real title available?)
- scientific article; zbMATH DE number 1894937 (Why is no real title available?)
- A BSP recursive divide and conquer algorithm to solve a tridiagonal linear system
This page was built for publication: An overlapped two-way method for solving tridiagonal linear systems in a BSP computer
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1763313)
