Wrap-around partitioning for block bidiagonal linear systems

DOI10.1093/IMANUM/18.3.373MaRDI QIDQ3840701zbMATH OpenOpenAlexFDO

Authors Markus Hegland, Michael R. Osborne

Publication date 18 February 1999

Published in IMA Journal of Numerical Analysis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/imanum/18.3.373

zbMATH Keywords

block bidiagonal linear systemsQR factorizationvector algorithmwrap-around partitioning

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10)

Review text

A stable vector algorithm for the solution of the block bidiagonal linear systems is obtained combining a wrap-around partitioning (reordering of the unknowns in a system of linear equations) and the QR factorization. A step of the wrap-around partitioning transforms a linear system into a system of the \(q\) (super)blocks of \(p\) (submatrix) elements each. Then the orthogonal transformations is considered for elimination of the \(q-1\) subdiagonal \(p\times p\) block matrices. Each subdiagonal block row in the current pivotal block column can be eliminated independently of the other block rows. This observation provides the basis for vectorizing the computation. The final block is again block bidiagonal in the structure and so it is possible to use the recursive implementation of the wrap-around partitioning. Organization of the wrap-around partitioning and elimination of the subdiagonal blocks are discussed. A determination of the optimum transformation parameters \(p\) and \(q\) is considered. Certain implementation details are discussed and some conclusions are drawn. Using a simple model for the vectorization overhead it is shown that small block sizes give the best performance.

Recommendations

• scientific article; zbMATH DE number 1217603
• Solving 3D block bidiagonal linear systems on vector computers
• On the parallel solution of tridiagonal systems by wrap-around partitioning and incomplete LU factorization
• A parallel partition method for solving banded systems of linear equations

Cited in

(5)

• Overlapping vs partitioning in block-iteration methods: Application in large-scale system theory
• Solving 3D block bidiagonal linear systems on vector computers
• On solution of large systems of linear equations with block-Toeplitz banded matrices
• Almost block diagonal linear systems: sequential and parallel solution techniques, and applications
• Iterative algorithms for nonlinear ordinary differential eigenvalue problems

This page was built for publication: Wrap-around partitioning for block bidiagonal linear systems

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