¿Es más rápido multiplicar una matriz por su transposición que la multiplicación de una matriz ordinaria?

Question

Estoy escribiendo un programa que multiplica una matriz por su transposición, y estaba tratando de encontrar hackeos de eficiencia que pudiera explotar considerando que las dos matrices que se están multiplicando están relacionadas. ¿Alguna idea?

Answer 1

Después de la sugerencia de Sivaram estoy convirtiendo mi comentario en una respuesta.

En general, $(AB)^ \textrm {T}=B^ \textrm {T}A^ \textrm {T}$ así que para el producto de una matriz con su transposición, tienes $AA^ \textrm {T}=(AA^ \textrm {T})^ \textrm {T}$ es simétrico. También puedes ver esto directamente observando que si el $ij$ la entrada de $A$ es $a_{ij}$ entonces el $ij$ la entrada de $AA^ \textrm {T}$ es $\sum_ {k=1}^n a_{ik}a_{jk}$ que es lo mismo si cambias $i$ y $j$ . Por lo tanto, si se calculan las entradas con $i \leq j$ tienes las entradas con $i>j$ de forma gratuita. Hay $1+2+3+ \cdots +n= \frac {n(n+1)}{2}$ tales entradas, en lugar de la $n^2$ que generalmente necesitas.

(Estaba pensando en $n$ -por- $n$ matrices, pero si su entrada es $m$ -por- $n$ esto te dará $\frac {m(m+1)}{2}$ cálculos de entrada, cada uno de los cuales es una suma de $n$ productos.)