FAST PARALLEL BAND MATRIX ARITHMETIC
Date
1990-08-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We present parallel algorithms for computation of the determinant,
adjoint, characteristic polynomial and rank of band matrices, and
for the solution of systems of linear equations with band matrices as
coefficient matrices. The algorithms can be implemented using
arithmetic-boolean circuits of polynomial size and depth O(log n logm),
or depth O(log n log m + log n log log n) for computations over small finite fields,
where n is the order and m the band width of the matrix given as
input. They can be implemented for computations over number fields and
finite fields using log space uniform boolean circuits of depth O(log
n log m + log n log log n) and polynomial
size, for input size n and band width m.
Description
Keywords
Computer Science