A fast and reliable numerical solver for general bordered k-tridiagonal matrix linear equations

To improve on the shortcomings observed in symbolic algorithms introduced recently for related matrices, a reliable numerical solver is proposed for computing the solution of the matrix linear equation AX=B. The (n×n) matrix coefficient A is a nonsingular bordered k-tridiagonal matrix. The particular structure of A is exploited through an incomplete or full Givens reduction, depending on the singularity of its associated k-tridiagonal matrix. Then adapted back substitution and Sherman-Morrison's formula can be applied. Specially the inverse of the matrix A is computed. Moreover for a wide range of matrices A, the solution of the vector linear equation Ax=b can be computed in O(n) time. Numerical comparisons illustrate the results.