6CAD-CAE-22 Хранение матриц (1014141), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

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 без перемещений всех следующих за ними элементов.

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

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

В схеме имеется основной массив ENV, содержащий элементы профиля (кроме диагональных) из всех строк матрицы. Для указания начала отрезка каждой строки используется вспомогательный индексный вектор XENV длины N+1. Чтобы добиться единообразия при индексировании, полагаем XENV (N+1) равным ENV (А)+1. Индексный вектор XENV дает возможность удобного доступа к любому ненулевому элементу. Отображение ENV(А) на множество 1,2,... ,ENV (А) задается таким образом: i,jXENV( i+1)-( i-j )

Другими словами, значение недиагонального элемента a_ij находится в ENV(XENV(i+1)-(i-j))

Пусть, например, нужно найти значение элемента a₂₁.

Имеем: XENV( 2+1)-(2-1)=2-1=1 поэтому a₂₁ хранится в ENV(1). Но попытка найти элемент a₃₂ приведет к тому же результату, что говорит о необходимости какого-то дополнения к алгоритму.

Чаще всего используемой операцией является выделение профильного отрезка какой-либо строки. Это удобно делать, пользуясь следующим фрагментом для поиска элементов a_ij:

J1=XENV(I); J2=XENV(I+1)-1

IF(J2.LT. J1) GO TO 200

Характеристики

Список файлов лекций