Presta atención ya que en esta crónica encontrarás el hallazgo que buscas.
Solución:
El algoritmo de multiplicación de matrices más rápido es una importante pregunta matemática abierta
La página de Wikipedia https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm#Sub-cubic_algorithms muestra cómo el rápido algoritmo asintótico conocido ha evolucionado a lo largo del tiempo:
Esto plantea la pregunta: ¿qué tan cerca podemos llegar a O(n^2), que por supuesto es un límite inferior ya que tenemos que leer 2 * n^2 entradas al menos una vez?
Demostrar el límite inferior superior, incluso de forma no constructiva, te haría famoso al instante. Wikipedia lo enumera como un “problema sin resolver en informática”.
Sin embargo, el factor constante para los mejores algoritmos es tan grande que los hace poco prácticos para la mayoría de los tamaños de matriz que se encuentran en la práctica hoy en día, y dudo que esto cambie si se encuentran nuevos algoritmos.
Por lo tanto, cualquier respuesta práctica del mundo real se reducirá a la optimización contra un modelo de máquina dado, que es una cuestión importante de optimización de ingeniería de software/hardware, pero no de mucho interés matemático.
Suposición personal sobre la resolución de variables individuales: no creo que pueda reducir la complejidad de esa manera en general, ya que todo el sistema está acoplado. ¿Cómo sabría que su solución para algunas variables también satisface la solución global completa?
A menos que su matriz sea escasa o estructurada (por ejemplo, Vandermonde, Hankel o esas otras familias de matrices nombradas que admiten un método de solución rápido), no hay muchas esperanzas de hacer las cosas mejor que el esfuerzo de $O(n^3)$. Incluso si uno se limitara a resolver solo una de las 50,000 variables, Cramer exigirá calcular dos determinantes para su respuesta, y el esfuerzo para calcular un determinante es al menos tanto como descomponer/invertir una matriz para empezar.
Hay una manera de reducir la complejidad y hacer que el sistema se pueda resolver en paralelo. Se llama Diakoptics (un método inventado por Gabriel Kron). El uso principal de los métodos es para grandes redes eléctricas que tienen pocas interconexiones como las redes eléctricas. Pero deberías poder adaptarlo.
La complejidad (para el caso a continuación) se reduce de $O(n^3)$ a $O(2(fracn2)^3)$ o $O(frac14 n^3)$, el impacto puede ser mucho mayor si el sistema se divide en más subsistemas. Para ese caso la complejidad es ($s$-subsistemas, $c$-puntos de interconexión) $O(c^3)+O((fracn^3s²))$, si el sistema se divide en subsistemas de igual tamaño. No estoy seguro acerca de la notación para múltiples variables, pero debería entender el punto.
En breve:
Supongamos que tiene un sistema $N times N$, digamos que puede dividir el sistema en dos sistemas con 1 punto de conexión (más la referencia cuando observa los sistemas eléctricos). Los puntos de conexión son $m$ y $n$. Supongamos que estos sistemas son del tamaño $N_1=N/2$ y $N_2=N/2$ (por razones de simplicidad). Ahora debe resolverlos por separado.
$ mathbf A_1 ^ – 1 = mathbf B_1 $
$mathbf A_2^-1=mathbf B_2$
El siguiente paso es volver a juntarlos, eso se hace con la ayuda de la llamada “Matriz de Thevenin” (en nuestro caso es 1$times$1). Puede buscar el principio exacto para órdenes más altas (más puntos de conexión), pero para este ejemplo se ve así: beginalign mathbfB_TH=B_1mm+B_2nn-2B_ mn endalign Para nuestro caso tenemos $B_mn=0$. Ahora necesitamos las soluciones $x_1$ y $x_2$ para formar los coeficientes $b_th$.
$mathbf x_th=x_1m-x_2n$
$mathbf b_p=mathbfB_TH^-1 mathbf x_th$
beginalign mathbf b_th=beginbmatrix0&cdots&b_p&cdots&-b_p&cdots&0 endbmatrix^T endalign
La matriz $mathbf b_th$ solo tiene elementos distintos de cero en $m$ y $N/2 +n$. Ahora finalmente podemos encontrar la solución $x_n$ para todo el sistema: beginalign mathbf x_n=beginbmatrixx_1\x_2 endbmatrix-beginbmatrixB_1&0\0&B_2 end bmatrixbeginbmatrixb_th endbmatrix endalign
Estoy más acostumbrado a la notación de ingeniería con $Z, I, U$, etc., así que disculpe el uso de símbolos no estándar.
Recuerda que tienes la capacidad de glosar tu experiencia si te fue útil.