Supongamos que a (m+n) (m+n) de la matriz $\textbf{A}$ con el bloque de la partición:
$\textbf{A}=\begin{pmatrix}\textbf{E}&\textbf{F}\\\\ \textbf{G}&\textbf{H}\end{pmatrix}$
Una secuencia de pasos puede ser descrito, invocando de forma recursiva en lugar de la matriz de inversión y otras medidas que incluyan, en lugar de la multiplicación de la matriz.
Algunos, pero no todos, de estos la multiplicación de la matriz de operaciones, parece requerir memoria adicional para ser "temporal", asignan entre las llamadas recursivas a el en lugar de la inversión de matrices. En la parte inferior vamos a argumentar que se necesita memoria adicional es lineal, por ejemplo, el tamaño m+n.
1. El primer paso es recursivamente a invertir en el lugar de la matriz $\textbf{E}$:
$\begin{pmatrix}\textbf{E}^{-1}&\textbf{F}\\\\ \textbf{G}&\textbf{H}\end{pmatrix}$
Por supuesto, para hacer que el trabajo requiere que el líder principal menor $\textbf{E}$ a ser nonsingular.
2. El siguiente paso es multiplicar $\textbf{E}^{-1}$ tiempos bloque submatriz $\textbf{F}$ e invalidar el resultado:
$\begin{pmatrix}\textbf{E}^{-1}&-\textbf{E}^{-1}\textbf{F}\\\\ \textbf{G}&\textbf{H}\end{pmatrix}$
Tenga en cuenta que la multiplicación de la matriz y sobrescribir en este paso puede realizarse de una columna de $\textbf{F}$ a un tiempo, algo que vamos a revisar en la evaluación de los requisitos de memoria.
3. Siguiente multiplicar $\textbf{G}$ veces el resultado anterior $-\textbf{E}^{-1}\textbf{F}$ y añadir al bloque existente submatriz $\textbf{H}$:
$\begin{pmatrix}\textbf{E}^{-1}&-\textbf{E}^{-1}\textbf{F}\\\\ \textbf{G}&\textbf{H}-\textbf{G}\textbf{E}^{-1}\textbf{F}\end{pmatrix}$
Este paso también se puede realizar en una columna a la vez, y porque los resultados son acumulados en el bloque existente submatriz $\textbf{H}$, no se necesita memoria adicional.
Tenga en cuenta que lo que se ha sobrescrito $\textbf{H}$$\textbf{S}=\textbf{H}-\textbf{G}\textbf{E}^{-1}\textbf{F}$.
4. & 5. Los dos próximos pasos pueden realizarse en cualquier orden. Queremos multiplicar bloque submatriz $\textbf{G}$ a la derecha por $\textbf{E}^{-1}$, y también queremos invertir de forma recursiva en el lugar del resultado anterior $\textbf{S}$. Después de hacer tanto tenemos:
$\begin{pmatrix}\textbf{E}^{-1}&-\textbf{E}^{-1}\textbf{F}\\\\ \textbf{G}\textbf{E}^{-1}&\textbf{S}^{-1}\end{pmatrix}$
Tenga en cuenta que la multiplicación de la matriz y la sobreescritura de $\textbf{G}$ se puede hacer de una fila a la vez.
6. Siguiente debemos multiplicar estos dos últimos resultados, sobrescribiendo $\textbf{G}\textbf{E}^{-1}$ $\textbf{S}^{-1}\textbf{G}\textbf{E}^{-1}$ y la negación de que el bloque:
$\begin{pmatrix}\textbf{E}^{-1}&-\textbf{E}^{-1}\textbf{F}\\\\ -\textbf{S}^{-1}\textbf{G}\textbf{E}^{-1}&\textbf{S}^{-1}\end{pmatrix}$
7. Estamos en la recta final, ahora! Multiplicar los dos fuera de la diagonal de bloques y añadir que a la diagonal bloque que contenga $\textbf{E}^{-1}$:
$\begin{pmatrix}\textbf{E}^{-1}+\textbf{E}^{-1}\textbf{F}\textbf{S}^{-1}\textbf{G}\textbf{E}^{-1}&-\textbf{E}^{-1}\textbf{F}\\\\ -\textbf{S}^{-1}\textbf{G}\textbf{E}^{-1}&\textbf{S}^{-1}\end{pmatrix}$
8. Finalmente, multiplicamos el bloque que contiene a $-\textbf{E}^{-1}\textbf{F}$ a la derecha por $\textbf{S}^{-1}$, algo que se puede hacer de una fila a la vez:
$\textbf{A}^{-1}=\begin{pmatrix}\textbf{E}^{-1}+\textbf{E}^{-1}\textbf{F}\textbf{S}^{-1}\textbf{G}\textbf{E}^{-1}&-\textbf{E}^{-1}\textbf{F}\textbf{S}^{-1}\\\\ -\textbf{S}^{-1}\textbf{G}\textbf{E}^{-1}&\textbf{S}^{-1}\end{pmatrix}$
Requisitos para memoria adicional:
Una necesidad temporal de memoria adicional surge cuando queremos hacer la multiplicación de la matriz y almacenar el resultado en la ubicación de uno de los dos factores.
Esta necesidad surge en el paso 2. cuando la formación de $\textbf{E}^{-1}\textbf{F}$, en el paso 4. (o 5.) cuando la formación de $\textbf{G}\textbf{E}^{-1}$, en el paso 6. cuando la formación de $\textbf{S}^{-1}\textbf{G}\textbf{E}^{-1}$, y en el paso 8. cuando la formación de $-\textbf{E}^{-1}\textbf{F}\textbf{S}^{-1}$.
Por supuesto, de otros "temporal" de las asignaciones están ocultos en las llamadas recursivas a en lugar de la inversión en el paso 1. y en el paso 4.&5. cuando las matrices de $\textbf{E}$ $\textbf{S}$ están invertidas.
En cada caso, la memoria asignada puede ser liberado (o reutilizados), después de una columna o una fila de una matriz de multiplicación se realiza, debido a la sobreescritura se puede hacer de una columna o de fila en fila siguiente a su cálculo. La sobrecarga de tales asignaciones se limita a la talla m+n, o, incluso, max(m,n), es decir, una sobrecarga lineal en el tamaño de $\textbf{A}$.
