Fast solver for Toeplitz bidiagonal systems of linear equations

Abstract

We present a new efficient parallel algorithm for solving the first order linear recurrence systems with constant coefficients which is equivalent to the problem of solving Toeplitz bidiagonal systems of linear equations. The algorithm is formulated in the terms of level 1 and 2 BLAS (Basic Linear Algebra Subprograms) routines AXPY and GER. We also discuss its platform-independent implementation with OpenMP and finally present the results of experiments performed on a dual processor Pentium III computer running under Linux operating system with Altas as an efficient implementation of BLAS. The sequential version of the algorithm is up to 2.5 times faster than a simple sequential algorithm.