<p>While I don't know about the complexity of matrix polynomials in general, the state of the art in the complexity of matrix multiplication is nicely summarized in a <a href="http://theoryofcomputing.org/articles/gs005/" rel="nofollow">recent ToC Graduate Survey by Markus Bläser</a>.</p>

<p>Computing entries mod $p$ is basically the same as the question of the complexity of performing the computation over the field $\mathbb{F}_p$, which is fairly well-studied (though perhaps not as well-studied as characteristic zero). </p>

<p>Most matrix multiplication research works in the nonuniform setting anyways, so it should almost all be relevant to the question of circuit size.</p>

CC BY-SA 3.0
2014-12-13T04:46:54.443Z
2014-12-13T04:46:54.443Z
Joshua Grochow
<p>So I'm wondering, first off, where I can read up to get a feel for state-of-the-art matrix multiplication concepts.  I'll try to be more specific:</p>

<p>I'm wondering if there has been research on circuits that compute a pre-defined matrix function.  For instance, if we have a function such as $(AB)+C+(DEF)(AB)$, where all the variables are matrices with given sizes, how efficient can we make a circuit that computes this function?  I've been toying with an idea in which the entries are all computed modulo $p$.  So I'm wondering, broadly, what I can read up on to be up-to-date.</p>

<matrices>
What is known about matrix multiplication, and matrix circuits?
Matt Groff
# What is known about matrix multiplication, and matrix circuits?

(Asked by: username_0 on 2014-12-12)

So I'm wondering, first off, where I can read up to get a feel for state-of-the-art matrix multiplication concepts. I'll try to be more specific:

I'm wondering if there has been research on circuits that compute a pre-defined matrix function. For instance, if we have a function such as $(AB)+C+(DEF)(AB)$, where all the variables are matrices with given sizes, how efficient can we make a circuit that computes this function? I've been toying with an idea in which the entries are all computed modulo $p$. So I'm wondering, broadly, what I can read up on to be up-to-date.

**Tags:** matrices


---

## 1 answers

### Answer by username_1 on 2014-12-13. Score: 3

While I don't know about the complexity of matrix polynomials in general, the state of the art in the complexity of matrix multiplication is nicely summarized in a [recent ToC Graduate Survey by Markus Bläser](http://theoryofcomputing.org/articles/gs005/).

Computing entries mod $p$ is basically the same as the question of the complexity of performing the computation over the field $\mathbb{F}\_p$, which is fairly well-studied (though perhaps not as well-studied as characteristic zero).

Most matrix multiplication research works in the nonuniform setting anyways, so it should almost all be relevant to the question of circuit size.


---

