4 / 8
Использование форматов хранения разреженных матриц…
ISSN 1812-3368. Вестник МГТУ им. Н.Э. Баумана. Сер. Естественные науки. 2017. № 2
7
полное число ненулевых элементов для каждого столбца или строки заранее не-
известно.
Для предварительного вычисления портрета матрицы предложено применять
вспомогательную структуру данных, использующую связные списки для хранения
строковых индексов ненулевых коэффициентов матрицы
.
K
Число связных спис-
ков равно числу столбцов. Связные списки соотнесены со столбцами матрицы в
полной форме в порядке перечисления. Каждый связный список содержит индек-
сы строк ненулевых коэффициентов своего столбца, упорядоченные по возраста-
нию. Пример такой структуры для матрицы (2) приведен ниже (для наглядности
матрица дополнена первой строкой с номерами столбцов):
1 2 3 4 5 6 7 8
1 1 2 1 2 3 4 5
2 2 3 4 4 5 7 7
4 3 6 5 5 6 8 8 .
5 7 6
8
Вспомогательная структура заполняется обходом таблицы сеточной связно-
сти по тому же алгоритму, который используется при построении матрицы
K
, с
тем различием, что ненулевые коэффициенты не вычисляют, а определяют
только их индексы. Для ее формирования традиционная реализация алгоритма
добавления элементов в связный список дополняется с учетом указанных выше
особенностей [5]. Учитывается, что индекс ненулевого коэффициента должен
содержаться в списке только один раз, и что добавленные в список индексы
должны быть отсортированы по возрастанию.
Далее приведены алгоритмы формирования и использования описанной
структуры.
Алгоритм решения задачи.
Алгоритмы выполняют в псевдокоде в том сти-
ле, который задан в работе [5]. Выбранный стиль псевдокода позволяет абстра-
гироваться от специфики конкретного языка программирования. Единствен-
ным безусловным требованием к языку программирования для реализации
проводимых ниже алгоритмов является поддержка работы с указателями, что
необходимо для реализации связного списка, либо наличия в языке встроенных
структур данных, сочетающих упорядоченное индексированное хранение дан-
ных с возможностью произвольной вставки по индексу (например, контейнер
list()
в языке
Python
).
В отличие от массива, размерность связного списка не определена на мо-
мент инициализации, он может пополняться элементами в произвольном по-
рядке, в том числе возможна вставка элемента между двумя другими. Связный
список хорошо подходит к решению проблемы о сохранении индексов строк
ненулевых коэффициентов, так как на начало работы с сеткой полное число
ненулевых коэффициентов в строках матрицы неизвестно.