Алгоритм Фокса умножения матриц: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
(Полностью удалено содержимое страницы)
 
(не показано 7 промежуточных версий этого же участника)
Строка 1: Строка 1:
  
= Свойства и структура алгоритмов =
 
== Общее описание алгоритма ==
 
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти.
 
 
 
== Математическое описание алгоритма ==
 
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).
 
 
Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).
 
 
При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
 
:<math>
 
\begin{align}
 
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
 
\end{align}
 
</math>
 
 
 
== Вычислительное ядро алгоритма ==
 
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
 
:<math>
 
\begin{align}
 
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
 
\end{align}
 
</math>
 
 
== Макроструктура алгоритма ==
 
 
Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
 
:<math>
 
\begin{align}
 
\sum_{k = 1}^{n} a_{ik} b_{kj}
 
\end{align}
 
</math>
 
 
 
== Схема реализации последовательного алгоритма ==
 
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
 
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
 
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.
 
 
:<math>
 
\begin{align}
 
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
 
\end{align}
 
</math>
 
 
После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.
 
 
== Последовательная сложность алгоритма ==
 
 
== Информационный граф ==
 
 
== Ресурс параллелизма алгоритма ==
 
 
== Входные и выходные данные алгоритма ==
 
 
= Программная реализация алгоритма =
 
 
= Литература =
 
<references />
 
1. Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016
 
 
2. Гергель В. П. Теория и практика параллельных вычислений: учебное пособие, ИНТУИТ, 2007
 

Текущая версия на 22:29, 23 октября 2017