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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

- 4 -
Таким образом, описание
i
-й строки матрицы
A
хранится в позициях с
)
(
i
A
I
до
]
1
)
1
(
[
−
+
i
A
I
массивов
AN
и
за исключением равенства
I
)
(
)
1
(
i
A
I
i
A
I
=
+
, означающего , что
i
-я строка пуста. Следовательно ,
элементы записываются в массив по порядку следования строк. Если
A
имеет
m
строк , то массив
A
I
содержит
)
1
(
+
m
позицию .
Данный способ представления называют полным, т.к. представлена вся
матрица
A
.
В зависимости от того , как записываются в каждой строке столбцовые
индексы в массиве
(по порядку возрастания или нет), различают
упорядоченное или неупорядоченное представление соответственно .
Неупорядоченные представления нужны для алгоритмических удобств:
результаты большинства матричных операций получаются неупорядоченными,
и упорядочение их требует дополнительных затрат машинного времени , в то
время как большинство алгоритмов для РМ не требует, чтобы представления
были упорядоченными.
З а м е ч а н и е . Всюду в дальнейшем мы будем иметь дело с
вещественными матрицами.
Задача 1. Написать для матрицы A упорядоченное представление в РСФ .
N
столбцов : 7654321
=
0000000
0630000
0000504
0002011
A .
N
позиций: 87654321
6
3
5
4
2
1
1
:
AN
6
5
3
1
4
2
1
:
8
8
6
4
1
:
A
I
З а м е ч а н и е . В первой позиции массива
A
I
всегда стоит 1 .
Задача 2. По массивам
IA
AN
,
,
восстановить матрицу
A
(с
точностью до нулевых столбцов справа).
9
8
5
4
3
2
1
:
AN
5
4
3
2
1
7
6
:
8
6
5
3
1
:
A
I
                                         -4-

        Таким образом, описание i -й строки матрицы A хранится в позициях с
I A(i ) до [ I A(i +1) −1] массивов AN и JA за исключением равенства
I I A(i +1) =I A(i ) , означающего, что i -я строка пуста. Следовательно,
элементы записываются в массив по порядку следования строк. Если A имеет
m строк , то массив I A содержит (m +1) позицию.
        Данный способ представления называют полным, т.к. представлена вся
матрица A .
        В зависимости от того, как записываются в каждой строке столбцовые
индексы в массиве JA (по порядку возрастания или нет), различают
упорядоченное или неупорядоченное представление соответственно.
        Неупорядоченные представления нужны для алгоритмических удобств:
результаты большинства матричных операций получаются неупорядоченными,
и упорядочение их требует дополнительных затрат машинного времени, в то
время как большинство алгоритмов для РМ не требует, чтобы представления
были упорядоченными.
        З а м е ч а н и е. Всюду в дальнейшем мы будем иметь дело с
вещественными матрицами.

     Задача 1. Написать для матрицы A упорядоченное представление в РСФ.
       N столбцов :          1 2 3 4 5 6 7
                           � 1          1 0 2 0 0 0�
                            �                         �
                              � 4       0 5 0 0 0 0�
                       A =�                               .
                                    0   0 0 0 3 6 0�
                               ��                     �
                                  � 0   0 0 0 0 0 0 ��

  N позиций:   1   2   3    4      5 6 7 8
        AN :   1   1   2    4      5 3 6
        JA :   1   2   4    1      3 5 6
        IA:    1   4   6    8      8

     З а м е ч а н и е. В первой позиции массива I A всегда стоит 1 .

     Задача 2. По массивам      AN , JA, IA       восстановить матрицу A (с
  точностью до нулевых столбцов справа).

   AN : 1 2 3 4 5 8 9
   JA : 6 7 1 2 3 4 5
   IA: 1 3 5 6 8

Страницы