Matriz de bloques

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 25 de abril de 2019; las comprobaciones requieren 3 ediciones .

Matriz de bloque (celda) - representación de la matriz , en la que se corta por líneas verticales y horizontales en partes rectangulares - bloques ( celdas ):

\mathbf{A} = \begin{bmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} & \cdots &\mathbf{A}_{1t}\\ \mathbf{A} _{21} & \mathbf{A}_{22} & \cdots &\mathbf{A}_{2t}\\ \vdots & \vdots & \ddots &\vdots \\ \mathbf{A}_{s1 } & \mathbf{A}_{s2} & \cdots &\mathbf{A}_{st}\end{bmatriz}

donde el bloque tiene tamaño para y ${\ estilo de visualización \ mathbf {A} _ {\ alfa \ beta}}$ $m_\alfa\veces n_\beta$ $\alfa = 1, 2,\puntos, s$ $\beta = 1, 2,\puntos, t$

Ejemplo

Tamaño de matriz 4×4

\mathbf{P} = \begin{bmatriz} 1 y 1 y 2 y 2\\ 1 y 1 y 2 y 2\\ 3 y 3 y 4 y 4\\ 3 y 3 y 4 y 4\end{bmatriz}

se puede representar como una matriz de bloques de cuatro bloques de 2x2 cada uno.

En la siguiente definición de bloque

\mathbf{P}_{11} = \begin{bmatrix} 1 y 1 \\ 1 y 1 \end{bmatrix}, \mathbf{P}_{12} = \begin{bmatrix} 2 y 2\\ 2 & 2\end{bmatrix}, \mathbf{P}_{21} = \begin{bmatrix} 3 & 3 \\ 3 & 3 \end{bmatrix}, \mathbf{P}_{22} = \begin{ bmatriz} 4 y 4\\ 4 y 4\end{bmatriz}

La matriz de bloques se puede escribir de la siguiente manera:

\mathbf{P} = \begin{bmatrix} \mathbf{P}_{11} & \mathbf{P}_{12}\\ \mathbf{P}_{21} & \mathbf{P}_{22 }\end{bmatriz}.

Operaciones

Formalmente, las operaciones con matrices de bloques se realizan de acuerdo con las mismas reglas que si se tratara de elementos numéricos en lugar de bloques. Para la viabilidad de las operaciones, es necesaria una correspondencia adecuada de los tamaños de los bloques. Por ejemplo, al multiplicar matrices de bloques, se requiere que las dimensiones horizontales de los bloques del primer factor coincidan con las dimensiones verticales correspondientes del segundo factor [1] .

Suma directa

La suma directa de dos matrices cuadradas y tamaños y se define como una matriz de bloque de la siguiente forma: $\matemáticas {A}$ $\matemáticas {B}$ $m \veces m$ $n\veces n$

\mathbf{A} \oplus \mathbf{B} = \begin{bmatrix} \mathbf{A} & \mathbf{0}\\ \mathbf{0} & \mathbf{B}\end{bmatrix}

donde denota el bloque cero (matriz de tipo cero arriba y abajo). Esta operación no es conmutativa sino asociativa [2] . $\mathbf {0}$ $m\veces n$ $n \veces m$

Tipos de matrices de bloques

Muchos tipos de matrices se pueden representar en forma de bloque. En este caso, al nombre se le añade el prefijo bloque o bloque, y las operaciones sobre elementos se transforman en operaciones sobre bloques.

Matriz de bloque diagonal (cuasi-diagonal)

Para una matriz de bloques diagonales , todos los bloques, excepto los ubicados en la diagonal principal, son matrices cero.

La matriz parece

