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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

- 20 -
)
(
n
JA
j
=
)
1
(
)
(
+
=
i
IB
i
IB
нет да
для 1)1(),( −+= jIBjBIm
)
(
m
k
=
(
)
ikY
=
нет да
(
)
ikY
=
;
knJC
j
=
)(
;
1
+
=
jj
nn
j
niIC
=
+
)1(
;
1
+
=
i
i
2. Численный этап – определяется вектор
CN
. Основная идея –
умножение с помощью РВН, размерность которого равна числу столбцов
матрицы
C
(т.е .
l
), поэтому матрица
C
будет записываться по строкам .
Пример. Найти произведение двух матриц
2221
1211
2221
1211
bb
bb
aa
aa
.
Р е ш е н и е
Накопитель
()
0,0
21
xx
– начальный момент . Берем первый элемент текущей
строки матрицы
A
и умножаем его на все элементы соответствующей строки
матрицы
B
и т.д.:
.,;,
;,;0,0
2
12
1
11
22
12
2
2
21
12
1
1
12112211111121
xcxcbaxxbaxx
baxxbaxxxx
==+=+=
+
=
+
=
=
=
Рассмотрим численный этап в общем случае .
0
1
.
1
=
i
.
0
2
. С помощью
IC
определяем, в каких позициях
JC
находится описание
i
-й
строки матрицы
C
.
0
3
. Просматриваем участок
JC
, соответствующий описанию
i
-й строки , и в
позиции РВН
X
с номерами столбцовых индексов
i
-й строки этого участка
засылаем нули.
0
4
. С помощью
IA
определяем, в каком участке
JA
содержится описание
i
-й строки матрицы
A
.
0
5
. Просматриваем выделенный участок (
i
-ю строку) массива
JA
. Для
каждого просматриваемого элемента
k
, стоящего в
m
-й позиции массива
JA
,
выполняем следующие операции: 
                                           - 20 -

                                j =JA(n)
                          IB(i ) =IB (i +1)
                         нет                да
            для     m =I B ( j ), IB( j +1) −1
                       k =JB(m)
                       Y (k ) =i
                  нет                 да
     Y (k ) =i ; JC (n j ) =k ; n j =n j +1
     IC (i +1) =n j ; i =i +1

    2. Численный этап – определяется вектор CN . Основная идея –
умножение с помощью РВН, размерность которого равна числу столбцов
матрицы C (т.е. l ), поэтому матрица C будет записываться по строкам.

                                                    � a11   a12 � � b11 b12 �
     Пример. Найти произведение двух матриц ��                    ��             � .
                                               � a21        a22 �� �� b21 b22 ��
                               Решение
                        x1 x2
       Накопитель               – начальный момент. Берем первый элемент текущей
                     (0, 0)
строки матрицы A и умножаем его на все элементы соответствующей строки
матрицы B и т.д.:

     x1 =0, x2 =0 ; x1 =x1 +a11b11 , x2 =x2 +a11b12 ;
                         x1 =x1 +a12 b21 , x2 =x2 +a12b22 ; c11 =x1 , c12 =x2 .

     Рассмотрим численный этап в общем случае.
1 . i =1.
 0

2 0 . С помощью IC определяем, в каких позициях JC находится описание i -й
строки матрицы C .
30 . Просматриваем участок JC , соответствующий описанию i -й строки, и в
позиции РВН X с номерами столбцовых индексов i -й строки этого участка
засылаем нули.
4 0 . С помощью IA определяем, в каком участке JA содержится описание
i -й строки матрицы A .
50 . Просматриваем выделенный участок ( i -ю строку) массива JA . Для
каждого просматриваемого элемента k , стоящего в m -й позиции массива JA ,
выполняем следующие операции:

Страницы