eficiente de la suma de $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n}\sum_{l=1}^{n}A_{ij}A_{ik}A_{il}A_{jk}A_{jl}A_{kl}$

Question

Quiero encontrar un algoritmo eficiente para calcular una suma de productos con enredados índices. Por ejemplo, $\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{n} A_{ij}A_{jk}A_{ki}$ donde $A_{ij}$ es el $i$-ésima fila y $j$-ésimo elemento de la columna de una matriz simétrica A. El ejemplo anterior es equivalente a calcular la traza de la cúbico de una matriz simétrica. Así que esto está relacionado con la multiplicación de la matriz.

Además, los productos pueden ser extendida tiene más elementos, como $A_{ij}A_{ik}A_{il}A_{jk}A_{jl}A_{kl}$, donde todos los índices están peleando (como una camarilla en un gráfico), y $A$ también se puede extender a un simétrica de mayor rango del tensor. El ingenuo algoritmo para calcular la suma es $O(n^m)$ donde $m$ es el número de índices. Quiero reducir la complejidad computacional tanto como sea posible. Al $A$ es una matriz y $m=3$, esta se ha convertido en una multiplicación de la matriz problema, pero ¿qué hay de los casos más generales?

Pregunta1: me pregunto si alguien sabe de matemáticas temas o libros relacionados con mi problema.

Pregunta2: ¿Cuál es el término matemático para la suma de los productos con enredados índices? Es difícil para mí a google sin referencias a la terminología estándar.

Answer 1

Actualización 2: Si usted considerar la rápida multiplicación de la matriz de algoritmos, entonces usted puede hacer mejor que el ingenuo $O(n^4)$. Permítanme supongamos que existe un algoritmo que calcula el producto de una $l\times m$ $m\times n$ matriz en $O(l m^\epsilon n)$ del tiempo, con $\epsilon < 1$. Permítanme cambiar un poco la notación $A(i,j) \to A(i;j)$ a resaltar la diferencia entre el entrante y saliente de la matriz de índices. A continuación, considere los siguientes pasos.

1. la fijación de $({k,l,i})$ $n^3$ veces ($1\times 1$ por $1\times 1$): $B_1(k,l;i) = A(k;l) A(k;i) A(l;i)$
2. la fijación de $(k)$ $n$ veces ($n\times n$ por $n\times n$): $B_2(k,j;i) = \sum_l A(j;l) B_1(k,l;i)$
3. la fijación de $(j)$ $n$ veces ($1\times n$ por $n\times n$): $B_3(j;i) = \sum_k A(j;k) B_2(k,j;i)$
4. la fijación de $(i)$ $n$ veces ($1\times n$ por $n\times 1$): $B_4(i) = \sum_j A(i;j) B_3(j;i)$
5. do $1$ tiempo ($1\times n$ por $n\times 1$): $B_5 = \sum_i B_4(i)$

$B_5$ es la suma que desee, como se puede ver mediante la sustitución de cada una de las $B_i$ en la siguiente expresión. El prefijo de cada paso que indica la complejidad como un número dado (para cada valor de la lista de índices) de la matriz rectangular multiplicaciones de los tamaños indicados, que también da a los requisitos de almacenamiento.

Como se puede ver, el tiempo de ejecución de la complejidad estará dominada por el paso 2, con $O(n^{3+\epsilon})$ operaciones. Los pasos 1 y 2 dominan en términos de almacenamiento, que requieren $O(n^3)$ espacio. Como usted señala en los comentarios, $\epsilon = 0.37$ es el mejor valor conocido. A continuación, $3+\epsilon = 3.37 < 4$ hace latir el método ingenuo.

Actualización: lo Siento, en más de reflexión, no creo que se puede hacer mejor con este particular, la contracción de $O(n^4)$, al menos no con las optimizaciones que yo tenía en mente. Estas optimizaciones son de una dinámica de programación de clase. Es decir, el uso de almacenamiento adicional para los resultados intermedios con la esperanza de obtener una aceleración en las operaciones que le llevan de un resultado intermedio a la siguiente. En este caso, el almacenamiento consistiría en matrices multidimensionales de tamaño $O(n^d)$ (para algunos $d$) y las operaciones consisten en la multiplicación por una o más copias de $A$ y la suma de más de uno o más de los índices de matriz, que implican $O(n^f)$ operaciones (para algunos $f$). Pero de cualquier manera yo trate de hacer que siempre se obtiene el $f\ge 4$, que no es mejor que el enfoque ingenuo.

---

Expresiones como estas son a veces conocido como el tensor de redes. Esto te dará una buena palabra clave para buscar en la literatura. También, usted puede encontrar de utilidad algunos de los "dispersos de la factorización de" técnicas de uno de mis artículos antiguos (arXiv:0809.3190). Puede ignorar todo excepto la sección 5 y el debate de cómo evaluar el producto-seguimiento en la ecuación (40).

Como has escrito, la evaluación de la complejidad es $O(n^4)$. Creo que este caso puede ser simplificado a $O(n^3)$. Si tengo tiempo más tarde, voy a tratar de escribir que en más detalle.