0
$\begingroup$

I need to implement an algorithm that calculates the symmetric matrix obtained by performing $A A^t$ being $A^t$ the transpose of $A$.

I did my analysis from two perspectives:

  1. The first thing I notice is that it is not necessary to have more memory to have $A^t$ because it is the same as $A$, what changes is the "rotation". Therefore I not need store $A^t$ whether it can be "creative" and "intelligent" to iterate over the row / column properly in $A$.

  2. The 2nd, what is known is that the symmetric matrices have the particularity that the elements of the upper and lower triangular (discounting the diagonal) are equal. Then, simply calculate the upper triangular and then "copy" the value of the position "transposed" in the lower triangular.

From what little I remember of the theory of computational complexity, traditional matrix multiplication $A B = (m\times n)\times (n\times p) = (m\times p)$, has complexity $O(mpn)$. If $A$ and $B$ are square everything is reduced to $O(m^3)$.

For my scenario where $A$ is $m\times n$ and recognizing that the symmetric matrix $S = A A^t$ is square, the expression reduces to $O(m^2n)$, but I can also be symmetrical save half the calculations: $O ((m^2n)/2)$. Until there more or less I think I'm doing OK.

The point is that I implemented two algorithms and can not remember as we proceed to analyze T() and thus see what could be more optimal. Hoping that one could guide me on how to estimate T():

Algorithm 1:

for i = 1..m do:
  for j = i..m do:
    if i = j
      then for k = 1..n do: 
             S(i,j) = S(i,j) + A(i,k) * A(i,k)
      else begin
             for k = 1..n do: 
               S(i,j) = S(i,j) + A(i,k) * A(j,k)
             S(j,i) = S(i,j)
           end

Algorithm 2:

for i = 1..m do:
begin
  for k = 1..n do:
    S(i,i) = S(i,i) + A(i,k) * A(i,k)
  for j = i+1..m do:
  begin
    for k = i..n do:
      S(i,j) = S(i,j) + A(i,k) * A(j,k)
    S(j,i) = S(i,j)
  end
end

Both by theory, do not exceed $O (m ^ 2n)$ obviously. When I try to analyze iteration cycles for the variable j, is where I get confused.

$\endgroup$
  • 1
    $\begingroup$ You can do theoretically better using fast matrix multiplication, and in fact, for the square case $n = m$, your problem is probably equivalent to matrix multiplication. But in practice, the blocked versions of your algorithms are probably the best. If you want to know which of them is better, implement them and do an experiment. $\endgroup$ – Yuval Filmus Apr 22 '15 at 20:04
  • $\begingroup$ I know there are more efficient algorithms. I remember, if I do not fault the little memory, Strassen's algorithm is slightly less than O(n^3), something like O(n^2.81). In this time I only must limit to my proposals and I need to give a more "theoretical" justification and not just in the experiments. $\endgroup$ – Delphius Apr 22 '15 at 20:15
  • $\begingroup$ Try counting exactly the number of arithmetical operations performed in each algorithm (or perhaps just the number of multiplications). $\endgroup$ – Yuval Filmus Apr 22 '15 at 20:16
  • $\begingroup$ Answered by our reference question? $\endgroup$ – Raphael Apr 22 '15 at 23:22
  • 1
    $\begingroup$ @YuvalFilmus I don't know what you mean by "concrete complexity". The actual runtime function, not only a $\Theta$-bound? Well, the reference question provides means to do that. In fact, it does barely talk about asymptotic bounds. $\endgroup$ – Raphael Apr 23 '15 at 10:40

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.