Как умножать блочные матрицы

Блочные матрицы и кронекеровские произведение и сумма матриц

Блочные (клеточные) матрицы и операции над ними

Пример 1.25. Даны блочные матрицы

Следовательно, матрица будет следующая

Матрица будет иметь блоки тех же размеров, что и :

Поэтому матрица будет иметь вид

Используя правило транспонирования блочных матриц, получаем

Умножение блочных матриц

Пример 1.26. Даны блочные матрицы

Следовательно, матрица будет иметь вид

1. Операции сложения, умножения на число и произведения блочных матриц выполняются по тем же правилам, что и для обычных матриц, только вместо элементов в формулах используются блоки.

2. Выполняя операции над блочными матрицами, всегда можно их рассматривать как числовые, и проводить указанные операции по обычным правилам для числовых матриц. При этом результат операций (числовая матрица) будет один и тот же. Действия с блочными матрицами предпочтительнее, чем с числовыми, в том случае, когда в результате вычислений требуется искать не всю матрицу, а только ее часть — блок.

Пример 1.27. Найти произведение матриц четвёртого порядка

Решение. Разобьем данные матрицы на блоки размеров

где — единичная, — нулевая. Запишем сначала произведение блочных матриц

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

Осталось записать результат

Кронекеровские произведение и сумма матриц

называется правым кронекеровским произведением матриц и (или правым прямым произведением матриц ).

Пусть и квадратные матрицы n-го и m-го порядков соответственно. Кронекеровскои суммой матриц и называется квадратная матрица mn-го порядка

где — единичные матрицы соответствующих порядков.

Пример 1.28. Даны матрицы

Источник

Алгебра блочных матриц возникает, как правило, из двойных произведений в категориях матриц.

СОДЕРЖАНИЕ

Пример

можно разбить на четыре блока 2 × 2

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

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

Или, используя нотацию Эйнштейна, которая неявно суммирует повторяющиеся индексы:

Обращение блочной матрицы

Если матрица разбита на четыре блока, ее можно поблочно инвертировать следующим образом:

Эквивалентно, переставляя блоки:

Если A и D оба обратимы, то:

Согласно тождеству Вайнштейна – Ароншайна одна из двух матриц в блочно-диагональной матрице обратима в точности тогда, когда другая обратима.

Определитель блочной матрицы

Блочно-диагональные матрицы

Для определителя и следа выполняются следующие свойства

Блочно-диагональная матрица обратима тогда и только тогда, когда каждый из ее главных диагональных блоков обратим, и в этом случае ее обратная матрица является другой блочно-диагональной матрицей, заданной формулой

Блочные трехдиагональные матрицы

Блочные матрицы Теплица

Блок Теплица матрица является еще специальным блоком матрицей, которая содержит блоки, которые повторяются вниз по диагонали матрицы, в качестве матрицы Теплицы имеет элементы повторяются вниз по диагонали. Отдельные элементы блочной матрицы Aij также должны быть тёплицевой матрицей.

Блочная теплицева матрица A имеет вид

Блокировать транспонирование

Прямая сумма

Эта операция естественным образом обобщается на массивы произвольных размеров (при условии, что A и B имеют одинаковое количество измерений).

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

Заявление

Источник

Как умножать блочные матрицы

Умножение матриц при блочной схеме разделения данных

где каждый блок C ij матрицы C определяется в соответствии с выражением:

Алгоритм Фокса умножения матриц. Выделение информационных зависимостей

Алгоритм Кэннона умножения матриц

Выделение информационных зависимостей

Отличие алгоритма Кэннона от метода Фокса состоит в изменении схемы начального распределения блоков перемножаемых матриц между подзадачами вычислительной системы. Начальное расположение блоков в алгоритме Кэннона подбирается таким образом, чтобы располагаемые блоки в подзадачах могли бы быть перемножены без каких-либо дополнительных передач данных. При этом подобное распределение блоков может быть организовано таким образом, что перемещение блоков между подзадачами в ходе вычислений может осуществляться с использованием более простых коммуникационных операций.

