On efficient band matrix arithmetic

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^ω-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^ω) processors. If asymptotically efficient matrix multiplication is used (ω<3), then the time-processor product for the resulting algorithm is less than the number of steps used to solve these problems via Gaussian elimination. The algorithm is more general than previous processor efficient parallel algorithms for band matrix computations, since it can be applied to invert arbitrary nonsingular band matrices over arbitrary fields