Новые клеточные методы умножения матриц
Запропоновано два нових клітинних методи множення матриць, які дозволяють отримати клітинні аналоги відомих алгоритмів матричного множення зі зменшеною обчислювальною складністю, порівняно з аналогами, отриманими на основі відомих клітинних методів множення матриць. Новий швидкий клітинний метод доз...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2013 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/86161 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Новые клеточные методы умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2013. — Т. 49, № 1. — С. 19-29. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859589736010612736 |
|---|---|
| author | Елфимова, Л.Д. |
| author_facet | Елфимова, Л.Д. |
| citation_txt | Новые клеточные методы умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2013. — Т. 49, № 1. — С. 19-29. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано два нових клітинних методи множення матриць, які дозволяють отримати клітинні аналоги відомих алгоритмів матричного множення зі зменшеною обчислювальною складністю, порівняно з аналогами, отриманими на основі відомих клітинних методів множення матриць. Новий швидкий клітинний метод дозволяє мінімізувати на 15% мультиплікативну, адитивну і загальну складність відомих алгоритмів матричного множення. Новий змішаний клітинний метод поєднує метод Лейдермана із запропонованим швидким клітинним методом, що призводить до мінімізації на 28% мультиплікативної, адитивної і загальної складності зазначених алгоритмів. Оцінки обчислювальної складності цих методів подано на прикладі отримання клітинних аналогів традиційного алгоритму множення матриць.
The paper proposes two new cellular methods of matrix multiplication, which allow obtaining cellular analogs of the well-known matrix multiplication algorithms with reduced computational complexity, as compared with the analogs derived on the basis of the well-known cellular methods of matrix multiplication. The new fast cellular method reduces by 15% the multiplicative, additive, and overall complexities of the mentioned algorithms. The new mixed cellular method combines the Laderman method with the proposed fast cellular method. The interaction of these methods reduces by 28% the multiplicative, additive, and overall complexities of the matrix multiplication algorithms. The computational complexity of these methods are estimated using the model of getting cellular analogs of the traditional matrix multiplication algorithm.
|
| first_indexed | 2025-11-27T13:52:35Z |
| format | Article |
| fulltext |
ÓÄÊ 681.322.012
Ë.Ä. ÅËÔÈÌÎÂÀ
ÍÎÂÛÅ ÊËÅÒÎ×ÍÛÅ ÌÅÒÎÄÛ ÓÌÍÎÆÅÍÈß ÌÀÒÐÈÖ
Êëþ÷åâûå ñëîâà: ëèíåéíàÿ àëãåáðà, êëåòî÷íûå ìåòîäû óìíîæåíèÿ ìàòðèö,
áûñòðûå ãèáðèäíûå àëãîðèòìû ìàòðè÷íîãî óìíîæåíèÿ, àëãîðèòì Ëåéäåðìàíà.
 íàñòîÿùåå âðåìÿ äëÿ ÷èñëåííûõ ìåòîäîâ ëèíåéíîé àëãåáðû ðàçðàáîòàíû èõ
