1
$\begingroup$

Integer matrix multiplication with its transpose (A^T)A gives symmetric matrix, so, only one half of it should be computed. Besides, the formula for the resulting element rik=Sum[aijajk, j] reduces to the simple sum of the multiplication of the the corresponding elements from two columns rik=Sum[ajiajk, j]. As I understand, the last observation is not giving any efficiency, the formulas are just bit more nice, nothing else. So, there are n(n-1)/2 multiplications and nn(n-1)/2 sum operations. Parallelization can improve the speed by simple division of labour, but my thinking is that there is not any sophistication available to improve the speed of this algorithm beyond the naive algorithm. Or maybe there is still any better, more sophisticated algorithm?

I am aware of https://math.stackexchange.com/questions/158219/is-a-matrix-multiplied-with-its-transpose-something-special but that is not discussion about algorithms.

There is also https://en.wikipedia.org/wiki/Strassen_algorithm - so maybe the sophistication I am seeking amounts to the application of the Strassen algorithm for the one half of the resulting matrices only? I am using symmetricity in that case. But can I take advantage of the fact that A enters in both sides of the multiplication?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.