Blockmatris

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 25 april 2019; kontroller kräver 3 redigeringar .

Blockmatris (cell) - representation av matrisen , där den skärs av vertikala och horisontella linjer i rektangulära delar - block ( celler ):

\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 & \ dDots & \ vdots {a {a} {s1 {s1 {s1 } & \ mathbf {a} _ {s2} & \ cdots & \ mathbf {a} {St.} \ end {bmatrix}

där blocket har storlek för och ${\ DisplayStyle \ Mathbf {a} _ {\ Alpha \ Beta}}$ $m_ \ alfa \ gånger n_ \ beta$ $\ alfa = 1, 2, \ prickar, s$ $\ beta = 1, 2, \ prickar, t$

Exempel

Matrisstorlek 4×4

\ Mathbf {p} = \ börja {bmatrix} 1 & 1 & 2 & 2 & 2 & 1 & 2 & 2 & 2 & 2 & 3 & 4 & 4 \\ 3 & 4 & 4 & 4 \ END {BMATRIX}

Den kan presenteras i form av en blockmatris av fyra block med storleken 2 × 2.

Vid nästa blockdefinition

\ Mathbf {p} _ {11} = \ start {bmatrix} 1 & 1 \\ 1 & 1 \ End {bmatrix}, \ mathbf {12} = \ bein {bmatrix} 2 & 2 \\ & 2 \ end { bmatrix}, \ mathbf {p} _ {21} = \ bein {bmatrix} 3 & 3 \\ 3 & 3 \ end {bmatrix}, \ mathbf {22} = \ begin { bmatrix} 4 & 4 \\ 4 & 4 \ end {bmatrix}

Blockmatrisen kan skrivas på följande sätt:

\ Mathbf {p} = \ begin {bmatrix} \ mathbf {p} _ {11} & \ mathbf {p} _} \\ \ mathbf {p} _ {21} {p} {22 {22 } \ end { bmatrix}.

Operationer

Formellt utförs operationer med blockmatriser enligt samma regler, som om det fanns numeriska element i stället för blocken. För utförande av operationer är lämplig samordning av storleken på blocken nödvändig. Till exempel, när man multiplicerar blockmatriser, krävs det att de horisontella storlekarna på blocken i den första tvivelaktiga sammanfaller med motsvarande vertikala dimensioner för den andra dubbningen [1] .

Direkt summa

Den raka mängden av två kvadratiska matriser och storlekar definieras som en blockmatris av följande typ: $\mathbf {A}$ $\mathbf {B}$ $m \ gånger m$ $n\ gånger n$

\ mathbf {a} \ oplus \ mathbf {b} = \ start {bmatrix} \ mathbf {a} {0} \\ \ mathbf {0} {b} \ end {bmatrix}} {bmatrix}

där anger nollblocket (nolltypsmatris ovanför och under). Denna operation är icke- kommutativ men associativ [2] . $\mathbf {0}$ $m\ gånger n$ $n \ gånger m$

Typer av blockmatriser

Många typer av matriser kan representeras i blockform. I det här fallet läggs ett block eller blockprefix till i namnet, och operationer över elementen omvandlas till operationer över blocken.

Blockdiagonal (kvasidiagonal) matris

I blockdiagonalmatrisen är alla block, förutom huvuddiagonalen, nollmatriser.

Matrisen ser ut

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

där varje element är en matris som inte är noll. $\ Mathbf {a} _K$

Determinanten för den kvadratiska kvasiidiagonala matrisen är lika med produkten av determinanterna för diagonala celler.

Kvasitriangulär matris

Den kvasirala storleken kallas blockkvadratmatrisen där blocken vid (eller ): $\mathbf {A}$ $\ mathbf {a} _ {ij} = 0$ $i>j$ $i<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 {bmatrix}

Determinanten för den kvasirala matrisen är lika med produkten av determinanterna för de diagonala blocken. Det är lätt att märka att den blockdiagonala matrisen är ett specialfall av quasirall [3] .

Blockera tridiagonal matris

Se även tridiagonal matris .

Block Toeplitz-matris

Se även Toeplitz matris .

Blockmultiplikation av matriser

För att öka effektiviteten av att använda CPU- cache finns det en algoritm för blockmultiplikation av matris

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

där den resulterande matrisen

C=\left[{\begin{array}{ccccc}C_{{11}}&C_{{12}}&...&C_{{1n}}\\C_{{21}}&C_{{22}} &...&C_{{2n}}\\...&...&...&...\\C_{{n1}}&C_{{n2}}&...&C_{{nn} } \\\ end {Array}} \ Right]

bildas block för block med den välkända formeln

C_{{ij}}=\summa _{{k=1}}^{{n}}A_{{ik}}\ gånger B_{{kj}}

eller dess snabbare analoger, och storleken på den bearbetade datan vid varje iteration överstiger inte cacheminnets kapacitet. Blockstorleken beror direkt på datorsystemets arkitektur och bestämmer multiplikationstiden [4] . Ett liknande tillvägagångssätt används i GPU -baserad matrismultiplikation med optimering av begränsad användning av delat minne [5] [6] .

Formler

Frobenius formel

För att invertera en icke-degenererad blockmatris kan Frobenius -formeln användas :

\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 {Array} \ Right],

Där - en outforskad kvadratisk matris av storlek , är en kvadratisk matris av storlek och . $A$ $m_1 \ gånger m_1$ $D$ $m_2 \ gånger m_2$ $H = d-ca^{-1} b$

Denna formel låter dig reducera tilltalandet av storlekens matris till cirkulationen av två mindre matriser och operationerna för multiplikation och addition av storlekar ,,,, [ 7 ] . $(m_1+m_2) \ gånger (m_1+m_2)$ $m_1 \ gånger m_1$ $m_2 \ gånger m_2$ $m_1 \ gånger m_1$ $m_2 \ gånger m_2$ $m_1 \ gånger m_2$ $m_2 \ gånger m_1$

Anteckningar

↑ Gantmakher, 2004 , sid. 53-54.
↑ Ilyin, Poznyak, 2007 , sid. arton.
↑ Gantmakher, 2004 , sid. 55.
↑ Vatutin E.I., Martynov I.A., Titov V.S. Utvärdering av den verkliga prestandan hos moderna processorer i problemet med matrismultiplikation för en enkeltrådad mjukvaruimplementering Arkiverad 11 januari 2015 på Wayback Machine // Proceedings of the Southwestern State University . Serie: Management, datateknik, informatik. Medicinsk instrumentering. 2013. Nr 4. - S. 11-20.
↑ Vatutin E. I., Martynov I. A., Titov V. S. Uppskattning av den verkliga prestandan för moderna grafikkort med CUDA-teknikstöd i problemet med matrismultiplikation Arkiverad 11 januari 2015 på Wayback Machine // Proceedings of the Southwestern State University . Serie: Management, datateknik, informatik. Medicinsk instrumentering. 2014. Nr 2. - S. 8-17.
↑ Parallell beräkning på GPU:n. Arkitektur och mjukvarumodell av CUDA / Boreskov A. V., Kharlamov A. A. Markovsky N. D. et al. - M . : Izd-vo Mosk. un-ta, 2012. - 336 sid.
↑ Gantmakher, 2004 , sid. 57-58.

Litteratur

Gantmakher F. R. . Matristeori. - 5:e uppl. — M .: Fizmatlit , 2004. — 560 sid. — ISBN 5-9221-0524-8 .
Ilyin V. A. , Poznyak E. G. . Linjär algebra. - 6:e uppl., stereotypt. — M .: Fizmatlit , 2007. — 278 sid. — (Kurs i högre matematik och matematisk fysik, nummer 4). - ISBN 978-5-9221-0481-4 .
Rublev A. N. Linjär algebra. - M . : Högre skola , 1968. - 387 sid.