Масштабирование и распределение подзадач по процессорам

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

Анализ эффективности алгоритма Фокса

Далее после умножения матричных блоков процессоры передают свои блоки матрицы В предыдущим процессорам по столбцам процессорной решетки (первые процессоры столбцов передают свои данные последним процессорам в столбцах решетки). Эти операции могут быть выполнены процессорами параллельно и, тем самым, длительность такой коммуникационной операции составляет:

Просуммировав все полученные выражения, можно получить, что общее время выполнения алгоритма Фокса может быть определено при помощи следующих соотношений:

Источник

Участник:NataliaPolienko/Блочное умножение матриц по методу Кеннона

Содержание

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

1.2 Математическое описание алгоритма

Исходные и результирующая матрицы представляются в виде наборов блоков. Операцию матричного умножения матриц [math]A[/math] и [math]B[/math] в блочном виде можно представить следующим образом [2] : [math] \begin A_ <11>& A_ <12>& \cdots & A_ <1k>\\ A_ <21>& A_ <22>& \cdots & A_ <2k>\\ \vdots & \vdots & \ddots & \vdots \\ A_ & A_ & \cdots & A_ \end \begin B_ <11>& B_ <12>& \cdots & B_ <1k>\\ B_ <21>& B_ <22>& \cdots & B_ <2k>\\ \vdots & \vdots & \ddots & \vdots \\ B_ & B_ & \cdots & B_ \end = \begin C_ <11>& C_ <12>& \cdots & C_ <1k>\\ C_ <21>& C_ <22>& \cdots & C_ <2k>\\ \vdots & \vdots & \ddots & \vdots \\ C_ & C_ & \cdots & C_ \end, [/math]

где каждый блок [math]C_[/math] матрицы [math]C[/math] определяется в соответствии с выражением:

[math] \begin C_ = \sum_^ A_ B_, \quad i \in [1, k], \quad j \in [1, k]. \end [/math]

Полученные блоки [math]C_[/math] являются независимыми.

1.3 Вычислительное ядро алгоритма

[math] \begin C_ = \sum_^ A_ B_, \quad i \in [1, k], \quad j \in [1, k]. \end [/math]

1.4 Макроструктура алгоритма

Этап инициализации алгоритма Кеннона включает выполнение следующих операций передачи данных:

Операции на каждом последующем этапе:

1. Вычисляется произведение блоков каждым процессором в соответствии с описанным ранее ядром алгоритма [math](C_ = C_ + A_*B_)[/math] ;

2. Для каждой строки решетки блоки матрицы [math]A[/math] циклически сдвигаются на координату [math]i, j-1[/math] ;

3. Для каждого столбца решетки блоки матрицы [math]B[/math] циклически сдвигаются на координату [math]i-1, j[/math] ;

1.5 Схема реализации последовательного алгоритма

Алгоритм осуществляет последовательное вычисление блоков результирующей матрицы [math]C[/math] :

2. На одной итерации цикла по переменной [math]i[/math] используется первая строка, состоящая из блоков матрицы [math]A[/math] и все столбцы, состоящие из блоков матрицы [math]B[/math] :

[math] \begin C_ = \sum_^ A_ B_, \quad i \in [1, k], \quad j \in [1, k]. \end [/math]

1.6 Последовательная сложность алгоритма

Для перемножения матриц размера [math]n \times n[/math] в последовательной реализации алгоритма требуется [math]n^3[/math] умножений и сложений.

1.7 Информационный граф

Опишем граф алгоритма [3] как аналитически, так и в виде рисунка.

Естественно введённые координаты области таковы:

Аргументы операции следующие:

Источник

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

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

Содержание

Пример [ | ]

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

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

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

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

Операции [ | ]

Прямая сумма [ | ]

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

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

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

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

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

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

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

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

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

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

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

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

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

C i j = ∑ k = 1 n A i k × B k j <\displaystyle C_=\sum _^A_\times B_>

Формулы [ | ]

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

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

Источник