A parallel balance scheme for banded linear systems

DOI10.1002/NLA.241MaRDI QIDQ4828881zbMATH OpenOpenAlexFDO

Authors Gene H. Golub, Ahmed H. Sameh, Vivek Sarin

Publication date 26 November 2004

Published in Numerical Linear Algebra with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/nla.241

zbMATH Keywords

algorithmcomparison of methodscondition numberiterative methodsKrylov subspace methodsparallel computationpreconditioningQR factorizationsparse linear systems

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35) Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05)

Review text

A new algorithm is proposed for the solution of a non-symmetric banded linear system that is sparse within the band. The system matrix is partitioned into blocks of rows in a such way that there is a small number of unknowns common to multiple blocks. The balance scheme algorithm consists of two main steps. In the first step, the underdetermined system is solved while in the second step the solution of a small reduced system is obtained. The reduced system with matrix \(M\) can be solved using either direct or iterative method. The upper bound of the condition number of \(M\) is derived and storage requirements are estimated. Another variant is proposed in which the matrix \(M\) is not expressed explicitly. The use of QR factorization to solve the underdetermined system is replaced by projection-based approach. The parallel implementation is examined and the results of experiments for narrow banded non-symmetric systems are presented. The experiments shows that the balance scheme is a competitive alternative to preconditioned Krylov subspace methods, especially for matrices with strongly indefinite symmetric part.

Recommendations

• A tearing-based hybrid parallel banded linear system solver
• Parallel algorithm with parameters based on alternating direction for solving banded linear systems
• scientific article; zbMATH DE number 1330400
• A parallel partition method for solving banded systems of linear equations
• scientific article; zbMATH DE number 822187

Cites work

• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Numerical methods for generalized least squares problems
• On some parallel banded system solvers
• Row Ordering for a Sparse QR Decomposition
• Row Projection Methods for Large Nonsymmetric Linear Systems
• ScaLAPACK Users' Guide

Cited in

(7)

• A tearing-based hybrid parallel banded linear system solver
• Parallel algorithm for solving linear systems arising from PDE and integral equations
• A hybrid triangulation method for banded linear systems
• Approximate Schur-block ILU preconditioners for regularized solution of discrete ill-posed problems
• Parallel finite element computations in fluid mechanics
• Parallel minimum norm solution of sparse block diagonal column overlapped underdetermined systems
• The Effect of Various Sparsity Structures on Parallelism and Algorithms to Reveal Those Structures

Describes a project that uses

Uses Software

• ScaLAPACK

This page was built for publication: A parallel balance scheme for banded linear systems

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