- cc.complexity-theory ds.algorithms reference-request dc.parallel-comp linear-algebra
- Updated Fri, 17 Jun 2022 02:08:54 GMT

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?

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.