LEC-27 (Материалы к лекциям)

13

Лекция №27

11.2.2. Хранение симметричных ленточных матриц

Пусть А - симметричная положительно определенная матрица порядка N с элементами a_{i j} . Для i -ой строки А , i=1,2,..., N положим:

f_i(A)=minj , a_{i j} 0 и _i(A)=i- f_i (A).

Число f_i(A) - это столбцовый индекс первого ненулевого элемента i-ой строки А. Так как диагональные элементы a_ii - положительны, имеем:

f_i(A)  i _i(A) 0.

Согласно Катхиллу и Макки определим ширину ленты А как:

 (A)=max _i(A) , 1  i  N = max  i-j  , a_{i j} 0

Число _i(A) называется i -ой шириной ленты. Ленту определяем таким образом:

Band(А)=i,j , 0<i-j(A) т.е. как область матрицы, удаленную от главной диагонали не более, чем на  (А) позиций.

Поскольку А симметрична в последней формуле используются неупорядоченные пары i,j.

Эта матрица имеет ширину ленты, равную 3. Матрицы с шириной ленты, равной единице называются трехдиагональными.

Понятие оболочки (профиля)

Оболочка матрицы А, обозначаемая через Env(A) определяется как :

Env(A)= )=i,j, 0 < i-j   _i (A)

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

Env(A)=i,j, f_i(A)  j< i 

Справедлива формула: Env(A)=

Схемы хранения симметричных матриц

Диагональная схема хранения

Распространенным методом хранения симметричной матрицы А является так называемая диагональная схема хранения (Мартин 1971г)

Поддиагонали нижнего треугольника А, составляющие Band (A), вместе с главной диагональю хранятся по строкам в прямоугольном массиве с размерами N( (A)+1)

Такая схема хранения очень проста и вполне эффективна, если _i(A) не слишком меняется с изменением i.

Профильная схема хранения (схема Дженнингса 1966г)

Хранение производится с помощью двух массивов:

VE - значений ненулевых элементов,

PD - положений диагональных элементов в массиве VE.

Для каждой строки в VE хранится крайний левый ненулевой элемент и все следующие элементы, расположенные справа от него вплоть до диагонального включительно. Поэтому i-я строка матрицы А требует _i+1 ячеек для хранения и VE будет состоять из элементов. Добавляя N элементов, необходимых для PD, получим общее количество в ячеек для хранения А. Если лента является полной, т.е. a_{i j}0 для всех i-j  _i при i>j, то

и требуемый объем памяти будет составлять ячеек.

Для ранее рассмотренной матрицы:

Элемент матрицы a_{i j} исходной матрицы может быть восстановлен по этой схеме следующим образом. Положение a_{i j} в VE определяется значением PD(i)-(i-j), если только PD(i)-(i-j)> PD(i-1). Последнее условие означает, что a_ij не будет лежать влево от первого ненулевого элемента i-ой строки, иначе a_{i j} =0 и не хранится в VE.

Например, чтобы найти элемент a₅₃ в массиве VE вычисляем

PD(5)-(5-3)=11-2=9>(PD(4)=8) и следовательно a₅₃ хранится в VE(9).

Ещё примеры:

a₅₁ : PD(5)-(5-1)=11-4=7 < PD(4), следовательно a₅₁ = 0

a₄₂ : PD(4)-(4-2)=8-2=6 > PD(3), следовательно a₄₂ = PD(6)

a₃₁ : PD(3)-(3-1)=4-2=2 < PD(2), следовательно a₃₁ = 0

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

Модификация профильной схемы хранения

Рассмотрим модификацию этой схемы, в которой дополнительные элементы хранятся отдельным вектором.