Способы хранения и представления разреженных матриц, операции над ними. Блатов И.А - 6 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

- 6 -
2.3. Строчный разреженный формат хранения симметричных
матриц
Для симметричной матрицы
{
}
n
ji
ij
aA
1, =
=
)(
jiij
aa
=
достаточно
хранить лишь ее диагональ и верхний (нижний) треугольник. При этом можно
указать два способа хранения:
1) строчное представление диагонали и верхнего (нижнего )
треугольника (РСФБД);
2) выделение диагональных элементов матрицы
A
в отдельный массив
AD
, а
разреженным форматом представляется только верхний (нижний)
треугольник матрицы
A
(причем в этом представлении диагональ считается
нулевой) (РСФД).
Задача 7. Записать симметричную матрицу
=
3011
0300
1010
1002
A
a) в РСФБД;
б) в РСФД.
a)
:
A
331112
б)
:
AN
11
:
JA
434241
:
JA
4
4
:
A
I
76531
:
IA
3
3
3
2
1
:
AD
3
3
1
2
2.4. Диагональная схема хранения (ДСХ) ленточных матриц
О п р е д е л е н и е 2.1. Квадратная матрица
{
}
n
ji
ij
aA
1, =
=
называется
)
1
2
(
+
m
–диагональной или ленточной, если
0
=
ij
a
для всех
j
i
,
таких, что
m
j
i
>
−
|
|
. Число
)
1
2
(
+
m
– это ширина ленты,
m
– полуширина.
Если
n
m
<<
, то такую матрицу следует рассматривать как разреженную .
Для хранения
)
1
2
(
+
m
–диагональной несимметричной матрицы
выделяется двумерный массив
))
1
(
(
+
×
m
n
AD
, а для симметричной –
))
1
(
(
+
×
m
n
. Столбцами этого массива являются ненулевые диагонали
матрицы
A
, которые хранятся , начиная с самой левой диагонали (самый левый
столбец) и кончая самой правой (самый правый столбец) следующим образом: 
                                              -6-

        2.3. Строчный разреженный формат хранения симметричных
             матриц
                                               A ={aij }i , j =1
                                                          n
       Для симметричной матрицы                                    (aij =a ji )   достаточно
хранить лишь ее диагональ и верхний (нижний) треугольник. При этом можно
указать два способа хранения:
1) строчное     представление    диагонали    и    верхнего     (нижнего)
   треугольника (РСФБД);
2) выделение диагональных элементов матрицы A в отдельный массив AD , а
   разреженным форматом представляется только верхний (нижний)
   треугольник матрицы A (причем в этом представлении диагональ считается
   нулевой) (РСФД).

       Задача 7.    Записать             симметричную                  матрицу


                                 � 2           0 0 1�
                                  �                        �
                                    � 0        1 0 1�
                             A =�
                                          0    0 3 0�
                                     ��                    ��
                                        � 1    1 0 3�
a) в РСФБД;
б) в РСФД.
a)   AN : 2 1 1 1 3 3                         б) AN : 1 1
     JA : 1 4 2 4 3 4                               JA : 4 4
     IA: 1 3 5 6 7                                   IA : 1 2 3 3 3
                                                    AD : 2 1 3 3

     2.4. Диагональная схема хранения (ДСХ) ленточных матриц
     О п р е д е л е н и е 2.1. Квадратная матрица A = aij             { }in, j =1 называется
(2m +1) –диагональной или ленточной, если aij =0 для всех i, j таких, что
| i − j |>m . Число (2m +1) – это ширина ленты, m – полуширина.
     Если m <

Страницы