Повышение эффективности алгоритмов арифметических операций над клеточными матрицами

АННОТАЦИЯ

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

ABSTRACT

The article deals with the problem of obtaining quantitative ratios of the number of elementary operations in the addition and multiplication of cell matrices with zero elements. The obtained relations give a possibility to assess the gain of considering zero elements of the matrices in the algorithms of arithmetical operations on matrices.

Ключевые слова: элементарные операции, матрицы, нулевые элементы, алгоритмы.

Keywords: elementary operations, matrices, zero elements, algorithms.

Арифметические операции над матрицами реализуются в ряде научно-технических направлений [2]: геометрическое моделирование, современная ускорительная техника, проектирование роботизированных систем, классификация бинарных отношений, численное решение дифференциальных уравнений, обработка сигналов и др. Операции над матрицами используются при математическом моделировании процессов, систем и явлений.

Обработка больших объемов данных повышает требования к времени нахождения  арифметических операций над матрицами. Часто время, затрачиваемое на выполнение расчетов с матрицами, является определяющим  фактором, от которого зависит общее время решения прикладной задачи в целом. Сокращение числа арифметических операций над матрицами, позволяет существенно сократить время реализующих их  алгоритмов на современных вычислительных средствах.

Матрицы высокого порядка, описывающие сложные системы, как правило, содержат определенное (часто значительное) число нулевых элементов. Учет нулевых элементов при составлении программ, выполняющих операции над матрицами высокого порядка приводит к увеличению быстродействия и уменьшению объема памяти, резервируемой процессором для выполнения программы. Ниже приводятся исходные соотношения для оценки эффективности одного из методов учета нулевых элементов  разбиения матриц на блоки (клетки).

     Рассмотрим две матрицы A=   и   B=[

одинакового типа. Пусть эти матрицы разбиты на клетки:

A= ;     B=  ,                           (1)

Если p=r  и q=s  и клетки   и  имеют одинаковый тип, то

A+B=  .                                       (2)

До разбиения на клетки, сложение матриц А и B требовало  =m n элементарных операций сложения. Определим, сколько таких операций потребуется с учетом клеточной структуры матриц.

Разобьем клетки на четыре вида: нулевые, все элементы которых равны нулю, обозначим Н; диагональные – Д; треугольные, элементы которых ниже (выше) главной диагонали равны нулю, обозначим Т; Полные матрицы, в которых не учитываются нулевые значения их элементов, обозначим П.

Элементы матрицы (2)        в зависимости от вида матриц    и    разобьем на четыре группы: 1 – Н+Н, Н+Д, Н+Т, Н+П; 2 – Д+Д; Д+Т; Д+П; 3 – Т+Т, Т+П; 4 – П+П.

Пусть размерность клетки  равна × .

Число элементарных сложений (вычитаний)   при определении элементов матрицы A + B в зависимости от группы равно:

1.    =0;    2. = ,( =);    3.  = ·.

Обозначим  множество пар индексов I, j элементов  матрицы 

A+B, принадлежащих i- ой группе. Тогда число элементарных сложений

( вычитаний) равно: -

 =+ + .                       (3)

Сравнивая величину  =m n с величиной  из (3), можно определить эффективность разбиения матриц А и В на клетки при их сложении.

Рассмотрим произведение матриц A=   и   B=[ , которые имеют структуру вида (1), причем в (1) q=r. Все клетки  и  таковы, что число столбцов клетки равно числу строк клетки , т.е. – типа× , а – типа ×.

Число элементарных умножений при перемножении матриц А и В без учета клеточной структуры равно = n·m·w, а число элементарных сложений =(n-1)·m·w.

Определим число элементарных умножений и сложений при вычислении одного элемента произведения с учетом клеточной структуры исходных матриц:

              · +  +·, (i =  k =  ).                 (4)

В зависимости от вида клеток  и  разобьем произведения клеток, входящих в (4), на четыре группы, аналогичные уже рассмотренным для случая сложения матриц: 1 - Н·Н, Н·Д, Н·Т,Н·П; 2 – Д·Д; Д·Т; Д·П; 3 – Т·Т, Т·П; 4 – П·П. Нетрудно видеть, что число элементарных сложений и умножений не зависит от перестановки клеток в произведении.

В зависимости от принадлежности произведения клеток в (4) к той или иной  i – ой группе, определим число элементарных сложений  и умножений :

1.    = 0, = 0;

2.  = 0,   =k·d;

3. (Т·Т) =  =  , при k=d=c;

(Т·Т) =  =  , при k=d=c;

(Т·П) =  =  , при c=k;

(Т·П) =  =  , при c=k;

4.  = (c-1)·k·d;  = c·k·d.

Обозначим через  – число произведений i - й группы в (4), тогда число элементарных умножений в (4) будет равно

               = ·,

а число сложений

                             = · + (q+1)·k·d.

Таким образом, вычисляя величины  и  для всех элементов результирующей матрицы произведения А и В, можно определить общее число элементарных сложений и умножений при учете клеточной структуры исходных матриц. Без учета клеточной структуры общее число элементарных умножений равно  = q·c·k·d , а сложений  = q·(c-1)·k·d + (q-1)·k·d. Сравнение числа элементарных операций до и после разбиения матриц на клетки может служить критерием эффективности этого метода.

Список литературы:
1. Демидович Б.П., Марон И.А. Основы вычислительной математики. –М.: Наука, 1970. – 664 с.
2. Зотолокин Ю.А., Ватутин Э.И., Титов В.С. Алгоритмическая оптимизация программной реализации алгоритмов умножения плотных вещественных матриц на графических процессорах с поддержкой технологии OpenGL // Известия Юго-Западного государственного университета. 2017. Т.21, №5(74). С.6-15.
3. Мальцев А.И. Основы линейной алгебры. – М.: Наука, 1975.-400 с.