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

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

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

Аналогично, для включения в список записей новых ненулевых элементов используются свободные записи, расположенные в начале списка свободных записей.

Предположим, что свободными являются две записи с начальными адресами 101 и 201, и мы хотим добавить к списку еще одну свободную запись с начальным адресом 301. Если ячейка 50 содержит адрес первой свободной записи, то требуемые изменения в содержании ячеек памяти могут быть представлены следующей таблицей:

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

10.2.2. Схемы, не использующие непосредственную адресацию (алгоритмические способы хранения разреженных матриц).

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

Схемы хранения для матриц общего вида

Пусть дана матрица А₅ общего вида с ненулевыми элементами.

a₂₁ , a₄₁ , a₅₂ , a₁₃ , a_{33 ,} а₂₄, a₄₅

В последующих трех схемах матрицы хранятся по столбцам.

Схема 1

Каждому ненулевому элементу матрицы соответствует запись, занимающая две ячейки памяти. Первая ячейка содержит номер строки, вторая - значение элемента. Нуль в первой ячейке означает конец данного столбца. Нули в обеих ячейках указываются на конец массива, хранящего матрицу. Таким образом, общее число записей равно n+  +1, из них n - для столбцов,  - для ненулевых элементов матрицы А и одна запись - для указания конца матрицы. Так как каждая запись использует две ячейки памяти, то для хранения матрицы А потребуется 2(n++1), ячеек. Матрица А₅, для которой =7 и n=5 будет храниться в виде массива.

0, 1, 2, a₂₁ , 4, a₄₁ , 0, 2, 5, a_52, 0, 3, 1, a₁₃ , 3, a₃₃ ,0, 4, 2, a₂₄, 0, 5, 4, a₄₅, 0, 0

Схема 2.

Информация о данной матрице хранится в трех массивах:

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

RI - индексов строк

и CIP -указателей индексов столбцов.

Элемент RI() (- элемент массива RI) - cодержит индекс строки -го элемента VE - VE( ). Если первый ненулевой элемент  - го столбца данной матрицы размещается в VE (t_), то t_ хранится в  -м элементе CIP, т.е.

CIP( )= t_. Очевидно, VE и RI состоят из  элементов, а CIP из n элементов. Следовательно, эта схема требует общее число в 2+n ячеек.

Матрица А₅ будет храниться следующим образом:

VE=( a₂₁ , a₄₁ , a_52, a₁₃ , a₃₃, a₂₄, a₄₅ )

RI=(2, 4, 5, 1, 3, 2, 4)

CIP=(1, 3, 4, 6,7) (Указатель индекса столбцов)

Вышеизложенной схемой легко пользоваться. Например, a₃₃ может быть найдено следующим образом. Так как CIP(3)=4, RI(4)) даст индекс строки первого ненулевого элемента третьего столбца.

Если a₃₃0, RI(4) или один из следующих за ним элементов RI, предшествующих первому ненулевому элементу четвертого столбца, должен быть равен 3. В нашем случае RI(5) =3, так как VE(5) cодержит a₃₃.

Схема 3.

Каждому ненулевому элементу данной матрицы однозначно ставится в соответствие целое число (i,j) вида:

(i,j)=i+(j-1)n a_ij0

Хранение ненулевых элементов обеспечивается двумя массивами:

VE- значений ненулевых элементов и LD , в каждом из которых содержится  элементов. (Память, понятно, потребуется 2 ячеек)

В LD() находится (i,j), соответствующее a_ij из VE(), где  =1, 2, ...,  .

Матрица А₅ хранится в виде:

VE=( a₂₁ , a_41, a₅₂ , a₁₃, a₃₃, a_24, a₄₅)

LD=(2, 4, 10, 11, 13, 17, 24)

Исходная матрица может быть восстановлена по этой схеме хранения следующим образом. В соответствии с данным выше определением (i,j) является очевидным, что j есть наименьшее целое число, большее ли равное и i= (i,j)-(j-1)n.

Например, если (i,j)=LD.(5)=13, тогда и наименьшее целое число, большее или равное будет 3.

Следовательно: j=3 и i=2(i,j)-(j-1)n=13-10=3.

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

Пусть А - симметричная положительно определенная матрица порядка 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) определяется как :

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

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