A note on the solution of not balanced banded Toeplitz systems

A direct algorithm for the solution of linear systems having block band Toeplitz matrix in block Hessenberg form is presented. Under reasonable assumption on the bandwidth, the algorithm always equals and some- times outperforms the already known direct ones in terms of computa- tional cost. It is derived from the block odd-even algorithm, it makes use of techniques based on the block displacement rank and it relies on the Morrison-Sherman-Woodbury formula. The case where the coefficient matrix is in addition a scalar band Toeplitz matrix is analyzed as well, showing the effectiveness of the new algorithm. The algorithm is numeri- cally stable if applied to scalar band Toeplitz M -matrices which are point diagonally dominant by columns.