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?
Respuesta
¿Demasiados anuncios?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.)