WikiSort.ru - Не сортированное

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

${\displaystyle \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}}}$ ,

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

Пример

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

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

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

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

${\displaystyle \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}}}$

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

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

Операции

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

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

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

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

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

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

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

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

Этот раздел не завершён. Вы поможете проекту, исправив и дополнив его.

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

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

${\displaystyle 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]}$ ,

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

${\displaystyle 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]}$

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

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

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

Формулы

Примечания

Литература

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