¿Existe un algoritmo subcúbico para el siguiente problema?

Dada una matriz simétrica real , ¿existe un algoritmo que calcule la suma sobre todo 1 \ leq i <j <k \ leq n con complejidad de tiempo mejor que O (n ^ 3) ?$n \times n$$A=(a_{ij})$

Existe un enfoque bastante práctico que funciona en tiempo , donde es el número de bits en la palabra del procesador. La idea principal es iterar sobre los elementos de la matriz uno por uno en orden creciente (romper los lazos arbitrariamente) y "encenderlos". Considere el momento en que el elemento más grande de algunos triples está encendido. Por simplicidad, supongamos que dicho elemento es . Es natural agregar el valor del triple a la respuesta ahora, cuando se enciende el último elemento. Entonces, tenemos que contar el número de posibles 's de modo que y$O(n^3 / w)$$w$$a_{ij}, a_{ik}, a_{jk}$$a_{ij}$$k$$a_{ik}$$a_{jk}$ya están encendidos (ese sería el número de triples, aquí es el elemento más grande, por lo que se encendieron por completo en este momento). Aquí podemos acelerar la implementación ingenua de utilizando la optimización de bits.$a_{ij}$$O(n)$

Para obtener detalles, puede consultar la siguiente implementación en C ++ 11 que debería funcionar para , (no está muy optimizado; sin embargo, aún supera la suma ingenua para por un amplio margen al menos en mi máquina).$n \leqslant 5000$$|a_{ij}| \leqslant 10^9$$n = 5000$

// code is not very elegant, 
// but should be understandable
// here the matrix a has dimensions n x n
// a has to be symmetric!
int64_t solve (int n, const vector<vector<int32_t>> &a)
{
        std::vector<boost::dynamic_bitset<int64_t>> mat
        (n, boost::dynamic_bitset<int64_t>(n));

        vector<pair<int, int>> order;
        for (int j = 1; j < n; j++)
        for (int i = 0; i < j; i++)
            order.emplace_back(i, j);
        sort(order.begin(), order.end(),
            [&] (const pair<int, int> &l, const pair<int, int> &r) 
            {return a[l.first][l.second] < a[r.first][r.second];});

        int64_t ans = 0;
        for (const auto &position : order)
        {
            int i, j;
            tie (i, j) = position;
            mat[i][j] = mat[j][i] = 1;
            // here it is important that conditions 
            // mat[i][i] = 0 and mat[j][j] = 0 always hold
            ans += (mat[i] & mat[j]).count() * int64_t(a[i][j]);
        }

        return ans;
}

Si considera el uso de trampas de optimizaciones de bits, puede usar el método de cuatro rusos para obtener el mismo resultado aquí, produciendo un algoritmo , que debería ser menos práctico (porque es bastante grande en la mayoría del hardware moderno) pero es teóricamente mejor. De hecho, elijamos y mantengamos cada fila de la matriz como una matriz de enteros de a , donde el -ésimo número en la matriz corresponde a los bits de la fila que van desde inclusive hasta exclusivo en$O(n^3 / \log n)$$w$$b \approx \log_2 n$$\lceil \frac{n}{b} \rceil$$0$$2^b - 1$$i$$ib$$\min(n, (i + 1)b)$$0$-indexación. Podemos precalcular los productos escalares de cada dos de estos bloques en el tiempo . Actualizar una posición en la matriz es rápido porque estamos cambiando solo un número entero. Para encontrar el producto escalar de las filas y simplemente repita los arreglos correspondientes a esas filas, busque productos escalares de los bloques correspondientes en la tabla y resuma los productos obtenidos.$O(2^{2b} b)$$i$$j$

El párrafo anterior supone que las operaciones con números enteros toman tiempo. Es una suposición bastante común , porque generalmente no cambia la velocidad comparativa de los algoritmos (por ejemplo, si no usamos esa suposición, el método de fuerza bruta realmente funciona en tiempo (aquí medimos el tiempo en operaciones de bit) si toma valores enteros con valores absolutos al menos hasta para alguna constante (y de lo contrario podemos resolver el problema con multiplicaciones matriciales de todos modos); sin embargo, el método de los cuatro rusos sugerido anteriormente usa$\leqslant n$$O(1)$$O(n^3 \log n)$$a_{ij}$$n^{\varepsilon}$$\varepsilon > 0$$O(n^{\varepsilon})$$O(n^3 / \log n)$ operaciones con números de tamaño en ese caso; por lo que realiza operaciones de bit , que aún es mejor que la fuerza bruta a pesar del cambio del modelo).$O(\log n)$$O(n^3)$

Sin embargo, la pregunta sobre la existencia del enfoque sigue siendo interesante.$O(n^{3 - \varepsilon})$

Las técnicas (optimizaciones de bits y método de cuatro rusos) presentadas en esta respuesta no son en absoluto originales y se presentan aquí para completar la exposición. Sin embargo, encontrar una manera de aplicarlos no fue trivial.