# Matrix multiplication efficiency

I have a multiplication $A * B * A^T$, where $B$ is a covariance matrix (i.e. symmetric, square) and $A$ is an arbitrary matrix with compatible dimensions. Given the symmetry of $B$ and the fact that I multiply by $A$ and $A^T$, it really feels like there must be a more efficient way to compute the result than two multiplications, but I haven't been able to find anything. Does anyone have any insight on the problem, or why there isn't any better way of doing it?

Thanks!

-

Since $B$ is symmetric, $ABA^T$ is also symmetric, and so you only need to determine the entries above the diagonal. Thus, instead of doing two matrix multiplications, you can make do with one and a half.

However, without there being anything else special about $A$ or $B$, I am skeptical that any speedup you get will be more than a constant factor. In particular, it is very unlikely that computing $ABA^T$ can be done faster than computing $AB$. Algorithmically, this means that your won't change the order of magnitude of the run time of whatever you are using this for, and so unless you are doing a ton of matrix multiplications, looking for a clever optimization won't likely net you great gains.

However, on a related note, something that will speed up the multiplication, at least when you are dealing with large matrices, is Strassen's algorithm, which is an algorithm for multiplying $2\times 2$ matrices with 7 multiplications instead of 8, which can recursively be used to multiply large matrices together quickly ($O(n^{\log_2 7+o(1)})$ instead of $O(n^3)$).

-
Yeah, I didn't really expect asymptotic improvements to begin with. I'm mostly just trying to optimize a program where this matrix operation dominates the runtime and even halving its cost would be a big win. I'm not sure Strassen's algorithm is used too much in practice, is it, in the optimized matrix multiplication libraries? –  copumpkin May 20 '11 at 23:49
@pumpkin I don't know what the big libraries do. The problem with Strassen's algorithm is that you lose a good deal of efficiency when $n$ isn't a power of 2, and figuring out the best way to divide the matrix in this case can be nontrivial. For a similar problem, that of doing FFT, I once saw a program which takes in input n and spits out an algorithm for doing FFT with input of size n. I imagine Strassen's algorithm is not an improvement for matrices that have special forms, or which are sparse. However, for general matrices, it gives a real spead up for large n. –  Aaron May 21 '11 at 0:29
By a real speed up, I mean that not only does it have better growth, but it does so without a large constant in front. so the gains are actually realized. However, because $\log_2(7)$ is not that much smaller than 3, the gains are not very large enough until you get to large matrices. –  Aaron May 21 '11 at 0:33

If you're going to be using the same $A$ for many different $B$, it might pay to precompute the matrices $C_{ii} = A E_{ii} A^T$ and $C_{ij} = A (E_{ij} + E_{ji}) A^T$ for all $i \le j$, where $E_{ij}$ is the matrix with $(i,j)$ entry $1$ and all others $0$. Then $A B A^T = \sum_i \sum_{j \ge i} b_{ij} C_{ij}$.

-