ON PARALLEL COMPUTATIONS WITH BANDED MATRICES

We devise parallel algorithms for solving a banded linear system of eq uations and for computing the determinant of a banded matrix, substant ially improving the previous record computational complexity estimates of [E]. Our algorithms are in NC or RNC and support new record bounds on the parallel time complexity of these computations and simultaneou sly the bounds on their potential work (the product of time and proces sor bounds), which match (within constant or logarithmic factors) the record sequential time bounds for the same computations. Moreover, the se algorithms are in NC1 or RNC(1) if the bandwidth is a constant. (C) 1995 Academic Press, Inc.