Понятие оболочки матрицы. Профильный метод хранения разреженной матрицы

Несколько более сложной схемой использования разреженности является так называемый оболочечный, или профильный, способ. Оболочка , обозначаемая через , определяется как

.

То же самое можно записать посредством столбцовых индексов :

.

Величина называется профилем или размером оболочки . Справедлива формула:

.

На рис.3 оболочка матрицы выделена ломаной линией. Профиль матрицы в этом примере равен 11.

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

В схеме имеется основной массив , содержащий элементы оболочки из всех строк матрицы. Для указания начала отрезка каждой строки используется вспомогательный индексный вектор длины . Чтобы добиться единообразия при индексировании, полагают . Индексный вектор дает возможность удобного доступа к любому ненулевому элементу. Отображениена множество задается следующим образом:

.

Другими словами, значение элемента , принадлежащего профильной области , находится в . Рис.4 иллюстрирует эту схему хранения на примере.

Рис.4.

Основная память в даной схеме равна , а накладная .

Дата добавления: 2014-01-11