ВУЗ:
Составители:
5
Разреженные формы LU-разложения
5.1 Упакованные формы хранения матриц
Для решения систем линейных алгебраических уравнений с разрежен-
ными матрицами используются те же самые методы гауссова исключения,
что и для линейных систем с заполненными матрицами. Отличие состоит
только в выборе главного элемента и в способе хранения матрицы коэффи-
циентов сист емы уравнений [10].
Так как разреженные матрицы име ют небольшое число ненулевых эле-
ментов, в целях экономии оперативной памяти ЭВМ такие матрицы хранят
в упакованном виде. Рассмотрим четыре наиболее употребимых способа упа-
ковки, используемых для хранения произвольных разреженных матриц.
Пример 5.1. В качестве примера возьмем квадратную м а т рицу A
порядка 6 с тринадцатью ненулевыми элементами: a
11
= 1, a
13
= 3, a
14
= −2,
a
21
= 1, a
25
= 5, a
33
= 7, a
34
= 2, a
42
= −3, a
46
= −1, a
51
= 1, a
54
= 3, a
65
= 2,
a
66
= 2.
В излагаемых ниже схемах хранения разреженной матрицы A упаковка
осуществляется по строкам.
Схема 1. Каждому ненулевому элементу матрицы A ставится в соо т -
ветствие запись, состоящая из двух полей. Первое поле записи содержит
номер столбца, а второе — значение эле м ента. Нуль во вт о ром поле озна-
чает начало новой строки. В этом случае первое поле содержит номер новой
строки. Нули в обоих полях записи указывают на конец массива, хранящего
данную разреженную матрицу A. В соответствии с этой схемой матрица A
примера 5.1 будет храниться в виде с ле дующе го массива:
Страницы
- « первая
- ‹ предыдущая
- …
- 80
- 81
- 82
- 83
- 84
- …
- следующая ›
- последняя »
