Optimum Parallel Computations with Band Matrices

TitleOptimum Parallel Computations with Band Matrices
Publication TypeTechnical Report
Year of Publication1993
AuthorsPan, V.
Other Numbers849

We devise optimum parallel algorithms for solving a band linear system of equations and for computing the determinant of a band matrix, substantially improving the previous record computational complexity estimates of [E]. All our algorithms are in NC or RNC and processor efficient; almost all of them reach the optimum bound on the potential work (the product of time and processor bounds). Moreover, these algorithms are in NC^1 or RNC^1 if the bandwidth is a constant.

Bibliographic Notes

ICSI Technical Report TR-93-061

Abbreviated Authors

V. Pan

ICSI Publication Type

Technical Report