\mathbf{A} = \begin{bmatrix} \mathbf{A}_{1} & 0 & \cdots & 0 \\ 0 & \mathbf{A}_{2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \mathbf{A}_{n} \end{bmatrix},

donde cada elemento es una matriz distinta de cero. $\mathbf{A}_k$

El determinante de una matriz cuasidiagonal cuadrada es igual al producto de los determinantes de las celdas diagonales.

Matriz cuasi-triangular

Cuasi-triangular es una matriz cuadrada de bloques cuyos bloques están en (o ): $\matemáticas {A}$ $\mathbf{A}_{ij} = 0$ $yo>j$ $yo<j$

\mathbf{A} = \begin{bmatrix} \mathbf{A}_{11} & \mathbf{A}_{12} & \cdots & \mathbf{A}_{1n} \\ 0 & \mathbf{ A}_{22} & \cdots & \mathbf{A}_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \mathbf{A}_{nn} \end{bmatriz}

El determinante de una matriz cuasi-triangular es igual al producto de los determinantes de los bloques diagonales. Es fácil ver que una matriz de bloques diagonales es un caso especial de una cuasi-triangular [3] .

Bloque matriz tridiagonal

Véase también matriz tridiagonal .

Matriz de bloque Toeplitz

Véase también matriz de Toeplitz .

Multiplicación por bloques de matrices

Para aumentar la eficiencia del uso de la memoria caché de la CPU , existe un algoritmo para la multiplicación de matriz de bloques

C=AB=\left[{\begin{matriz}{ccccc}A_{{11}}&A_{{12}}&...&A_{{1n}}\\A_{{21}}&A_{{22 }}&...&A_{{2n}}\\...&...&...&...\\A_{{n1}}&A_{{n2}}&...&A_{{ nn}}\\\end{matriz}}\right]\times \left[{\begin{matriz}{ccccc}B_{{11}}&B_{{12}}&...&B_{{1n}} \\B_{{21}}&B_{{22}}&...&B_{{2n}}\\...&...&...&...\\B_{{n1}}&B_ {{n2}}&...&B_{{nn}}\\\end{matriz}}\right]

en la que la matriz resultante

C=\izquierda[{\begin{matriz}{ccccc}C_{{11}}&C_{{12}}&...&C_{{1n}}\\C_{{21}}&C_{{22}} &...&C_{{2n}}\\...&...&...&...\\C_{{n1}}&C_{{n2}}&...&C_{{nn} }\\\end{matriz}}\right]

se forma bloque a bloque utilizando la conocida fórmula

C_{{ij}}=\sum_{{k=1}}^{{n}}A_{{ik}}\times B_{{kj}}

o sus análogos más rápidos, y el tamaño de los datos procesados en cada iteración no excede la capacidad de la memoria caché. El tamaño del bloque depende directamente de la arquitectura del sistema informático y determina el tiempo de ejecución de la multiplicación [4] . Se utiliza un enfoque similar en la multiplicación de matrices basada en GPU con optimización del uso limitado de memoria compartida [5] [6] .

Fórmulas

Fórmula de Frobenius

Para invertir una matriz de bloques no degenerados, se puede utilizar la fórmula de Frobenius :

\left[\begin{array}{ccccc} A & B \\ C & D \\ \end{array}\right]^{-1} = \left[\begin{array}{ccccc} A^{- 1} +A^{-1} BH^{-1} CA^{-1} & -A^{-1} BH^{-1} \\ -H^{-1} CA^{-1} & H^{-1} \\ \end{matriz}\right],

donde es una matriz cuadrada no singular de tamaño , es una matriz cuadrada de tamaño y . $A$ $m_1\veces m_1$ $D$ $m_2\veces m_2$ $H=D-CA^{-1}B$

Esta fórmula nos permite reducir la inversión de la matriz de tamaño a la inversión de dos matrices más pequeñas y las operaciones de multiplicación y suma de matrices de tamaño , , , [7] . $(m_1+m_2)\veces (m_1+m_2)$ $m_1\veces m_1$ $m_2\veces m_2$ $m_1\veces m_1$ $m_2\veces m_2$ $m_1\veces m_2$ $m_2\veces m_1$

Notas

↑ Gantmakher, 2004 , pág. 53-54.
↑ Ilyin, Poznyak, 2007 , pág. Dieciocho.
↑ Gantmakher, 2004 , pág. 55.
↑ Vatutin E.I., Martynov I.A., Titov V.S. Evaluación del rendimiento real de los procesadores modernos en el problema de la multiplicación de matrices para una implementación de software de un solo subproceso. Archivado el 11 de enero de 2015 en Wayback Machine // Actas de la Southwestern State University . Serie: Gestión, informática, informática. Instrumentación médica. 2013. Nº 4. - S. 11-20.
↑ Vatutin E. I., Martynov I. A., Titov V. S. Estimation of the real performance of modern video cards with CUDA technology support in the problem of matrix multiplication Archivado el 11 de enero de 2015 en Wayback Machine // Proceedings of the Southwestern State University . Serie: Gestión, informática, informática. Instrumentación médica. 2014. Nº 2. - S. 8-17.
↑ Cómputo paralelo en la GPU. Arquitectura y modelo de software de CUDA / Boreskov A. V., Kharlamov A. A. Markovsky N. D. et al. - M . : Izd-vo Mosk. un-ta, 2012. - 336 p.
↑ Gantmakher, 2004 , pág. 57-58.

Literatura

Gantmakher F.R. Teoría de la matriz. - 5ª ed. — M .: Fizmatlit , 2004. — 560 p. — ISBN 5-9221-0524-8 .
Ilyin V. A. , Poznyak E. G. . Álgebra lineal. - 6ª ed., estereotipada. — M .: Fizmatlit , 2007. — 278 p. — (Curso de Matemática Superior y Física Matemática, número 4). - ISBN 978-5-9221-0481-4 .
Rublev A. N. Álgebra lineal. - M. : Escuela superior , 1968. - 387 p.