A hybrid triangulation method for banded linear systems

We propose a fast solution method for banded linear systems that transforms the original system into an equivalent one with an almost block triangular coefficient matrix, and then constructs a preconditioner based on this formulation. We analyze the algorithmic complexity of the new method and the eigenvalue distribution of the resulting preconditioned matrix. Numerical examples involving block tridiagonal, block Hessenberg and block pentadiagonal systems are illustrated to demonstrate the computational performance and the efficiency of the new matrix solver.