Para $n\times n$ matrices dimensionales, se sabe que el cálculo de $\operatorname{tr}\{AB\}$ necesita $n^2$ multiplicaciones escalares. ¿Cuántas multiplicaciones escalares se necesitan para calcular $\operatorname{tr}\{ABCD\}$ ? Tenga en cuenta que $\operatorname{tr}$ significa la traza de una matriz.
Como usted dice, la evaluación de un rastro es el orden $n^2$ -Tienes $n$ términos diagonales, cada uno de los cuales toma $n$ multiplica y $n$ añade para evaluar. El final $n$ se dominan las adiciones. Para hacer la traza $ABCD$ No veo nada mejor que el primer hallazgo $AB$ y $CD$ cada uno de los cuales es $n^3$ operaciones, o, si eres más inteligente $n^{2.373}$ . A continuación, utilice su $n^2$ cálculo de trazos, dando la orden $n^3$ o $n^{2.373}$ . Esto funcionará para cualquier número de Puede haber algo más inteligente por ahí.
La multiplicación de matrices puede realizarse en menos de $n^3$ multiplicación aunque aumenta la sobrecarga. Lista de Complejidad Computacional
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.
0 votos
¿Qué hace la operación tr? ¿Transponer?
1 votos
@saadtaame Creo que es rastrear .
1 votos
@saadtaame, rastrear
0 votos
Para $s$ $n\times n$ matrices $(A^{(q)})$ hay que sumar los $n$ coeficientes diagonales $(A^{(1)}\cdots A^{(s)})_{i,i}=\sum_{1\leq i_1,\ldots, i_{s-1}\leq n}A^{(1)}_{ii_1}\cdots A^{(s)}_{i_{s-1}i}$ . Esto arroja un total de $n\cdot n^{s-1}\cdot (s-1)$ multiplicaciones escalares y $(n-1)+(n^{s-1}-1)$ sumas escalares.
0 votos
@julien Para 4 matrices esto se convierte en $3n^4$ pero la sugerencia de Ross, más abajo, da $n^3$ . Y, ¿dónde $(s-1)$ ¿De dónde viene?
0 votos
@Maesumi Entiendo que para calcular el producto (resp suma) de $2$ escalares, necesita $1$ multiplicación (resp suma). $3$ escalares, $2$ multiplicaciones (resp sumas). $s$ escalares, $s-1$ multiplicaciones (resp sumas).