Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 1 down vote accepted

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)$).

share|improve this answer
    
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}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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