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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

- 19 -
:
2
=
i
23
7
3
2
)
1
(
=
⋅
+
=
C
:
3
=
i
38
3
5
23
)
1
(
=
⋅
+
=
C
2
=
k
;
0
)
2
(
=
С
;
)
2
(
)
3
(
≠
8
,...,
4
=
i
:
4
=
i
:
42
6
7
0
)
2
(
=
⋅
+
=
C
. . . . . . . . . . . . . . . . . . . . . . . . .
3.7. Умножение РМ
На входе заданы РМ
)
(
),
(
l
m
B
m
n
A
×
×
в неупорядоченном РСФ . На
выходе должны получить матрицу
AB
C
=
в РСФ .
Частным случаем является умножение РМ на РВ , когда результат –- РВ .
Алгоритм
1. Символический этап – определение векторов
IC
JC
,
. Для него
потребуется ЦМП
Y
, размерность которого равна
l
. Начальное состояние
Y
– нулевое .
0
1
.
1
=
i
.
1
)
1
(
=
IC
.
0
2
. Просматриваем по порядку столбцовые индексы элементов
i
-й строки в
массиве
JA
. Для каждого просматриваемого индекса
j
в массиве
столбцовых индексов
JB
просматриваем содержимое
j
-й строки. При этом
для каждого ненулевого элемент
j
-й строки выполним следующие операции.
Пусть просматриваемый индекс равен
k
. Если
k
-я позиция массива
переключателей не “включена”, то “включаем” её и помещаем индекс
k
в
первую свободную позицию массива
JC
. Если позиция уже “включена”, то
переходим к просмотру следующего элемента вектора
JB
, ничего не добавляя
к
JC
.
0
3
. После окончания просмотра
i
-й строки матрицы
А
компоненте вектора
(
)
1
+
iIC присваиваем порядковый номер первой свободной позиции
JC
.
0
4
.
1
+
=
i
i
и идем на
0
2
. Значение ПП
p
увеличиваем на единицу.
Алгоритм
(
)
(
)
(
)
021
=
=
=
=
lYYY K
1
=
i
:
1
)
1
(
=
IC
1
=
j
n
(
N
элемента в
JC
)
)
1
(
)
(
+
=
i
i
нет да
1
+
=
i
i
1)1(),( −+= iIAiAIn : 
                                     - 19 -

               i =2 :   C (1) =2 +3 ⋅ 7 =23
               i =3 :   C (1) =23 +5 ⋅ 3 =38
  k =2 ; С (2) =0 ;     IA(3) ≠IA(2)
  i =4,...,8 :
               i =4 :   C (2) =0 +7 ⋅ 6 =42
  . . . . . . . . . . . . . . . . . . . . . . . . .

    3.7. Умножение РМ
    На входе заданы РМ A(n ×m), B(m ×l ) в неупорядоченном РСФ. На
выходе должны получить матрицу C =AB в РСФ.
  Частным случаем является умножение РМ на РВ, когда результат –- РВ.
                        Алгоритм
   1. Символический этап – определение векторов JC, IC . Для него
потребуется ЦМП Y , размерность которого равна l . Начальное состояние Y
– нулевое.
10 . i =1. IC (1) =1 .
2 0 . Просматриваем по порядку столбцовые индексы элементов i -й строки в
массиве JA . Для каждого просматриваемого индекса          j в массиве
столбцовых индексов JB просматриваем содержимое j -й строки. При этом
для каждого ненулевого элемент j -й строки выполним следующие операции.
Пусть просматриваемый индекс равен k . Если k -я позиция массива
переключателей не “включена”, то “включаем” её и помещаем индекс k в
первую свободную позицию массива JC . Если позиция уже “включена”, то
переходим к просмотру следующего элемента вектора JB , ничего не добавляя
к JC .
30 . После окончания просмотра i -й строки матрицы А компоненте вектора
IC (i +1) присваиваем порядковый номер первой свободной позиции JC .
4 0 . i =i +1 и идем на 2 0 . Значение ПП p увеличиваем на единицу.
                           Алгоритм
  Y (1) =Y (2 ) = =Y (l ) =0
  i =1: IC (1) =1
        n j =1    ( N элемента в JC )
                     IA(i ) =IA(i +1)
            нет                       да
                               i =i +1
  n =I A(i ), IA(i +1) −1 :

Страницы