<p>How about <a href="http://rads.stackoverflow.com/amzn/click/1601982429">Complexity Lower Bounds using Linear Algebra</a>? The book is not exactly what you want, since it surveys lower bounds <strong>using</strong> linear algebra, not the complexity <strong>of</strong> linear algebra problems. Yet I think it is helpful anyway, since it is first necessary to grasp the complexity of linear algebra problems, and then use it to prove lower bounds on other problems.</p>

<p>Here's the description of the book:</p>

<blockquote>
  <p>While rapid progress has been made on upper bounds (algorithms), progress on lower bounds on the complexity of explicit problems has remained slow despite intense efforts over several decades. As is natural with typical impossibility results, lower bound questions are hard mathematical problems and hence are unlikely to be resolved by ad hoc attacks. Instead, techniques based on mathematical notions that capture computational complexity are necessary. Complexity Lower Bounds using Linear Algebra <strong>surveys</strong> several techniques for proving lower bounds in Boolean, algebraic, and communication complexity based on certain linear algebraic approaches. The common theme among these approaches is to study <strong>robustness measures of matrix rank</strong> that capture the complexity in a given model. Suitably strong lower bounds on such robustness functions of explicit matrices lead to important consequences in the corresponding circuit or communication models. Understanding the inherent computational complexity of problems is of fundamental importance in mathematics and theoretical computer science. Complexity Lower Bounds using Linear Algebra is an invaluable reference for anyone working in the field.</p>
</blockquote>

<p><strong>PS:</strong> You asked for a book, but I believe this article: <a href="http://dx.doi.org/10.1006/jcss.1998.1608">The Computational Complexity of Some Problems of Linear Algebra</a> is also useful (yet it dates back to 1999).</p>

CC BY-SA 2.5
2010-11-04T09:35:25.760Z
Thanks Sadeq. Actually I have asked for a *survey or book*. I will take a look at the article although it does not seem to be what I am looking for.
Kaveh
CC BY-SA 2.5
2010-11-04T09:46:55.300Z
Btw, I have Lokam's book and it is a really nice one.
Kaveh
CC BY-SA 2.5
2010-11-04T09:24:36.540Z
2010-11-04T09:24:36.540Z
Sadeq Dousti
<p>This book does not explicitly mention parallel algorithms, but <a href="http://cs.nyu.edu/cs/faculty/yap/">Yap's</a> book <a href="http://cs.nyu.edu/~yap/book/alge/ftpSite/">"Fundamental Problems of Algorithmic Algebra"</a> is a very good reference and discusses the complexity of many Linear Algebra questions.  There is a chapter specifically on <a href="http://cs.nyu.edu/~yap/book/alge/ftpSite/l10.ps.gz">Linear Systems</a> discussing the time/bit complexity of determinant calculation, matrix inversion, Hermite normal form algorithms, amongst others.</p>

<p>The book also deals with complexity of multiplication, Grobner bases and Lattice Reduction techniques (such as LLL).  I can't recommend it enough and I bet you'll find something of worth therein.</p>

CC BY-SA 2.5
2010-11-05T03:36:54.170Z
2010-11-05T03:36:54.170Z
user834
<p>Two references you might find to be helpful:</p>

<blockquote>
  <p>D. Bini and V. Pan.  Polynomial and matrix computations, Volume 1: Fundamental Algorithms.  Progress in Theoretical Computer Science, Birkhauser, 1994.</p>
  
  <p>J. von zur Gathen. Parallel linear algebra. In J. Reif, editor, Synthesis of Parallel Algorithms, chapter 13. Morgan Kaufmann Publishers, Inc., 1993.</p>
</blockquote>

<p>They aren't necessarily recent, but they're a good starting point.</p>

CC BY-SA 2.5
2010-11-04T13:19:32.927Z
2010-11-04T13:19:32.927Z
John Watrous
<p>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.</p>

<p>Do you know a good recent survey or book on complexity of linear algebra? </p>

<cc.complexity-theory><ds.algorithms><reference-request><dc.parallel-comp><linear-algebra>
Survey on algorithms/complexity of linear algebra
Kaveh
# Survey on algorithms/complexity of linear algebra

(Asked by: username_0 on 2010-11-04)

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?

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, dc.parallel-comp, linear-algebra


---

## 3 answers

### Answer by username_3 on 2010-11-04. Score: 17 | Accepted answer

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.


---

### Answer by username_1 on 2010-11-04. Score: 9

How about [Complexity Lower Bounds using Linear Algebra](http://rads.stackoverflow.com/amzn/click/1601982429)? The book is not exactly what you want, since it surveys lower bounds **using** linear algebra, not the complexity **of** linear algebra problems. Yet I think it is helpful anyway, since it is first necessary to grasp the complexity of linear algebra problems, and then use it to prove lower bounds on other problems.

Here's the description of the book:

> While rapid progress has been made on upper bounds (algorithms), progress on lower bounds on the complexity of explicit problems has remained slow despite intense efforts over several decades. As is natural with typical impossibility results, lower bound questions are hard mathematical problems and hence are unlikely to be resolved by ad hoc attacks. Instead, techniques based on mathematical notions that capture computational complexity are necessary. Complexity Lower Bounds using Linear Algebra **surveys** several techniques for proving lower bounds in Boolean, algebraic, and communication complexity based on certain linear algebraic approaches. The common theme among these approaches is to study **robustness measures of matrix rank** that capture the complexity in a given model. Suitably strong lower bounds on such robustness functions of explicit matrices lead to important consequences in the corresponding circuit or communication models. Understanding the inherent computational complexity of problems is of fundamental importance in mathematics and theoretical computer science. Complexity Lower Bounds using Linear Algebra is an invaluable reference for anyone working in the field.

**PS:** You asked for a book, but I believe this article: [The Computational Complexity of Some Problems of Linear Algebra](http://dx.doi.org/10.1006/jcss.1998.1608) is also useful (yet it dates back to 1999).

> **Comments:**
> **username_0**: Thanks Sadeq. Actually I have asked for a *survey or book*. I will take a look at the article although it does not seem to be what I am looking for.  
> **username_0**: Btw, I have Lokam's book and it is a really nice one.  

---

### Answer by username_2 on 2010-11-05. Score: 7

This book does not explicitly mention parallel algorithms, but [Yap's](http://cs.nyu.edu/cs/faculty/yap/) book ["Fundamental Problems of Algorithmic Algebra"](http://cs.nyu.edu/~yap/book/alge/ftpSite/) is a very good reference and discusses the complexity of many Linear Algebra questions. There is a chapter specifically on [Linear Systems](http://cs.nyu.edu/~yap/book/alge/ftpSite/l10.ps.gz) discussing the time/bit complexity of determinant calculation, matrix inversion, Hermite normal form algorithms, amongst others.

The book also deals with complexity of multiplication, Grobner bases and Lattice Reduction techniques (such as LLL). I can't recommend it enough and I bet you'll find something of worth therein.


---