êëåòî÷íûå àíàëîãè [1], îáåñïå÷èâàþùèå âîçìîæíîñòü áûñòðîãî ðåøåíèÿ çàäà÷
ïðîèçâîëüíûõ ðàçìåðîâ íà ðàçëè÷íûõ âû÷èñëèòåëüíûõ ñèñòåìàõ è ñîçäàíèÿ
ýôôåêòèâíîãî ïðîãðàììíîãî îáåñïå÷åíèÿ äëÿ òàêèõ ñèñòåì.  ðàáîòàõ [2, 3]
âïåðâûå ïðåäñòàâëåíû áûñòðûé è ñìåøàííûé êëåòî÷íûå ìåòîäû óìíîæåíèÿ
äâóõ ( )n n� -ìàòðèö, íà îñíîâå êîòîðûõ ïîëó÷åíû êëåòî÷íûå àíàëîãè èçâåñòíûõ
àëãîðèòìîâ ìàòðè÷íîãî óìíîæåíèÿ ñ ìèíèìèçèðîâàííîé âû÷èñëèòåëüíîé ñëîæ-
íîñòüþ. Áûñòðûé êëåòî÷íûé ìåòîä [2] îáåñïå÷èâàåò ìèíèìèçàöèþ ìóëüòèïëèêà-
òèâíîé, àääèòèâíîé è îáùåé ñëîæíîñòåé óêàçàííûõ àëãîðèòìîâ íà 12,5 %. Ñìå-
øàííûé êëåòî÷íûé ìåòîä [3] cî÷åòàåò ðåêóðñèâíûé ìåòîä Øòðàññåíà [4] äëÿ
óìíîæåíèÿ ( )n n� -ìàòðèö ñ áûñòðûì êëåòî÷íûì ìåòîäîì, âçàèìîäåéñòâèå êîòî-
ðûõ ïðèâîäèò ê ïîëó÷åíèþ êëåòî÷íûõ àíàëîãîâ èçâåñòíûõ àëãîðèòìîâ ìàòðè÷-
íîãî óìíîæåíèÿ ñ ìèíèìèçèðîâàííûìè íà 25 % ìóëüòèïëèêàòèâíîé, àääèòèâ-
íîé è îáùåé ñëîæíîñòÿìè. Äàííûå ìåòîäû èìåþò ìåñòî ïðè n , êðàòíûõ 2.
Äëÿ îïòèìèçàöèè âû÷èñëèòåëüíîé ñëîæíîñòè êëåòî÷íûõ àíàëîãîâ èçâåñò-
íûõ àëãîðèòìîâ óìíîæåíèÿ ìàòðèö, ïîëó÷åííûõ íà îñíîâå ìåòîäîâ [2, 3], â íà-
ñòîÿùåé ñòàòüå ðàññìîòðåíû äâà íîâûõ êëåòî÷íûõ ìåòîäà óìíîæåíèÿ ( )n n� -ìàò-
ðèö, èñïîëüçóþùèõ èñõîäíûå ìàòðèöû íå òîëüêî ÷åòíîãî, íî è íå÷åòíîãî ïîðÿä-
êà. Íîâûé áûñòðûé êëåòî÷íûé ìåòîä äàåò âîçìîæíîñòü ïîëó÷èòü êëåòî÷íûå
àíàëîãè óêàçàííûõ àëãîðèòìîâ ñ ìèíèìèçèðîâàííûìè íà 15 % ìóëüòèïëèêàòèâ-
íîé, àääèòèâíîé è îáùåé ñëîæíîñòÿìè. Íîâûé ñìåøàííûé êëåòî÷íûé ìåòîä ñî-
÷åòàåò ðåêóðñèâíûé ìåòîä Ëåéäåðìàíà [5] äëÿ óìíîæåíèÿ ( )n n� -ìàòðèö ñ ïðåä-
ëîæåííûì äàëåå áûñòðûì êëåòî÷íûì ìåòîäîì, âçàèìîäåéñòâèå êîòîðûõ ïðèâî-
äèò ê ïîëó÷åíèþ êëåòî÷íûõ àíàëîãîâ èçâåñòíûõ àëãîðèòìîâ ìàòðè÷íîãî
óìíîæåíèÿ ñ ìèíèìèçèðîâàííûìè íà 28 % ìóëüòèïëèêàòèâíîé, àääèòèâíîé è
îáùåé ñëîæíîñòÿìè. Ïðåäëàãàåìûå ìåòîäû èìåþò ìåñòî ïðè n , êðàòíûõ 3.
Îöåíêè âû÷èñëèòåëüíîé ñëîæíîñòè ýòèõ ìåòîäîâ äàíû íà ïðèìåðå ïîëó÷åíèÿ
êëåòî÷íûõ àíàëîãîâ òðàäèöèîííîãî àëãîðèòìà óìíîæåíèÿ ìàòðèö [6].
Íîâûé áûñòðûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö. Îñíîâîé äëÿ ïî-
ñòðîåíèÿ äàííîãî ìåòîäà ÿâëÿåòñÿ îïèñàííûé â [7] áûñòðûé ãèáðèäíûé àëãîðèòì
óìíîæåíèÿ äâóõ ÷èñëîâûõ ìàòðèö, êîòîðûé äîïóñêàåò ïåðåõîä ê êðóïíîìàñøòàá-
íûì âû÷èñëåíèÿì íà óðîâíå êëåòî÷íûõ îïåðàöèé. Ïóñòü A , B è C AB� — òðè
ìàòðèöû ïîðÿäêà n r� �3� , ãäå � �1, r — ðàçìåð êëåòêè, m n r� / . Äåêîìïîçèðó-
åì èñõîäíûå ìàòðèöû A è B íà êëåòêè çàäàííîãî ïîðÿäêà r :
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 19
A
A A A
A A A
A A A
B
m
m
m m mm
�
�
�
�
�
�
�
�
�
�
�
11 12 1
21 22 2
1 2
�
�
� � � �
�
, �
�
�
�
�
�
�
�
�
�
�
�
B B B
B B B
B B B
C
m
m
m m mm
11 12 1
21 22 2
1 2
�
�
� � � �
�
,
C C C
C C C
C C C
m
m
m m mm
11 12 1
21 22 2
1 2
�
�
� � � �
�
�
�
�
�
�
�
�
�
�
�
.
r
r r
r r
r
© Ë.Ä. Åëôèìîâà, 2013
Ðåçóëüòèðóþùàÿ ìàòðèöà C AB� áóäåò èìåòü èäåíòè÷íóþ êàæäîìó ñîìíî-
æèòåëþ êëåòî÷íóþ ñòðóêòóðó.
Âåëè÷èíà r çàâèñèò îò âûáðàííîãî âíóòðåííåãî àëãîðèòìà, â êà÷åñòâå êîòî-
ðîãî ìîæíî èñïîëüçîâàòü èçâåñòíûå àëãîðèòìû ìàòðè÷íîãî óìíîæåíèÿ, îïåðè-
ðóþùèå ÷èñëàìè.
Êëåòî÷íûé ìåòîä, îïåðèðóþùèé ( )r r� -ìàòðèöàìè, ñîñòîèò èç òðåõ ýòàïîâ.
Ýòàï 1. Âû÷èñëÿåì ìàòðè÷íûå êîýôôèöèåíòû Rik è Fkj :
R A A A A A
ik i k i k i k i k i
1
3 2 3 2 3 2 3 1 3 2 3 3 13 2 3� � �
, , , ,
13 1 3 3 2 3 3, , , ,k i k i kA A
R A A
ik i k i k
2
3 2 3 2 3 1 3 2�
, , , R A A A
ik i k i k i k
3
3 2 3 2 3 1 3 2 3 1 3 1�
� �
, , , ,
R A A
ik i k i k
4
3 1 3 2 3 1 3 1� �
, , , R A A A
ik i k i k i k
5
3 2 3 2 3 3 2 3 3 1�
� �
, , , ,
R A A
ik i k i k
6
3 2 3 2 3 3 2�
�
, , , R A A
ik i k i k
7
3 3 2 3 3 1� �
, , , (1)
R A A A A A
ik i k i k i k i k i
8
3 2 3 2 3 2 3 1 3 2 3 3 13 1 3� � �
, , , ,
13 3 3 2 3 3 1, , ,k i k i kA A ,
R A A A
ik i k i k i k
9
3 2 3 3 3 1 3 3�
� �
, , , , R A A
ik i k i k
10
3 2 3 3 3�
, , ,
R A A
ik i k i k
11
3 3 1 3 3� �
, , , R A A A
ik i k i k i k
12
3 2 3 3 1 3 1 3 1 3�
� �
, , , ,
R A A
ik i k i k
13
3 2 3 3 1 3�
, , , R A A
ik i k i k
14
3 1 3 1 3 1 3� �
, , ,
ãäå i j k p, , , , ...,�1 2 ; p n r� / 3 ;
F B B
kj k j k j
1
3 2 3 1 3 1 3 1�
�
, , , F B B
kj k j k j
2
3 2 3 2 3 2 3 1�
� �
, ,
�
�
B B B B Bk j k j k j k j k j3 1 3 2 3 1 3 1 3 1 3 3 3 2 3 3, , , , , ,
F B B B
kj k j k j k j
3
3 2 3 2 3 2 3 1 3 1 3 1�
�
, , , , F B B
kj k j k j
4
3 2 3 2 3 2 3 1�
�
, , ,
F B B B
kj k j k j k j
5
3 2 3 2 3 2 3 3 1 3�
�
, , , ,
F B B
kj k j k j
6
3 2 3 3 1 3�
, , , F B B
kj k j k j
7
3 2 3 2 3 2 3�
�
, , , (2)
F B B B B B
kj k j k j k j k j
8
3 2 3 2 3 2 3 3 1 3 2 3 1 3 1 3�
� �
, , , , k j
1 3,
�
B Bk j k j3 3 2 3 3 1, , , F B B B
kj k j k j k j
9
3 1 3 1 3 3 2 3 3 1� �
, , , ,
F B B
kj k j k j
10
3 1 3 1 3 3 1�
, , , F B B
kj k j k j
11
3 3 2 3 3 1�
�
, , ,
F B B B
kj k j k j k j
12
3 1 3 3 3 2 3 3� �
, , , , F B B
kj k j k j
13
3 1 3 3 3�
, , ,
F B B
kj k j k j
14
3 3 2 3 3�
�
, , ,
ãäå i j k p, , , , ...,�1 2 ; p n r� / 3 .
Ýòàï 2. Âû÷èñëÿåì ïðîìåæóòî÷íûå ìàòðèöû Qij :
Q R Bij ik
k
p
k j
1 1
1
3 1 3 1� �
�
� , , Q R Fij ik
k
p
kj
2 2
1
1� �
�
� , Q A Fij i k
k
p
kj
3
3 1 3 1
1
2� �
�
� , ,
Q R Fij ik
k
p
kj
4 3
1
3� �
�
� , Q R Fij ik
k
p
kj
5 4
1
4� �
�
� , Q A Bij i k
k
p
k j
6
3 2 3 2
1
3 2 3 2� �
�
� , , ,
Q R Fij ik
k
p
kj
7 5
1
5� �
�
� , Q R Fij ik
k
p
kj
8 6
1
6� �
�
� , Q R Fij ik
k
p
kj
9 7
1
7� �
�
� ,
Q R Bij ik
k
p
k j
10 8
1
3 1 3� �
�
� , , Q A Fij i k
k
p
kj
11
3 3 1
1
8� �
�
� , , Q R Fij ik
k
p
kj
12 9
1
9� �
�
� , (3)
20 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1
Q R Fij ik
k
p
kj
13 10
1
10� �
�
� , Q A Bij i k
k
p
k j
14
3 2 3
1
3 3 2� �
�
� , , , Q R Fij ik
k
p
kj
15 11
1
11� �
�
� ,
Q R Fij ik
k
p
kj
16 12
1
12� �
�
� , Q R Fij ik
k
p
kj
17 13
1
13� �
�
� , Q R Fij ik
k
p
kj
18 14
1
14� �
�
� ,
Q A Bij i k
k
p
k j
19
3 2 3 1
1
3 1 3 2� �
�
� , , , Q A Bij i k
k
p
k j
20
3 1 3
1
3 3 1� �
�
� , , ,
Q A Bij i k
k
p
k j
21
3 1 3 2
1
3 2 3� �
�
� , , , Q A Bij i k
k
p
k j
22
3 3 2
1
3 2 3 1� �
�
� , , ,
Q A Bij i k
k
p
k j
23
3 3
1
3 3� �
�
� , , ,
ãäå i j k p, , , , ...,�1 2 .
Ýòàï 3. Âû÷èñëÿåì ðåçóëüòèðóþùèå ìàòðèöû Cij :
C Q Q Qi j ij ij ij3 2 3 2
6 14 19
� � �, ,
C Q Q Q Q Q Q Qi j ij ij ij ij ij ij ij3 2 3 1
1 4 5 6 12 14 15
� � � � � � �, ,
C Q Q Q Q Q Q Qi j ij ij ij ij ij ij ij3 2 3
6 7 9 10 14 16 18
� � � � � � �, ,
C Q Q Q Q Q Q Qi j ij ij ij ij ij ij ij3 1 3 2
2 3 4 6 14 16 17
� � � � � � �, ,
C Q Q Q Q Qi j ij ij ij ij ij3 1 3 1
2 4 5 6 20
� � � � �, , (4)
C Q Q Q Q Qi j ij ij ij ij ij3 1 3
14 16 17 18 21
� � � � �, ,
C Q Q Q Q Q Q Qi j ij ij ij ij ij ij ij3 3 2
6 7 8 11 12 13 14
,
� � � � � � � ,
C Q Q Q Q Qi j ij ij ij ij ij3 3 1
12 13 14 15 22
,
� � � � � ,
C Q Q Q Q Qi j ij ij ij ij ij3 3
6 7 8 9 23
, � � � � � ,
ãäå i j p, , , ...,�1 2 .
Îöåíèì âû÷èñëèòåëüíóþ ñëîæíîñòü ðàññìîòðåííîãî êëåòî÷íîãî ìåòîäà
(1)–(4). Ïîñêîëüêó ìàòðè÷íûå êîýôôèöèåíòû Rik (ñîîòâåòñòâåííî Fkj ) âû÷èñëÿ-
þòñÿ òîëüêî îäèí ðàç è èñïîëüçóþòñÿ äëÿ âñåé ìàòðè÷íîé ñòðîêè i (ñîîòâåòñòâåí-
íî ìàòðè÷íîãî ñòîëáöà j ), ñîñòîÿùåé èç ( )3 3r r� -êëåòîê, ïðè âû÷èñëåíèè (1)
è (2) âíåøíèé (êëåòî÷íûé) àëãîðèòì òðåáóåò 56 2p ìàòðè÷íûõ îïåðàöèé ñëî-
æåíèÿ. Äëÿ êàæäîé ìàòðè÷íîé îïåðàöèè ñëîæåíèÿ âíóòðåííèé àëãîðèòì
òðåáóåò r 2 ñêàëÿðíûõ îïåðàöèé ñëîæåíèÿ, òàê êàê ïîðÿäîê ìàòðèö-îïåðàíäîâ
ðàâåí r. Ñëåäîâàòåëüíî, àääèòèâíàÿ ñëîæíîñòü âû÷èñëåíèé (1) è (2), îïðåäåëÿå-
ìàÿ êîëè÷åñòâîì ñêàëÿðíûõ îïåðàöèé ñëîæåíèÿ, ñîñòàâëÿåò W p ra
( ),( )1 2 2 256� � �
�
�
�
�
�
�
� � �56
3
6 22
2
2 2n
r
r n, îïåðàöèé ñëîæåíèÿ.
Ïðè âû÷èñëåíèè ìàòðè÷íûõ âûðàæåíèé (3) âíåøíèé àëãîðèòì òðåáóåò 23 3p
ìàòðè÷íûõ îïåðàöèé óìíîæåíèÿ è 23 3 2( )p p
ìàòðè÷íûõ îïåðàöèé ñëîæåíèÿ.
Èñïîëüçóÿ â êà÷åñòâå âíóòðåííåãî àëãîðèòìà òðàäèöèîííûé àëãîðèòì [6], òðåáóþ-
ùèé r 3ñêàëÿðíûõ îïåðàöèé óìíîæåíèÿ è ( )r r3 2
ñêàëÿðíûõ îïåðàöèé ñëîæå-
íèÿ, ïîëó÷àåì ñëåäóþùèå çíà÷åíèÿ ìóëüòèïëèêàòèâíîé è àääèòèâíîé ñëîæíîñ-
òåé âû÷èñëåíèé (3):
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 21
� W p r
n
r
r nì
( ) ,3 3 3
3
3 323 23
3
0 85� �
�
�
�
�
�
� � îïåðàöèé óìíîæåíèÿ;
� W p p r p r r
n
r
r
n
r
a
( ) [( ) ( )]3 3 2 2 3 3 2
3
323 23
3
23
3
�
�
�
�
�
�
�
�
�
�
�
�
�
�
� �
2
2 30 85r n,
2 55 2, n îïåðàöèé ñëîæåíèÿ.
Ïðè âû÷èñëåíèè ýëåìåíòîâ ðåçóëüòèðóþùåé ìàòðèöû (4) âíåøíèé àëãî-
ðèòì òðåáóåò 42 3p ìàòðè÷íûõ îïåðàöèé ñëîæåíèÿ, à âíóòðåííèé — r 2 ñêàëÿð-
íûõ îïåðàöèé ñëîæåíèÿ, ïîýòîìó àääèòèâíàÿ ñëîæíîñòü âû÷èñëåíèé (4) ñîñòà-
âèò W p r
n
r
r na
( ) ,4 2 2
3
3 242 42
3
4 66� �
�
�
�
�
�
� � îïåðàöèé ñëîæåíèÿ.
Ñëåäîâàòåëüíî, êëåòî÷íûé àíàëîã òðàäèöèîííîãî àëãîðèòìà, ïîëó÷åííûé
íà îñíîâå ïðåäëîæåííîãî ìåòîäà (1)–(4), èìååò ñëåäóþùèå çíà÷åíèÿ ìóëüòè-
ïëèêàòèâíîé, àääèòèâíîé è îáùåé ñëîæíîñòåé:
� W nì � 0 85 3, îïåðàöèé óìíîæåíèÿ;
� W W W W n na a a a� � � � �( ),( ) ( ) ( ) , ,1 2 3 4 3 20 85 8 34 îïåðàöèé ñëîæåíèÿ;
� W W W n n n n nîáù ì à� � � � � � �0 85 0 85 8 34 1 7 8 343 3 2 3 2, , , , , îïåðàöèé ñëî-
æåíèÿ/óìíîæåíèÿ.
Òàêèì îáðàçîì, ïðåäëîæåííûé êëåòî÷íûé ìåòîä (1)–(4) ìèíèìèçèðóåò íà
15 % ìóëüòèïëèêàòèâíóþ ñëîæíîñòü òðàäèöèîííîãî àëãîðèòìà ïðè âñåõ çíà-
÷åíèÿõ n , à òàêæå àääèòèâíóþ è îáùóþ ñëîæíîñòè ïðè n � 103 , êîãäà ñëîæ-
íîñòü O n O n( ) ( )2 3�� . Îòìåòèì, ÷òî ïðè n �103 ñëîæíîñòü O n( )2 â çíà÷åíèÿõ
àääèòèâíîé è îáùåé ñëîæíîñòåé ñîñòàâëÿåò ñîîòâåòñòâåííî 0,9 % è 0,4 %
ñëîæíîñòè O n( )3 . Àíàëîãè÷íî ìîæíî ïîëó÷èòü îöåíêè ìóëüòèïëèêàòèâíîé,
àääèòèâíîé è îáùåé ñëîæíîñòåé êëåòî÷íûõ àíàëîãîâ äðóãèõ èçâåñòíûõ àëãî-
ðèòìîâ óìíîæåíèÿ ìàòðèö.
Íîâûé ñìåøàííûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö. Äàííûé ìåòîä
ÿâëÿåòñÿ ãèáðèäîì ìåòîäà Ëåéäåðìàíà [5] äëÿ óìíîæåíèÿ äâóõ ( )n n� -ìàòðèö è ðàñ-
ñìîòðåííîãî âûøå êëåòî÷íîãî ìåòîäà (1)–(4). Ïóñòü A, B è C AB� — òðè ìàòðèöû
ïîðÿäêà n rq� � �3 � (ãäå � �1, q �1). Äåêîìïîçèðóåì èñõîäíûå ìàòðèöû A è B íà
êëåòêè Aij è Bij çàäàííîãî ïîðÿäêà r, ãäå m n r� / ; � � m / 3 ; i j m, , , ...,�1 2 :
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1
A
A A A A A A m
A A A
�
� �11 1 1 1 1 2 1 2 1 1
11 12 13
� � �
� � � � �
� � � �
�� ��
, , ,
��
� �� � � � � � � �
� � � �
�
� � �
�
A A A A A A
A A A
m1 1 2 2 1
1 1 1 1
, , ,
, ,
� �
� � � , , , ,� � � � � �
�� �� ��
� � � � �1 1 2 1 2 1 1
21 22 23
� �
� � � � � �
A A A
A
m
A A A
2 1 2 2 1 2 2 2 2 1 2
2 1 1 2
� � � � � � � � � �
� �
, , , , , ,
,
� � �
�
A A A A A
A A
m� �
� �1 2 1 1 2 1 2 2 1 2 1 2 1
31 32
, , , , ,� � � � � � � �
��
A A A A m
A A
� � � � � �� �
� � �
�� ��
� � � �
� � �
� � �
A
A A A A A Am m m m m m m
33
1 1 2 2 1, , , ,� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
,
r
r
Êàæäàÿ ïîëó÷åííàÿ êëåòî÷íàÿ ìàòðèöà A è B ïîðÿäêà m ðàçáèâàåòñÿ â ñâîþ
î÷åðåäü íà äåâÿòü ðàâíûõ êëåòî÷íûõ ïîäìàòðèö Aij
ls è Bij
ls ïîðÿäêà �, ãäå íèæíèå
èíäåêñû i j, , ,�1 2 3 ïîêàçûâàþò ìåñòî ýòèõ ïîäìàòðèö â ïîëíîé ( )m m� -ìàòðèöå,
à âåðõíèå èíäåêñû l � � è s � � — ñîîòâåòñòâåííî ÷èñëî ìàòðè÷íûõ ñòðîê è ìàò-
ðè÷íûõ ñòîëáöîâ êëåòî÷íûõ ïîäìàòðèö. Ïðîèçâåäåíèåì êëåwòî÷íûõ ìàòðèö A è
B ÿâëÿåòñÿ ðåçóëüòèðóþùàÿ ìàòðèöà C, èìåþùàÿ èäåíòè÷íóþ êàæäîìó èç ñî-
ìíîæèòåëåé êëåòî÷íóþ ñòðóêòóðó.
Îáúåäèíåíèå äâóõ óïîìÿíóòûõ âûøå ìåòîäîâ îñóùåñòâëÿåòñÿ ñëåäóþùèì
îáðàçîì. Êàê èçâåñòíî, ìåòîä Ëåéäåðìàíà äëÿ óìíîæåíèÿ ìàòðèö ïîðÿäêà n ,
ìóëüòèïëèêàòèâíàÿ ñëîæíîñòü êîòîðîãî ðàâíà O n O n( ) ~ ( )
log ,3 23 2 854 , òðåáóåò
log 3 n ðåêóðñèâíûõ øàãîâ [5].
Äëÿ ïåðâîãî øàãà ðåêóðñèè ìåòîä Ëåéäåðìàíà â ìàòðè÷íîì âèäå ïðèìåíè-
òåëüíî ê êëåòî÷íûì ïîäìàòðèöàì ïîðÿäêà � çàïèñûâàåòñÿ ñëåäóþùèì îáðàçîì:
Z A A A A A A A B1
11 12 13 21 22 32 33 22
� � �
( )�� �� �� �� �� �� �� �� ,
Z A A B B2
11 21 12 22
�
�( )( )�� �� �� �� ,
Z A B B B B B B B3
22 11 12 21 22 23 31 33
�
� �
��� �� �� �� �� �� �� �( � ) ,
Z A A A B B B4
11 21 22 11 12 22
�
� �
�( )( )�� �� �� �� �� �� ,
Z A A B B5
21 22 11 12
� �
�( )( )�� �� �� �� , Z A B6
11 11
� �� �� ,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 23
B
B B B B B B m
B B B
�
� �11 1 1 1 1 2 1 2 1 1
11 12 13
� � �
� � � � �
� � � �
�� ��
, , ,
��
� �� � � � � � � �
� � � �
�
� � �
�
B B B B B B
B B B
m1 1 2 2 1
1 1 1 1
, , ,
, ,
� �
� � � , , , ,� � � � � �
�� �� ��
� � � � �1 1 2 1 2 1 1
21 22 23
� �
� � � � � �
B B B
B
m
B B B
2 1 2 2 1 2 2 2 2 1 2
2 1 1 2
� � � � � � � � � �
� �
, , , , , ,
,
� � �
�
B B B B B
B B
m� �
� �1 2 1 1 2 1 2 2 1 2 1 2 1
31 32
, , , , ,� � � � � � � �
��
B B B B m
B B
� � � � � �� �
� � �
�� ��
� � � �
� � �
� � �
B
B B B B B Bm m m m m m m
33
1 1 2 2 1, , , ,� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
,
r
r
(5)
C
C C C C C C m
C C C
�
� �11 1 1 1 1 2 1 2 1 1
11 12 13
� � �
� � � � �
� � � �
�� ��
, , ,
��
� �� � � � � � � �
� � � �
�
� � �
�
C C C C C C
C B C
m1 1 2 2 1
1 1 1 1
, , ,
, ,
� �
� � � , , , ,� � � � � �
�� �� ��
� � � � �1 1 2 1 2 1 1
21 22 23
� �
� � � � � �
C C C
C
m
C C C
2 1 2 2 1 2 2 2 2 1 2
2 1 1 2
� � � � � � � � � �
� �
, , , , , ,
,
� � �
�
C C C C C
C C
m� �
� �1 2 1 1 2 1 2 2 1 2 1 2 1
31 32
, , , , ,� � � � � � � �
��
C C C C m
C C
� � � � � �� �
� � �
�� ��
� � � �
� � �
� � �
C
C C C C C Cm m m m m m m
33
1 1 2 2 1, , , ,� �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
.
r
r
Z A A A B B B7
11 31 32 11 13 23
�
� �
�( )( )�� �� �� �� �� �� ,
Z A A B B8
11 31 13 23
�
�
( )( )�� �� �� �� , Z A A B B9
31 32 11 13
� �
�( )( )�� �� �� �� ,
Z A A A A A A A B10
11 12 13 22 23 31 32 23
� � �
( )�� �� �� �� �� �� �� �� ,
Z A B B B B B B B11
32 11 13 21 22 23 31 32
�
� �
��� �� �� �� �� �� ��( �� ) , (6)
Z A A A B B B12
13 32 33 22 31 32
�
� � �
( )( )�� �� �� �� �� �� ,
Z A A B B13
13 33 22 32
�
( )( )�� �� �� �� , Z A B14
13 31
� �� �� ,
Z A A B B15
32 33 31 32
� �
�( )( )�� �� �� �� , Z A A A B B B16
13 22 23 23 31 33
�
� � �
( )( )�� �� �� �� �� �� ,
Z A A B B17
13 23 23 33
�
( )( )�� �� �� �� , Z A A B B18
22 23 31 33
� �
�( )( )�� �� �� �� ,
Z A B19
12 21
� �� �� , Z A B20
23 32
� �� �� ,
Z A B21
21 13
� �� �� , Z A B22
31 12
� �� �� , Z A B23
33 33
� �� �� .
C Z Z Z
11
6 14 19�� � � � , C Z Z Z Z Z Z Z
12
1 4 5 6 12 14 15�� � � � � � � � ,
C Z Z Z Z Z Z Z
13
6 7 9 10 14 16 18�� � � � � � � � ,
C Z Z Z Z Z Z Z
21
2 3 4 6 14 16 17�� � � � � � � � ,
C Z Z Z Z Z
22
2 4 5 6 20�� � � � � � , C Z Z Z Z Z
23
14 16 17 18 21�� � � � � � , (7)
C Z Z Z Z Z Z Z
31
6 7 8 11 12 13 14�� � � � � � � � ,
C Z Z Z Z Z
32
12 13 14 15 22�� � � � � � , C Z Z Z Z Z
33
6 7 8 9 23�� � � � � � .
 îòëè÷èå îò ìåòîäà Ëåéäåðìàíà, êîòîðûé îïåðèðóåò ÷èñëîâûìè ïîäìàòðèöà-
