2 / 8
Использование форматов хранения разреженных матриц…
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2017. № 2
5
ленных по расчетной области узлов, объединенных в элементы. Распределение
узлов по элементам называют сеточной связностью. Сеточная связность определя-
ет портрет матрицы
,
K
т. е. множество пар индексов строк и столбцов ее ненуле-
вых коэффициентов [1]. Портрет матрицы
K
вычисляется так называемой проце-
дурой сборки. Во время исполнения сборки определяются матрицы коэффициен-
тов для отдельных элементов, которые затем суммируются в матрицу
K
по схеме,
однозначно задаваемой сеточной связностью. В настоящей работе рассмотрена
только часть процедуры сборки, связанная с определением портрета матрицы
.
K
По построению, только те коэффициенты
ij
K
являются ненулевыми, ин-
дексы (
i
,
j
) которых соответствуют узлам сетки, соединенным ребрами. По-
скольку каждый узел соединен лишь с несколькими другими узлами и общее
число связей между узлами пропорционально числу
,
n
а число коэффициентов
в матрице
K
равно
2
,
n
матрица
K
является разреженной, т. е. число ненулевых
коэффициентов
nz
N
на порядки меньше, чем нулевых.
Разреженную матрицу целесообразно хранить не в полной форме (массива
чисел размерностью
),
n n
а в некоторой структуре данных, которая макси-
мально использует разреженность для экономии памяти, и в то же время поз-
воляет использовать сохраненную матрицу так же, как если бы она оставалась в
полной форме.
К числу наиболее эффективных по затратам памяти и скорости использо-
вания в вычислениях форматам данных для хранения разреженных матриц от-
носится формат компактного хранения по столбцам
CCS
(
compressed column
storage
), предложенный в работе [2]. Формат
CCS
хранит только ненулевые ко-
эффициенты, их строковые индексы и
1
n
вспомогательных индексов. Прене-
брегая разностью байтов, отводимых на хранение в памяти компьютера целых
чисел и чисел с плавающей точкой, потребление памяти матрицей, сохраненной
в формате
CCS
, оценивается как
2
1.
nz
N n
Для формата
CCS
построены алго-
ритмы умножения матрицы на вектор и извлечения матричной диагонали, ра-
ботающие без «распаковки» матрицы в полную форму. Указанных алгоритмов
операций достаточно для реализации решения системы (1) методом сопряжен-
ных градиентов с диагональным предобуславливателем, когда матрица
K
сим-
метрична, и аналогичными методами, когда матрица
K
несимметрична [3].
По мнению автора настоящей работы, в программной реализации вычисле-
ний с форматом
CCS
[4] есть существенный изъян с точки зрения использова-
ния этой структуры данных для хранения и решения СЛАУ МКЭ. Предполага-
ется, что формат
CCS
инициализируется из матрицы, сохраненной в полной
форме. Подход, изложенный в данной работе, основан на наблюдении, что в
сеточной связности содержится достаточно информации для инициализации
формата
CCS
заранее с тем, чтобы во время сборки матрицы
K
сохранять ее
ненулевые коэффициенты прямо в формате
CCS
, исключив стадию инициали-
зации памяти для хранения матрицы
K
в полной форме. Последнее открывает
возможность решать сеточные задачи МКЭ большой размерности на обычных
компьютерах.