Theoretical Computer Science

Survey on algorithms/complexity of linear algebra


I am looking for a good survey on algorithms and complexity of linear algebra (operations like rank, inverse, eigenvalues, ... for Boolean, $\mathbb{F}_p$, and integers/rationals matrices) with emphasis on parallel ($NC$ hierarchy) and polytime algorithms. I could not find a recent one.

Do you know a good recent survey or book on complexity of linear algebra?




Solution

Two references you might find to be helpful:

D. Bini and V. Pan. Polynomial and matrix computations, Volume 1: Fundamental Algorithms. Progress in Theoretical Computer Science, Birkhauser, 1994.

J. von zur Gathen. Parallel linear algebra. In J. Reif, editor, Synthesis of Parallel Algorithms, chapter 13. Morgan Kaufmann Publishers, Inc., 1993.

They aren't necessarily recent, but they're a good starting point.