Previous Page  4 / 8 Next Page
Information
Show Menu
Previous Page 4 / 8 Next Page
Page Background

Использование форматов хранения разреженных матриц…

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

).

В отличие от массива, размерность связного списка не определена на мо-

мент инициализации, он может пополняться элементами в произвольном по-

рядке, в том числе возможна вставка элемента между двумя другими. Связный

список хорошо подходит к решению проблемы о сохранении индексов строк

ненулевых коэффициентов, так как на начало работы с сеткой полное число

ненулевых коэффициентов в строках матрицы неизвестно.