Блочная матрица

Бло́чная (кле́точная) ма́трица — представление матрицы, при котором она рассекается вертикальными и горизонтальными линиями на прямоугольные части — блоки (клетки):

\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{bmatrix}}

,

где блок $\mathbf {A} _{\alpha \beta }$ имеет размер $m_{\alpha }\times n_{\beta }$ для $\alpha =1,2,\dots ,s$ и $\beta =1,2,\dots ,t$

Пример

Матрица размера 4×4

\mathbf {P} ={\begin{bmatrix}1&1&2&2\\1&1&2&2\\3&3&4&4\\3&3&4&4\end{bmatrix}}

может быть представлена в виде блочной матрицы из четырёх блоков размера 2×2 каждый.

При следующем определении блоков

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

блочная матрица может быть записана в таком виде:

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

Операции

Формально операции с блочными матрицами производятся по тем же правилам, как если бы на месте блоков были числовые элементы. Для выполнимости операций необходимо соответствующее согласование размеров блоков. Например, при умножении блочных матриц требуется, чтобы горизонтальные размеры блоков первого сомножителя совпадали с соответствующими вертикальными размерами второго сомножителя[1].

Прямая сумма

Прямая сумма двух квадратных матриц $\mathbf {A}$ и $\mathbf {B}$ размеров $m\times m$ и $n\times n$ определяется как блочная матрица следующего вида:

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

где $\mathbf {0}$ обозначает нулевой блок(нулевую матрицу типа $m\times n$ вверху и $n\times m$ внизу). Эта операция некоммутативна, но ассоциативна[2].

Виды блочных матриц

Многие виды матриц могут быть представлены в блочном виде. В этом случае к названию добавляется приставка блочно- или блочная, а операции над элементами трансформируются в операции над блоками.

Блочно-диагональная (квазидиагональная) матрица

У блочно-диагональной матрицы все блоки, кроме расположенных на главной диагонали, являются нулевыми матрицами.

Матрица выглядит, как

\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}},

где каждый элемент $\mathbf {A} _{k}$ является ненулевой матрицей.

Определитель квадратной квазидиагональной матрицы равен произведению определителей диагональных клеток.

Квазитреугольная матрица

Квазитреугольной называется блочная квадратная матрица $\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}}

.

Определитель квазитреугольной матрицы равен произведению определителей диагональных блоков. Легко заметить, что блочно-диагональная матрица является частным случаем квазитреугольной[3].

Блочно-трёхдиагональная матрица

См. также трёхдиагональная матрица.

Блочно-теплицева матрица

См. также матрица Тёплица.

Блочное умножение матриц

С целью повышения эффективности использования кэш-памяти CPU существует алгоритм блочного умножения матриц

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]

,

в котором результирующая матрица

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]

формируется поблочно с использованием известной формулы

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

либо её более быстрых аналогов, а размер обрабатываемых данных на каждой итерации не превышает ёмкость кэш-памяти. Размер блока напрямую зависит от архитектуры вычислительной системы и определяет время выполнения умножения[4]. Аналогичный подход применяется при умножении матриц с использованием GPU с оптимизацией использования разделяемой памяти ограниченного объёма[5][6].

Формулы

Формула Фробениуса

Для обращения невырожденной блочной матрицы может использоваться формула Фробениуса:

\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],

где $A$ — невырожденная квадратная матрица размера $m_{1}\times m_{1}$ , $D$ — квадратная матрица размера $m_{2}\times m_{2}$ и $H=D-CA^{-1}B$ .

Эта формула позволяет свести обращение матрицы размера $(m_{1}+m_{2})\times (m_{1}+m_{2})$ к обращению двух матриц меньшего размера $m_{1}\times m_{1}$ и $m_{2}\times m_{2}$ и операциям умножения и сложения матриц размеров $m_{1}\times m_{1}$ , $m_{2}\times m_{2}$ , $m_{1}\times m_{2}$ , $m_{2}\times m_{1}$ [7].

Примечания

Гантмахер, 2004, с. 53—54.
Ильин, Позняк, 2007, с. 18.
Гантмахер, 2004, с. 55.
Ватутин Э. И., Мартынов И. А., Титов В. С. Оценка реальной производительности современных процессоров в задаче умножения матриц для однопоточной программной реализации // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2013. № 4. — С. 11—20.
Ватутин Э. И., Мартынов И. А., Титов В. С. Оценка реальной производительности современных видеокарт с поддержкой технологии CUDA в задаче умножения матриц // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2014. № 2. — С. 8—17.
Параллельные вычисления на GPU. Архитектура и программная модель CUDA / Боресков А. В., Харламов А. А. Марковский Н. Д. и др. — М.: Изд-во Моск. ун-та, 2012. — 336 с.
Гантмахер, 2004, с. 57—58.

Литература

Гантмахер Ф. Р. . Теория матриц. — 5-е изд. — М.: Физматлит, 2004. — 560 с. — ISBN 5-9221-0524-8.
Ильин В. А., Позняк Э. Г. . Линейная алгебра. — 6-е изд., стереотипное. — М.: Физматлит, 2007. — 278 с. — (Курс высшей математики и математической физики, вып. 4). — ISBN 978-5-9221-0481-4.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_b9ae25cfb4342c1b-1] Гантмахер, 2004, с. 53—54.

[_dbbd1a23d1894077-2] Ильин, Позняк, 2007, с. 18.

[_7c42e9e9db90abf4-3] Гантмахер, 2004, с. 55.

[4] Ватутин Э. И., Мартынов И. А., Титов В. С. Оценка реальной производительности современных процессоров в задаче умножения матриц для однопоточной программной реализации // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2013. № 4. — С. 11—20.

[5] Ватутин Э. И., Мартынов И. А., Титов В. С. Оценка реальной производительности современных видеокарт с поддержкой технологии CUDA в задаче умножения матриц // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2014. № 2. — С. 8—17.

[6] Параллельные вычисления на GPU. Архитектура и программная модель CUDA / Боресков А. В., Харламов А. А. Марковский Н. Д. и др. — М.: Изд-во Моск. ун-та, 2012. — 336 с.

[_4221bc8a4f55f613-7] Гантмахер, 2004, с. 57—58.