0
$\begingroup$

Consider $A\in\mathbb{R}^{n\times n}$ its not a special matrix and in the worst case all of its entries are non-zero. I am looking for a way to compute $AA^{T}$ using matrix-vector operation. The total number of flops are $(2n-1)\frac{n(n+1)}{2}$ because all I have to do for a symmetric matrix like $C=AA^{T}$ is to compute the diagonal entires which are $C(i,i)=A(i,:)^TA(i,:)$. What I want now is to compute the lower triangular part and then when I am done I just say that the upper triangular part is the same as the lower triangular part. The problem is can I do it in matrix-vector multiplication or will it force me to perform unnecessary multiplication (like multiplying elements in the upper part)? It is clear that a vector-vector computation would work but I am interested to know if a matrix-vector computation would work or not.

$\endgroup$
9
  • $\begingroup$ It's not clear to me .. do you need all of $\mathbf C = \mathbf A \mathbf A^T$, or just the diagonal entries? Do you need to tabulate $\mathbf C$, or just apply it's action to a vector? Your question is close but not quite there. $\endgroup$ Jul 7 at 15:03
  • $\begingroup$ I wish to compute $C=AA^{T}$ by just computing the lower triangular part of $C$ that is where I am stuck I can do that using scalar operation but I was wondering if its possible to do it as a matrix-vector operation @rchilton1980 $\endgroup$
    – TYWQ
    Jul 7 at 15:12
  • $\begingroup$ The diagonal entries and the upper triangular part will follow from the symmetry of $C$ @rchilton1980 $\endgroup$
    – TYWQ
    Jul 7 at 15:13
  • 2
    $\begingroup$ Which language are you using? I think that in Matlab and Python a call of the form A * A' (with the same variable on both sides) already gets translated to a ?SYRK BLAS call that does this under the hood. (More generally, if the question is "what is the fastest way to do this?", then I believe the answer will be "use ?SYRK". $\endgroup$ Jul 7 at 16:14
  • 3
    $\begingroup$ Can you do matrix-vector products only with $A$ or also with $A^T$? Or alternatively, can you do products with vectors from the left, i.e., $v^TA$? $\endgroup$ Jul 7 at 20:30

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.