Parallel solution of almost block diagonal systems on a hypercube
The authors are interested in solution of problems arising from finite difference discretization of systems of linear ordinary differential equations with separated boundary conditions. These problems have coefficient matrices which are almost of block diagonal form. They are interested in solution of these problems on hypercube computers which are characterized by relatively expensive interprocessor communication costs in a single-tasking environment. The authors present a two-stage approach to factorization of these linear matrices. The original matrix is divided among \(p\) processors with several blocks per processor. The first stage of the factorization involves, for each processor, an LU factorization of the portion of the matrix referring only to variables stored on the same processor. The method used for this stage is similar to the one introduced by \textit{M. Paprzycki} and \textit{I. Gladwell} [Parallel Comput. 17, No. 2/3, 133-153 (1991; Zbl 0729.65012)]. This stage involves roughly \(\log_2 p\) steps, each of which starts with a sharing of information with adjacent processors and performs a factorization of the same resulting matrix on pairs of processors. Duplication of the matrices results in additional arithmetic operations, but these operations are performed on processors which would otherwise be idle. This duplication reduces the amount of interprocess communication required in the solution. The authors provide precise descriptions of the algorithms used, arithmetical operation counts, and memory requirements. They compare these operation counts and memory requirements with the earlier algorithm and also with the best sequential algorithm.
- A parallel version of the cyclic reduction algorithm on a hypercube
- A set of level 3 basic linear algebra subprograms
- Alternate Row and Column Elimination for Solving Certain Linear Systems
- An extended set of FORTRAN basic linear algebra subprograms
- Basic Linear Algebra Subprograms for Fortran Usage
- FORTRAN Packages for Solving Certain Almost Block Diagonal Linear Systems by Modified Alternate Row and Column Elimination
- scientific article; zbMATH DE number 781814 (Why is no real title available?)
- On parallel methods for boundary value ODEs
- On some parallel banded system solvers
- Parallel Factorizations for Tridiagonal Matrices
- Parallel solution of almost block diagonal systems on the CRAY Y-MP using level 3 BLAS
- Parallel treatment of block-bidiagonal matrices in the solution of ordinary differential boundary value problems
- Solving almost block diagonal systems on parallel computers
- Solving banded systems on a parallel processor
- Solving narrow banded systems on ensemble architectures
- Stable Parallel Algorithms for Two-Point Boundary Value Problems
- Hypercube implementations of parallel shooting
- High-order transverse schemes for the numerical solution of PDEs
- Efficient parallel algorithm for quasi pentadiagonal systems on a hypercube
- A massively parallel algorithm for bordered almost block diagonal systems on GPUs
- Adaptation of a Two-Point Boundary Value Problem Solver to a Vector-Multiprocessor Environment
- Solution of Linear Systems of Ordinary Differential Equations on an INTEL Hypercube
- Almost block diagonal linear systems: sequential and parallel solution techniques, and applications
- scientific article; zbMATH DE number 935164 (Why is no real title available?)
- Solving almost block diagonal systems on parallel computers
This page was built for publication: Parallel solution of almost block diagonal systems on a hypercube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1923143)
