1
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ Matrix squaring has exactly the same exponent as matrix multiplication. $\endgroup$ Jan 7, 2019 at 7:35
  • $\begingroup$ @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. $\endgroup$ Jan 8, 2019 at 2:03

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.