On efficient band matrix arithmetic
Wayne Eberly · 1992
An efficient parallel Las Vegas algorithm is presented for computation of the determinant of a non-singular band matrix and for the solution of a system of linear equations with a band matrix as coefficient matrix. The algorithm can be implemented using time polylogarithmic in n with O(nm/sup omega -1/) processors, in order to process an input matrix with order n and band width m, provided that n*n matrices can be multiplied in logarithmic time with O(n/sup omega /) processors. If asymptotically efficient matrix multiplication is used ( omega>