Матричные операции.
Самыми распространенными формами хранения матриц являются стандартная построчечная форма хранения всех коэффициентов матрицы (DM), которая применяется для хранения плотных матриц, а также построчечная форма хранения ненулевых коэффициентов матрицы и их индексов (SM), которая применяется для хранения разреженных матриц.
Для организации эффективных рекурсивных параллельных матричных операций необходимо иметь соответствующий формат для хранения матриц.
Таким естественным форматом может служить формат кватернарного дерева (QT). Дерево строится следующим образом. Если порядок матрицы 2n, то она может быть разбита на четыре квадратных блока порядка 2n-1, которые также могут быть разбиты на четыре равных блока, и так – вплоть до элементов. Если блокам поставить в соответствие вершины, а ребрами соединить вершины, соответствующие блокам, с вершинами, соответствующими его подблокам, то в результате получим кватернарное дерево. Если некоторый блок нулевой, то соответствующее ему ребро в дереве отсутствует. Это обеспечивает эффективный способ хранения разреженных матриц (см. также [10 и [11]). Отметим, что при необходимости всякая матрица может быть дополнена до матрицы размера 2n, введением дополнительных нулевых или единичных элементов. Заметим, что обозначения QT, DM и SM происходят от названий: quaternary tree, density matrix и sparse matrix.
Если время вычисления суммы и произведения элементов матриц примерно одинаковые, то применение схемы умножения Штрассена не приводит к ускорению вычислений, если порядок матрицы менее 1287 (см. оценки в [12]). Поэтому в первую очередь были разработаны параллельные программы для стандартного алгоритма умножения матриц. При этом использовались две схемы – простая параллельная схема умножения и рекурсивная блочная схема умножения.
