16 votos

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

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?

17voto

tooshel Puntos 475

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.)

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X