ìè ïîðÿäêà n / 3, â âû÷èñëèòåëüíîì ïðîöåññå ñîãëàñíî ôîðìóëàì (6) è (7) ó÷àñòâóþò
êëåòî÷íûå ïîäìàòðèöû ïîðÿäêà �, äåêîìïîçèðîâàííûå íà êëåòêè çàäàííîãî ïîðÿäêà
r, è âû÷èñëåíèå ìàòðè÷íûõ ïðîèçâåäåíèé âûïîëíÿåòñÿ ñ èñïîëüçîâàíèåì êëåòî÷íî-
ãî ìåòîäà (1)–(4). Ïðè òàêîì ñî÷åòàíèè äâóõ ìåòîäîâ îáðàçóåòñÿ ñìåøàííûé êëå-
òî÷íûé ìåòîä, ôîðìàëèçàöèÿ êîòîðîãî îñóùåñòâëÿåòñÿ ñëåäóþùèì îáðàçîì.
Îáîçíà÷èì ñóììû êëåòî÷íûõ (� ��� -ïîäìàòðèö, âõîäÿùèõ â (6), X i è Y i
( , , , ..., ):i j �1 2 14
X A A A A A A A1
11 12 13 21 22 32 33
� � �
( )�� �� �� �� �� �� �� ,
X A A2
11 21
�
( )�� �� , X A A A3
11 21 22
�
� �( )�� �� �� ,
X A A4
21 22
� �( )�� �� , X A A A5
11 31 32
�
� �( )�� �� �� ,
X A A6
11 31
�
�( )�� �� , X A A7
31 32
� �( )�� �� , (8)
X A A A A A A A8
11 12 13 22 23 31 32
� � �
( )�� �� �� �� �� �� �� ,
X A A A9
13 32 33
�
� �( )�� �� �� , X A A10
13 33
�
( )�� �� , X A A11
32 33
� �( )�� �� ,
X A A A12
13 22 23
�
� �( )�� �� �� , X A A13
13 23
�
( )�� �� , X A A14
22 23
� �( )�� �� .
Y B B1
12 22
�
�( )�� �� , Y B B B B B B B2
11 12 21 22 23 31 33
�
� �
�( )�� �� �� �� �� �� �� ,
Y B B B3
11 12 22
�
�( )�� �� �� , Y B B4
11 12
�
�( )�� �� , Y B B B5
11 13 23
�
�( )�� �� �� ,
Y B B6
13 23
�
( )�� �� , Y B B7
11 13
�
�( )�� �� , (9)
Y B B B B B B B8
11 13 21 22 23 31 32
�
� �
�( )�� �� �� �� �� �� �� ,
Y B B B9
22 31 32
� �
( )�� �� �� , Y B B10
22 32
�
( )�� �� , Y B B11
31 32
�
�( )�� �� ,
Y B B B12
23 31 33
� �
( )�� �� �� , Y B B13
23 33
�
( )�� �� , Y B B14
31 33
�
�( )�� �� .
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1
Òîãäà âûðàæåíèå (6) ïðèìåò ñëåäóþùèé âèä:
Z X B1 1
22
� �� , Z X Y2 2 1� , Z A Y3
22
2� �� , Z X Y4 3 3� , Z X Y5 4 4� ,
Z A B6
11 11
� �� �� , Z X Y7 5 5� , Z X Y8 6 6� , Z X Y9 7 7� , Z X B10 8
23
� �� ,
Z A Y11
32
8� �� , Z X Y12 9 9� , Z X Y13 10 10� , Z A B14
13 31
� �� �� , (10)
Z X Y15 11 11� , Z X Y16 12 12� , Z X Y17 13 13� , Z X Y18 14 14� ,
Z A B19
12 21
� �� �� , Z A B20
23 32
� �� �� ,
Z A B21
21 13
� �� �� , Z A B22
31 12
� �� �� , Z A B23
33 33
� �� �� .
Âû÷èñëåíèå ïðîèçâåäåíèÿ AB C� ïî ñìåøàííîìó êëåòî÷íîìó ìåòîäó òàê-
æå âûïîëíÿåòñÿ â òðè ýòàïà.
Ýòàï 1. Îïåðèðóÿ êëåòêàìè ïîðÿäêà r, âû÷èñëÿåì ìàòðè÷íûå ñóììû ñîãëàñ-
íî âûðàæåíèÿì (8) è (9) ïî ñëåäóþùèì ôîðìóëàì:
X A A A A A Aij ij i j i j i j i j i j
1
2 2� � �
� � � � � � �( , , , , ,� � � � � � �
� �A i j2 2� �, ) ,
X A Aij ij i j
2 �
�( ),� , X A A Aij ij i j i j
3 �
� �� � �( ), ,� � � ,
X A Aij i j i j
4 � �� � �( ), ,� � � , X A A Aij ij i j i j
5
2 2�
� �� � �( ), ,� � � ,
X A Aij ij i j
6
2�
� �( ),� , X A Aij i j i j
7
2 2� �� � �( ), ,� � � ,
(11)
X A A A A A Aij ij i j i j i j i j i
8
2 2 2� � �
� � � � � � �( , , , , ,� � � � � � � j i jA
� �2� �, ) ,
X A A Aij i j i j i j
9
2 2 2 2�
� �� � � � �( ), , ,� � � � � , X A Aij i j i j
10
2 2 2�
� � �( ), ,� � � ,
X A Aij i j i j
11
2 2 2� �� � � �( ), ,� � � � , X A A Aij i j i j i j
12
2 2�
� �� � � � �( ), , ,� � � � � ,
X A Aij i j i j
13
2 2�
� � �( ), ,� � � , X A Aij i j i j
14
2� �� � � �( ), ,� � � � ,
ãäå i j, , , ..., ;�1 2 �
Y B Bij i j i j
1 �
�� � �( ), ,� � � , Y B B B Bij ij i j i j i j
2 �
� �
� � � �( , , ,� � � �
�� � � � �B B Bi j i j i j� � � � �, , , )2 2 2 2 , Y B B Bij ij i j i j
3 �
�� � �( ), ,� � � ,
Y B Bij ij i j
4 �
� �( ),� , Y B B Bij ij i j i j
5
2 2�
�� � �( ), ,� � � ,
Y B Bij i j i j
6
2 2�
� � �( ), ,� � � , Y B Bij ij i j
7
2�
� �( ), � ,
(12)
Y B B B B B Bij ij i j i j i j i j i
8
2 2 2�
� �
� � � � � � �( , , , ,� � � � � � � , , )j i jB� � �2� � ,
Y B B Bij i j i j i j
9
2 2� �
� � � � �( ), , ,� � � � � , Y B Bij i j i j
10
2�
� � � �( ), ,� � � � ,
Y B Bij i j i j
11
2 2�
�� � �( ), ,� � � , Y B B Bij i j i j i j
12
2 2 2 2� �
� � � � �( ), , ,� � � � � ,
Y B Bij i j i j
13
2 2 2�
� � � �( ), ,� � � � , Y B Bij i j i j
14
2 2 2�
�� � �( ), ,� � � ,
ãäå i j, , , ...,�1 2 �.
Ýòàï 2.  ñîîòâåòñòâèè ñ ôîðìóëîé (10) âû÷èñëÿåì 23 ìàòðè÷íûõ ïðîèçâå-
äåíèÿ Z1, Z Z2 23, ,� , äëÿ ðåàëèçàöèè êàæäîãî èç êîòîðûõ ïðèìåíÿåòñÿ êëåòî÷-
íûé ìåòîä (1)–(4). Äëÿ íàõîæäåíèÿ ïåðâîãî ìàòðè÷íîãî ïðîèçâåäåíèÿ Z1 èñ-
ïîëüçóþòñÿ êëåòî÷íûå ìàòðèöû-îïåðàíäû X X ij
1 1� { } è B Bij22
�� � { } ïîðÿäêà � :
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 25
Îòìåòèì, ÷òî êëåòî÷íàÿ ìàòðèöà B
22
�� ÿâëÿåòñÿ ïîäìàòðèöåé èñõîäíîé ìàò-
ðèöû B (5) è ó÷àñòâóåò â äàëüíåéøèõ âû÷èñëåíèÿõ êàê íåçàâèñèìàÿ.
Ñîãëàñíî êëåòî÷íîìó ìåòîäó (1)–(4) âíà÷àëå îïðåäåëÿþòñÿ ìàòðè÷íûå êî-
ýôôèöèåíòû Rik è Fkj :
R X X X Xik i k i k i k i k
1
3 2 3 2
1
3 2 3 1
1
3 2 3
1
3 1 3 2
1� � �
, , , ,
X X Xi k i k i k3 1 3 1
1
3 3 2
1
3 3
1
, , , ,
R X X
ik i k i k
2
3 2 3 2
1
3 1 3 2
1�
, ,
, R X X X
ik i k i k i k
3
3 2 3 2
1
3 1 3 2
1
3 1 3 1
1�
� �
, , ,
,
R X X
ik i k i k
4
3 1 3 2
1
3 1 3 1
1� �
, ,
, R X X X
ik i k i k i k
5
3 2 3 2
1
3 3 2
1
3 3 1
1�
� �
, , ,
,
R X X
ik i k i k
6
3 2 3 2
1
3 3 2
1�
�
, ,
, R X X
ik i k i k
7
3 3 2
1
3 3 1
1� �
, ,
, (13)
R X X X Xik i k i k i k i k
8
3 2 3 2
1
3 2 3 1
1
3 2 3
1
3 1 3 1
1� � �
, , , ,
X X Xi k i k i k3 1 3
1
3 3 2
1
3 3 1
1
, , , ,
R X X X
ik i k i k i k
9
3 2 3
1
3 3 1
1
3 3
1�
� �
, , ,
, R X X
ik i k i k
10
3 2 3
1
3 3
1�
, ,
,
R X X
ik i k i k
11
3 3 1
1
3 3
1� �
, ,
, R X X X
ik i k i k i k
12
3 2 3
1
3 1 3 1
1
3 1 3
1�
� �
, , ,
,
R X X
ik i k i k
13
3 2 3
1
3 1 3
1�
, ,
, R X X
ik i k i k
14
3 1 3 1
1
3 1 3
1� �
, ,
,
ãäå i j k p, , , , ...,�1 2 ; p n r� / 9 ;
F B B
kj k j k j
1
3 2 3 1 3 1 3 1
�
�
, ,
, F B B
kj k j k j
2
3 2 3 2 3 2 3 1
�
� �
, ,
�
�
B B B B B
k j k j k j k j k j3 1 3 2 3 1 3 1 3 1 3 3 3 2 3 3, , , , ,
,
F B B B
kj k j k j k j
3
3 2 3 2 3 2 3 1 3 1 3 1
�
�
, , ,
,
F B B
kj k j k j
4
3 2 3 2 3 2 3 1
�
�
, ,
, F B B B
kj k j k j k j
5
3 2 3 2 3 2 3 3 1 3
�
�
, , ,
,
F B B
kj k j k j
6
3 2 3 3 1 3
�
, ,
, F B B
kj k j k j
7
3 2 3 2 3 2 3
�
�
, ,
,
F B B B B B
kj k j k j k j k j
8
3 2 3 2 3 2 3 3 1 3 2 3 1 3 1 3
�
� �
, , , , k j
1 3,
(14)
�
B B
k j k j3 3 2 3 3 1, ,
, F B B B
kj k j k j k j
9
3 1 3 1 3 3 2 3 3 1
� �
, , ,
,
F B B
kj k j k j
10
3 1 3 1 3 3 1
�
, ,
, F B B
kj k j k j
11
3 3 2 3 3 1
�
�
, ,
,
26 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1
X
X X X
X X X
X X X
1
11
1
12
1
1
1
21
1
22
1
2
1
1
1
2
1 1
�
�
�
�
�
�
�
� � � �
�
�
�
� � ��
�
�
�
�
�
�
�
�
�
�
�, B
B B B
B B B
B B
22
11 12 1
21 22 1
1 2
��
�
�
� �
�
�
� � � �
� B��
�
�
�
�
�
�
�
�
�
�
�
�
,
Z
Z Z Z
Z Z Z
Z Z Z
1
11
1
12
1
1
1
21
1
22
1
2
1
1
1
2
1 1
�
�
�
�
�
�
�
� � � �
�
�
�
� � ��
�
�
�
�
�
�
�
�
�
�
.
r
r
r
r
r
r
F B B B
kj k j k j k j
12
3 1 3 3 3 2 3 3
� �
, , ,
, F B B
kj k j k j
13
3 1 3 3 3
�
, ,
,
F B B
kj k j k j
14
3 3 2 3 3
�
�
, ,
,
ãäå i j k p, , , , ...,�1 2 ; p n r� / 9 .
Çàòåì âûïîëíÿþòñÿ ðåãóëÿðíûå âû÷èñëåíèÿ ìàòðèö Qij :
Q R Bij ik
k
p
k j
1 1
1
3 1 3 1� �
�
� , , Q R Fij ik
k
p
kj
2 2
1
1� �
�
� ,
Q X Fij i k
k
p
kj
3
3 1 3 1
1
1
2� �
�
� ,
, Q R Fij ik
k
p
kj
4 3
1
3� �
�
� ,
Q R Fij ik
k
p
kj
5 4
1
4� �
�
� , Q X Bij i k
k
p
k j
6
3 2 3 2
1
1
3 2 3 2� �
�
� , , ,
Q R Fij ik
k
p
kj
7 5
1
5� �
�
� , Q R Fij ik
k
p
kj
8 6
1
6� �
�
� , Q R Fij ik
k
p
kj
9 7
1
7� �
�
� ,
Q R Bij ik
k
p
k j
10 8
1
3 1 3� �
�
� , , Q X Fij i k
k
p
kj
11
3 3 1
1
1
8� �
�
� ,
,
Q R Fij ik
k
p
kj
12 9
1
9� �
�
� , Q R Fij ik
k
p
kj
13 10
1
10� �
�
� , (15)
Q X Bij i k
k
p
k j
14
3 2 3
1
1
3 3 2� �
�
� , , , Q R Fij ik
k
p
kj
15 11
1
11� �
�
� , Q R Fij ik
k
p
kj
16 12
1
12� �
�
� ,
Q R Fij ik
k
p
kj
17 13
1
13� �
�
� , Q R Fij ik
k
p
kj
18 14
1
14� �
�
� , Q X Bij i k
k
p
k j
19
3 2 3 1
1
1
3 1 3 2� �
�
� , , ,
Q X Bij i k
k
p
k j
20
3 1 3
1
1
3 3 1� �
�
� , , , Q X Bij i k
k
p
k j
21
3 1 3 2
1
1
3 2 3� �
�
� , , ,
Q X Bij i k
k
p
k j
22
3 3 2
1
1
3 2 3 1� �
�
� , , , Q X Bij i k
k
p
k j
23
3 3
1
1
3 3� �
�
� , , ,
ãäå i j k p, , , , ...,�1 2 .
 çàêëþ÷åíèå âòîðîãî ýòàïà âû÷èñëÿþòñÿ ìàòðèöû Zij
1 :
Z Q Q Q
i j ij ij ij3 2 3 2
1 6 14 19
� � �
,
,
Z Q Q Q Q Q Q Q
i j ij ij ij ij ij ij ij3 2 3 1
1 1 4 5 6 12 14 15
� � � � � � �
,
,
Z Q Q Q Q Q Q Q
i j ij ij ij ij ij ij ij3 2 3
1 6 7 9 10 14 16 18
� � � � � � �
,
,
Z Q Q Q Q Q Q Q
i j ij ij ij ij ij ij ij3 1 3 2
1 2 3 4 6 14 16 17
� � � � � � �
,
,
Z Q Q Q Q Q
i j ij ij ij ij ij3 1 3 1
1 2 4 5 6 20
� � � � �
,
, (16)
Z Q Q Q Q Q
i j ij ij ij ij ij3 1 3
1 14 16 17 18 21
� � � � �
,
,
Z Q Q Q Q Q Q Q
i j ij ij ij ij ij ij ij3 3 2
1 6 7 8 11 12 13 14
,
� � � � � � � ,
Z Q Q Q Q Q
i j ij ij ij ij ij3 3 1
1 12 13 14 15 22
,
� � � � � ,
Z Q Q Q Q Q
i j ij ij ij ij ij3 3
1 6 7 8 9 23
,
� � � � � ,
ãäå i j p, , , ...,�1 2 .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 27
Ýòàï 3. Âû÷èñëÿåì ðåçóëüòèðóþùèå ìàòðèöû Cij :
C Z Z Zij ij ij ij� � �6 14 19 , C Z Z Z Z Z Z Zi j ij ij ij ij ij ij ij,�� � � � � � � �1 4 5 6 12 14 15 ,
C Z Z Z Z Z Z Zi j ij ij ij ij ij ij ij,2
6 7 9 10 14 16 18
�� � � � � � � � ,
C Z Z Z Z Z Z Zi j ij ij ij ij ij ij ij�� � � � � � � �,
2 3 4 6 14 16 17 ,
C Z Z Z Z Zi j ij ij ij ij ij� �� � � � � � �,
2 4 5 6 20 , (17)
C Z Z Z Z Zi j ij ij ij ij ij� �� � � � � � �,2
14 16 17 18 21,
C Z Z Z Z Z Z Zi j ij ij ij ij ij ij ij2
6 7 8 11 12 13 14
�� � � � � � � �, ,
C Z Z Z Z Zi j ij ij ij ij ij2
12 13 14 15 22
� �� � � � � � �, ,
C Z Z Z Z Zi j ij ij ij ij ij2 2
6 7 8 9 23
� �� � � � � � �, ,
ãäå i j p, , , ...,�1 2 .
Îöåíèì âû÷èñëèòåëüíóþ ñëîæíîñòü ðàññìîòðåííîãî êëåòî÷íîãî ìåòîäà
(10)–(17). Ïðè âû÷èñëåíèè ìàòðè÷íûõ âûðàæåíèé (11), (12) è (17) ýòîò ìåòîä
òðåáóåò ñîîòâåòñòâåííî 28 2� , 28 2� è 42 2� ìàòðè÷íûõ îïåðàöèé ñëîæåíèÿ, äëÿ
êàæäîé èç êîòîðûõ âíóòðåííèé àëãîðèòì òðåáóåò r 2 ñêàëÿðíûõ îïåðàöèé ñëî-
æåíèÿ. Òàêèì îáðàçîì, ñóììàðíàÿ àääèòèâíàÿ ñëîæíîñòü âû÷èñëåíèé (11),
(12) è (17), îïðåäåëÿåìàÿ êîëè÷åñòâîì ñêàëÿðíûõ îïåðàöèé ñëîæåíèÿ, ñîñòàâ-
ëÿåò W r
m
r
n
r
a
( ),( ),( )11 12 17 2 2
2
298 98
3
98
3
� � �
�
�
�
�
�
� � �
�
�
�
�
�
� � � �
2
2 210 9r n, îïåðàöèé
ñëîæåíèÿ.
Îïðåäåëèì ñëîæíîñòü âû÷èñëåíèé îäíîãî èç 23 ìàòðè÷íûõ ïðîèçâåäå-
íèé Z1, ò.å. âû÷èñëåíèé (13), (14) è (16). Ïðè íàõîæäåíèè ìàòðè÷íûõ êîýôôè-
öèåíòîâ Rik , Fkj è ìàòðèö Zij
1 âíåøíèå àëãîðèòìû òðåáóþò ñîîòâåòñòâåííî
28 2p , 28 2p è 42 2p ìàòðè÷íûõ îïåðàöèé ñëîæåíèÿ, äëÿ êàæäîé èç êîòîðûõ
âíóòðåííèé àëãîðèòì òðåáóåò r 2 ñêàëÿðíûõ îïåðàöèé ñëîæåíèÿ. Ñóììàðíàÿ àä-
äèòèâíàÿ ñëîæíîñòü óêàçàííûõ âû÷èñëåíèé ñîñòàâëÿåò Wa
( ),( ),( )13 14 16 �
� � �
�
�
�
�
�
� � �98 98
9
1212 2
2
2 2p r
n
r
r n, îïåðàöèé ñëîæåíèÿ.
Ïðè âû÷èñëåíèè ìàòðè÷íûõ âûðàæåíèé (15) âíåøíèé àëãîðèòì òðåáóåò
23 3p ìàòðè÷íûõ îïåðàöèé óìíîæåíèÿ è 23 3 2( )p p
ìàòðè÷íûõ îïåðàöèé ñëî-
æåíèÿ. Èñïîëüçóÿ â êà÷åñòâå âíóòðåííåãî òðàäèöèîííûé àëãîðèòì óìíîæåíèÿ
ìàòðèö [6], òðåáóþùèé r 3 ñêàëÿðíûõ îïåðàöèé óìíîæåíèÿ è ( )r r3 2
ñêàëÿð-
íûõ îïåðàöèé ñëîæåíèÿ, ïîëó÷àåì äëÿ ìóëüòèïëèêàòèâíîé è àääèòèâíîé ñëîæ-
íîñòåé âû÷èñëåíèé (15) ñîîòâåòñòâåííî ñëåäóþùèå çíà÷åíèÿ:
� W p r
n
r
r nì
( ) ,15 3 3
3
3 323 23
9
0 0315� � �
�
�
�
�
�
� � � îïåðàöèé óìíîæåíèÿ;
� W p p r p r r
n
r
r
n
a
( ) [( ) ( )]15 3 2 2 3 3 2
3
323 23
9
23
9
�
�
�
�
�
�
�
�
�
r
r n
�
�
�
�
�
� �
2
2 30 0315,
0 284 2, n îïåðàöèé ñëîæåíèÿ.
Ñëåäîâàòåëüíî, íà îñíîâå ðàññìîòðåííîãî ñìåøàííîãî êëåòî÷íîãî ìåòîäà
(10)–(17) ïîëó÷àåì êëåòî÷íûé àíàëîã òðàäèöèîííîãî àëãîðèòìà ñî ñëåäóþùèìè
28 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1
çíà÷åíèÿìè ìóëüòèïëèêàòèâíîé, àääèòèâíîé è îáùåé ñëîæíîñòåé:
� W W n nì ì� � � � �23 23 0 0315 0 7215 3 3( ) , , îïåðàöèé óìíîæåíèÿ;
� W W W Wa a a a� � � �23 2313 14 16 15 11 12 17( )( ),( ),( ) ( ) ( ),( ),( ) ( , ,121 0 03152 3n n�
� � �0 284 10 9 0 72 32 22 2 3 2, ) , , ,n n n n îïåðàöèé ñëîæåíèÿ;
� W W W n n n n nîáù ì à� � � � � � �0 72 0 72 32 2 144 32 23 2 2 3 2, , , , , îïåðàöèé ñëî-
æåíèÿ/óìíîæåíèÿ.
Òàêèì îáðàçîì, ïðåäëîæåííûé êëåòî÷íûé ìåòîä (10)–(17) ìèíèìèçèðóåò íà
28 % ìóëüòèïëèêàòèâíóþ ñëîæíîñòü òðàäèöèîííîãî àëãîðèòìà ïðè âñåõ çíà÷å-
íèÿõ n , à òàêæå àääèòèâíóþ è îáùóþ ñëîæíîñòè ïðè n � 104 , êîãäà ñëîæíîñòü
O n O n( ) ( )2 3�� . Ñëåäóåò îòìåòèòü, ÷òî ïðè n �104 ñëîæíîñòü O n( )2 â çíà÷åíèÿõ
àääèòèâíîé è îáùåé ñëîæíîñòåé ñîñòàâëÿåò ñîîòâåòñòâåííî 0,4 % è 0,2 % ñëîæ-
íîñòè O n( )3 . Àíàëîãè÷íî ìîæíî ïîëó÷èòü îöåíêè âû÷èñëèòåëüíîé ñëîæíîñòè
êëåòî÷íûõ àíàëîãîâ äðóãèõ èçâåñòíûõ àëãîðèòìîâ óìíîæåíèÿ ìàòðèö.
Ðàññìîòðåííûå ìåòîäû (1)–(4) è (10)–(17) ñîâìåñòíî ñ èçâåñòíûìè ìåòîäàìè
[2, 3] îáðàçóþò ñåìåéñòâî êëåòî÷íûõ ìåòîäîâ óìíîæåíèÿ ìàòðèö êàê ÷åòíîãî, òàê
è íå÷åòíîãî ïîðÿäêà, êîòîðûå îáåñïå÷èâàþò ìèíèìèçàöèþ ìóëüòèïëèêàòèâíîé,
àääèòèâíîé è îáùåé ñëîæíîñòåé èçâåñòíûõ àëãîðèòìîâ óìíîæåíèÿ ìàòðèö. Ýòè
ìåòîäû ìîæíî ýôôåêòèâíî ðåàëèçîâàòü â ìàòðè÷íûõ ìàøèíàõ è ñèñòåìàõ.
CÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ë û ñ à í î â Ñ . Þ . Êëåòî÷íûå ìåòîäû ðåøåíèÿ çàäà÷ ëèíåéíîé àëãåáðû // Âîïð. êèáåðíåòèêè. —
1988. — ¹ 135. — Ñ. 64–73.
2. Å ë ô è ì î â à Ë . Ä . Áûñòðûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö // Êèáåðíåòèêà è ñèñòåìíûé
àíàëèç. — 2008. — ¹ 3. — Ñ. 55–59.
3. Å ë ô è ì î â à Ë . Ä . Ñìåøàííûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö // Òàì æå. — 2009. — ¹ 1. —
Ñ. 22–27.
4. S t r a s s e n V . Gaussian elimination is not optimal // Numer. Math. — 1969. — 13. — P. 354–356.
5. L a d e r m a n J . D . A noncommutative algorithm for multiplying 3 3� -matrices using 23 multiplications //
Bull. Amer. Math. Soc. — 1976. — 82, N 1. — P. 126–128.
6. Ô à ä ä å å â Ä . Ê . , Ô à ä ä å å â à  . Í . Âû÷èñëèòåëüíûå ìåòîäû ëèíåéíîé àëãåáðû. — Ì.; Ë.:
Ôèçìàòãèç, 1963. — 734 ñ.
7. Å ë ô è ì î â à Ë . Ä . Íîâûå áûñòðûå ãèáðèäíûå àëãîðèòìû óìíîæåíèÿ ìàòðèö // Êèáåðíåòèêà è
ñèñòåìíûé àíàëèç. — 2011. — ¹ 6. — Ñ. 59–67.
Ïîñòóïèëà 27.10.2011
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 29
|
| id | nasplib_isofts_kiev_ua-123456789-86161 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-27T13:52:35Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Елфимова, Л.Д. 2015-09-08T18:00:14Z 2015-09-08T18:00:14Z 2013 Новые клеточные методы умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2013. — Т. 49, № 1. — С. 19-29. — Бібліогр.: 7 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86161 681.322.012 Запропоновано два нових клітинних методи множення матриць, які дозволяють отримати клітинні аналоги відомих алгоритмів матричного множення зі зменшеною обчислювальною складністю, порівняно з аналогами, отриманими на основі відомих клітинних методів множення матриць. Новий швидкий клітинний метод дозволяє мінімізувати на 15% мультиплікативну, адитивну і загальну складність відомих алгоритмів матричного множення. Новий змішаний клітинний метод поєднує метод Лейдермана із запропонованим швидким клітинним методом, що призводить до мінімізації на 28% мультиплікативної, адитивної і загальної складності зазначених алгоритмів. Оцінки обчислювальної складності цих методів подано на прикладі отримання клітинних аналогів традиційного алгоритму множення матриць. The paper proposes two new cellular methods of matrix multiplication, which allow obtaining cellular analogs of the well-known matrix multiplication algorithms with reduced computational complexity, as compared with the analogs derived on the basis of the well-known cellular methods of matrix multiplication. The new fast cellular method reduces by 15% the multiplicative, additive, and overall complexities of the mentioned algorithms. The new mixed cellular method combines the Laderman method with the proposed fast cellular method. The interaction of these methods reduces by 28% the multiplicative, additive, and overall complexities of the matrix multiplication algorithms. The computational complexity of these methods are estimated using the model of getting cellular analogs of the traditional matrix multiplication algorithm. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Новые клеточные методы умножения матриц Новi клiтиннi методи множення матриць New cellular methods of matrix multiplication Article published earlier |
| spellingShingle | Новые клеточные методы умножения матриц Елфимова, Л.Д. Кибернетика |
| title | Новые клеточные методы умножения матриц |
| title_alt | Новi клiтиннi методи множення матриць New cellular methods of matrix multiplication |
| title_full | Новые клеточные методы умножения матриц |
| title_fullStr | Новые клеточные методы умножения матриц |
| title_full_unstemmed | Новые клеточные методы умножения матриц |
| title_short | Новые клеточные методы умножения матриц |
| title_sort | новые клеточные методы умножения матриц |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/86161 |
| work_keys_str_mv | AT elfimovald novyekletočnyemetodyumnoženiâmatric AT elfimovald noviklitinnimetodimnožennâmatricʹ AT elfimovald newcellularmethodsofmatrixmultiplication |