Блочные матрицы и кронекеровские произведение и сумма матриц
Блочные (клеточные) матрицы и операции над ними
Пример 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
где каждый блок [math]C_
[math] \begin
Полученные блоки [math]C_
1.3 Вычислительное ядро алгоритма
[math] \begin
1.4 Макроструктура алгоритма
Этап инициализации алгоритма Кеннона включает выполнение следующих операций передачи данных:
Операции на каждом последующем этапе:
1. Вычисляется произведение блоков каждым процессором в соответствии с описанным ранее ядром алгоритма [math](C_
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
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_
Формулы [ | ]
Формула Фробениуса [ | ]
Для обращения невырожденной блочной матрицы может использоваться формула Фробениуса:
