# Smallest circuit for square of sparse symmetric matrix

I have an $$n \times n$$ symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are $$\sqrt{n}$$ nonzero entries in each row/column, so the input will be sparse by the output will be nearly a density of $$1$$. A normal sparse multiplication algorithm would take $$O (n^2)$$ time which is clearly optimal, but the circuit depth for any sparse representation I can think of is at least $$O (n^3)$$. (The act of "accessing a given location in memory" is not efficient in circuits.)

Using a fast matrix multiplication method like Coppersmith-Winograd (C-W) would bring me to $$O \left( n^{\sim 2.4} \right)$$. I know I can use the symmetry to reduce by a constant factor, but I figure not more than that. I'm hoping that the fact that it's squaring (and not multiplying two different matrices) can reduce the exponent, but I don't know how — I know that it can cut my work down a bit because the first iteration of C-W will have some identical results. I can't find any way to use the sparsity at all.

Numerical precision isn't an issue for me; the input is a 0-1 matrix.

In terms of practical purposes, I particularly care about $$n \sim 3000$$, but am generally curious about asymptotically good answers too. (Just saying this to explain that very huge constant factors are a big negative for me.) Any references very much appreciated!

• Matrix squaring has exactly the same exponent as matrix multiplication. Jan 7, 2019 at 7:35
• @YuvalFilmus Okay right, that makes sense, I see the reduction. Still, I do care about constant factors to some degree, so if there's a way for me to shave a factor of two off, that would mean a great deal to me. Jan 8, 2019 at 2:03

If it's really depth that you care about, I think you should be able to do it with a circuit of depth $$O(\log^2 n)$$ using sorting networks. I'll assume we want to compute the product $$AB$$, and that $$A$$ is represented as an array of rows, where each row is a sorted list of non-zero entries; and $$B$$ is an array of columns, where each column is a sorted list of non-zero entries. Then the $$ik$$ cell of the product $$AB$$ (namely, $$(AB)_{ik}$$) can be computed as follows: copy the entire row $$A_{i\cdot}$$; copy the entire column $$B_{\cdot k}$$; concatenate these two lists; sort them based on their indices, using a sorting network, to bring together entries with a common index; at each position where both matrices have an entry, multiply those entries; and sum up those products. You can build a sorting network with depth $$O(\log^2 n)$$, and the multiply-and-sum step can be done with depth $$O(\log n)$$ using an addition tree.