Fast and stable solution of banded-plus-semiseparable linear systems

DOI10.1007/S100920200009MaRDI QIDQ2569768zbMATH OpenOpenAlexFDO

Authors Dario Fasino, L. Gemignani

Publication date 26 April 2006

Published in Calcolo (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s100920200009

zbMATH Keywords

algorithmbanded-plus-semiseparable matrixGaussian eliminationlinear complexitynumerical examplespartial pivotingtriangular factorization

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50) Complexity and performance of numerical algorithms (65Y20)

Review text

The authors propose a new stable algorithm for solving systems of linear equations \({(A+B)x = y}\) with a nonsingular semiseparable \((n \times n)\) matrix \(A\) and a banded matrix \(B\). It is supposed that \(\max\{p,q\} \ll n\), where \(p\) is the lower bandwidth and \(q\) the upper bandwidth. At first, a stable numerical algorithm for computing a triangular factorization of a nonsingular semiseparable matrix \(A\) is developed. The algorithm is based on the Gaussian elimination with partial pivoting and makes use of the structural properties of the inverse matrix \(A^{-1}\). The algorithm requires \(O(n)\) arithmetical operations. Based on this algorithm and the representation \(A+B = A(I + A^{-1}B)\) a procedure for solving systems of equations with a banded-plus-semiseparable matrix is derived. This algorithm has also linear complexity. Finally, the numerical behaviour of the algorithm is illustrated by numerical examples.

Recommendations

• Fast and Stable Algorithms for Banded Plus Semiseparable Systems of Linear Equations
• Matrix computations and semiseparable matrices. Vol. 1: Linear systems.
• O(n) algorithms for banded plus semiseparable matrices
• scientific article; zbMATH DE number 1955860
• scientific article; zbMATH DE number 2098303

Cited in

(10)

• Linear complexity algorithms for semiseparable matrices
• A hybrid triangulation method for banded linear systems
• A Levinson-like algorithm for symmetric strongly nonsingular higher order semiseparable plus band matrices
• O(n) algorithms for banded plus semiseparable matrices
• scientific article; zbMATH DE number 1955860 (Why is no real title available?)
• Fast and Stable Algorithms for Banded Plus Semiseparable Systems of Linear Equations
• scientific article; zbMATH DE number 2098303 (Why is no real title available?)
• scientific article; zbMATH DE number 908202 (Why is no real title available?)
• Asymptotically fast solution of two-level banded Toeplitz systems of linear equations
• On solving sparse band systems with three algorithms of the ABS family

Describes a project that uses

Uses Software

• mctoolbox

This page was built for publication: Fast and stable solution of banded-plus-semiseparable linear systems

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