Новые быстрые гибридные алгоритмы умножения матриц
Запропоновано новi гiбриднi алгоритми множення (n x n)-матриць, при побудові яких використано алгоритм Лейдермана для множення (3 x 3)-матриць. Порівняно з відомими гібридними алгоритмами множення матриць нові алгоритми характеризуються мінімізованою обчислюваною складністю. Наведено оцінки мультипл...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2011 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84251 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Новые быстрые гибридные алгоритмы умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 59-67. — Бібліогр.: 8 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860009135101181952 |
|---|---|
| author | Елфимова, Л.Д. |
| author_facet | Елфимова, Л.Д. |
| citation_txt | Новые быстрые гибридные алгоритмы умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 59-67. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано новi гiбриднi алгоритми множення (n x n)-матриць, при побудові яких використано алгоритм Лейдермана для множення (3 x 3)-матриць. Порівняно з відомими гібридними алгоритмами множення матриць нові алгоритми характеризуються мінімізованою обчислюваною складністю. Наведено оцінки мультиплікативної, адитивної та загальної складності в представлених алгоритмах.
New hybrid algorithms are proposed for multiplying (n x n)-matrices. They are based on Laderman’s algorithm for multiplying (3 x 3)-matrices. As compared with the well-known hybrid matrix multiplication algorithms, the new algorithms are characterized by the minimum computational complexity. The multiplicative, additive, and overall complexities of the algorithms are estimated.
|
| first_indexed | 2025-12-07T16:41:12Z |
| format | Article |
| fulltext |
ÓÄÊ 681.322.012
Ë.Ä. ÅËÔÈÌÎÂÀ
ÍÎÂÛÅ ÁÛÑÒÐÛÅ ÃÈÁÐÈÄÍÛÅ ÀËÃÎÐÈÒÌÛ
ÓÌÍÎÆÅÍÈß ÌÀÒÐÈÖ
Êëþ÷åâûå ñëîâà: ëèíåéíàÿ àëãåáðà, ãèáðèäíûå àëãîðèòìû óìíîæåíèÿ ìàò-
ðèö, àëãîðèòì Ëåéäåðìàíà äëÿ óìíîæåíèÿ ( )3 3� -ìàòðèö.
 íàñòîÿùåå âðåìÿ ðàçðàáîòàíû áûñòðûå ãèáðèäíûå àëãîðèòìû äëÿ óìíîæå-
íèÿ ( )n n� -ìàòðèö [1, 2], ïðè ïîñòðîåíèè êîòîðûõ èñïîëüçîâàëèñü àëãîðèòìû Øòðàñ-
ñåíà äëÿ óìíîæåíèÿ ( )2 2� -ìàòðèö [3], Âèíîãðàäà–Øòðàññåíà äëÿ óìíîæåíèÿ
( )2 2� -ìàòðèö [4] è Âèíîãðàäà [5].  óêàçàííûõ ãèáðèäíûõ àëãîðèòìàõ â îòëè÷èå îò
èçâåñòíûõ, íàïðèìåð øèðîêî ïðèìåíÿåìûõ íà ïðàêòèêå àëãîðèòìîâ [3–5], âïåðâûå
äîñòèãíóòà îäíîâðåìåííàÿ ìèíèìèçàöèÿ ìóëüòèïëèêàòèâíîé è àääèòèâíîé ñëîæíî-
ñòåé, ÷òî îáóñëîâëèâàåò èõ íàèìåíüøóþ îáùóþ âû÷èñëèòåëüíóþ ñëîæíîñòü.
Öåëü íàñòîÿùåé ðàáîòû — îïòèìèçàöèÿ âû÷èñëèòåëüíîé ñëîæíîñòè ãèá-
ðèäíûõ àëãîðèòìîâ óìíîæåíèÿ ìàòðèö. Â äàííîé ñòàòüå ðàññìàòðèâàþòñÿ íîâûå
áûñòðûå ãèáðèäíûå àëãîðèòìû äëÿ óìíîæåíèÿ ( )n n� -ìàòðèö, ïðè ïîñòðîåíèè
êîòîðûõ èñïîëüçóþòñÿ àëãîðèòìû Ëåéäåðìàíà äëÿ óìíîæåíèÿ ( )3 3� -ìàòðèö [6]
è Âèíîãðàäà [5], ÷òî ïðèâîäèò ê ìèíèìèçàöèè ìóëüòèïëèêàòèâíîé, àääèòèâíîé è
îáùåé ñëîæíîñòåé ïî ñðàâíåíèþ ñ èçâåñòíûìè ãèáðèäíûìè àëãîðèòìàìè.
ÁÛÑÒÐÛÉ ÃÈÁÐÈÄÍÛÉ ÀËÃÎÐÈÒÌ ÓÌÍÎÆÅÍÈß ÌÀÒÐÈÖ ÏÎÐßÄÊÀ n � 3� ( )� � 1
Àëãîðèòì óìíîæåíèÿ äâóõ êâàäðàòíûõ ìàòðèö A aij� { } è B bij� { } óêàçàííîãî
ïîðÿäêà n ïîñòðîåí ñ èñïîëüçîâàíèåì âîñõîäÿùåé ñõåìû âû÷èñëåíèé [7], ãäå
â êà÷åñòâå âíóòðåííåãî àëãîðèòìà ïðèìåíÿåòñÿ àëãîðèòì Ëåéäåðìàíà äëÿ
óìíîæåíèÿ ( )3 3� -ìàòðèö [6]. Ïðè ýòîì ïðèâëåêàþòñÿ ñâîéñòâà êîììóòàòèâ-
íîñòè è àññîöèàòèâíîñòè îïåðàöèè ñëîæåíèÿ. Îñíîâíûì âû÷èñëèòåëüíûì ÿä-
ðîì ïðåäëàãàåìîãî àëãîðèòìà ÿâëÿþòñÿ ñëåäóþùèå ðåãóëÿðíûå âû÷èñëåíèÿ:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 59
s bij ik
k
m
k j
1 1
1
3 1 3 1� �
�
� �� � , ,
sij ik
k
m
kj
2 2
1
1� �
�
� � � ,
s aij i k
k
m
kj
3
3 1 3 1
1
2� �� �
�
� , � ,
sij ik
k
m
kj
4 3
1
3� �
�
� � � ,
sij ik
k
m
kj
5 4
1
4� �
�
� � � ,
s a bij i k
k
m
k j
6
3 2 3 2
1
3 2 3 2� �� �
�
� �� , , ,
sij ik
k
m
kj
7 5
1
5� �
�
� � � ,
sij ik
k
m
kj
8 6
1
6� �
�
� � � ,
sij ik
k
m
kj
9 7
1
7� �
�
� � � ,
s bij ik
k
m
k j
10 8
1
3 1 3� �
�
�� � , ,
s aij i k
k
m
kj
11
3 3 1
1
8� ��
�
� , � ,
sij ik
k
m
kj
12 9
1
9� �
�
� � � ,
sij ik
k
m
kj
13 10
1
10� �
�
� � � ,
s a bij i k
k
m
k j
14
3 2 3
1
3 3 2� ��
�
�� , , ,
� Ë.Ä. Åëôèìîâà, 2011
ãäå i j k m, , , , , ;� 1 2 � m n� / 3.
Êîýôôèöèåíòû � �
ik ik
1 14, ,� è � �
kj kj
1 14, ,� îïðåäåëÿþòñÿ ïî ôîðìóëàì
�
ik i k i k i k i ka a a a1
3 2 3 2 3 2 3 1 3 2 3 3 1 3 2� � �� � � � � � �, , , ,
� � �� � �a a ai k i k i k3 1 3 1 3 3 2 3 3, , , ,
�
ik i k i ka a2
3 2 3 2 3 1 3 2� �� � � �, , ,
�
ik i k i k i ka a a3
3 2 3 2 3 1 3 2 3 1 3 1� � � � � � � �, , , ,
�
ik i k i ka a4
3 1 3 2 3 1 3 1� � � � �, , ,
�
ik i k i k i ka a a5
3 2 3 2 3 3 2 3 3 1� � � � � �, , , ,
�
ik i k i ka a6
3 2 3 2 3 3 2� � � � �, , ,
�
ik i k i ka a7
3 3 2 3 3 1� � �, , , (2)
�
ik i k i k i k i ka a a a8
3 2 3 2 3 2 3 1 3 2 3 3 1 3 1� � �� � � � � � �, , , ,
� � �� � �a a ai k i k i k3 1 3 3 3 2 3 3 1, , , ,
�
ik i k i k i ka a a9
3 2 3 3 3 1 3 3� � � �, , , ,
�
ik i k i ka a10
3 2 3 3 3� �� , , ,
�
ik i k i ka a11
3 3 1 3 3� �, , ,
�
ik i k i k i ka a a12
3 2 3 3 1 3 1 3 1 3� � � � � �, , , ,
�
ik i k i ka a13
3 2 3 3 1 3� �� �, , ,
�
ik i k i ka a14
3 1 3 1 3 1 3� � � �, , ,
ãäå i k m, , , , ;� 1 2 � m n� / 3 ;
�
kj k j k jb b1
3 2 3 1 3 1 3 1� � � � � �, , ,
�
kj k j k j k j k jb b b b2
3 2 3 2 3 2 3 1 3 1 3 2 3 1 3 1� � � �� � � � � � � �, , , ,
� � � �b b bk j k j k j3 1 3 3 3 2 3 3, , , ,
�
kj k j k j k jb b b3
3 2 3 2 3 2 3 1 3 1 3 1� � � � � � � �, , , ,
�
kj k j k jb b4
3 2 3 2 3 2 3 1� � � � � �, , ,
�
kj k j k j k jb b b5
3 2 3 2 3 2 3 3 1 3� � � � � �, , , ,
�
kj k j k jb b6
3 2 3 3 1 3� �� �, , ,
�
kj k j k jb b7
3 2 3 2 3 2 3� � � � �, , ,
60 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
sij ik
k
m
kj
15 11
1
11� �
�
� � � ,
sij ik
k
m
kj
16 12
1
12� �
�
� � � ,
sij ik
k
m
kj
17 13
1
13� �
�
� � � ,
sij ik
k
m
kj
18 14
1
14� �
�
� � � ,
s a bij i k
k
m
k j
19
3 2 3 1
1
3 1 3 2� �� �
�
� �� , , ,
s a bij i k
k
m
k j
20
3 1 3
1
3 3 1� ��
�
�� , , ,
s a bij i k
k
m
k j
21
3 1 3 2
1
3 2 3� �� �
�
�� , , ,
s a bij i k
k
m
k j
22
3 3 2
1
3 2 3 1� ��
�
� �� , , ,
s a bij i k
k
m
k j
23
3 3
1
3 3� �
�
� , , ,
(1)
�
kj k j k j k j k jb b b b8
3 2 3 2 3 2 3 3 1 3 2 3 1 3 1� � � �� � � � � � �, , , ,
� � � � �b b bk j k j k j3 1 3 3 3 2 3 3 1, , , ,
�
kj k j k j k jb b b9
3 1 3 1 3 3 2 3 3 1� �� � � �, , , ,
�
kj k j k jb b10
3 1 3 1 3 3 1� �� � �, , , (3)
�
kj k j k jb b11
3 3 2 3 3 1� � � �, , ,
�
kj k j k j k jb b b12
3 1 3 3 3 2 3 3� �� �, , , ,
�
kj k j k jb b13
3 1 3 3 3� �� , , ,
�
kj k j k jb b14
3 3 2 3 3� � �, , ,
ãäå j k m, , , , ;� 1 2 � m n� / 3.
Ýëåìåíòû ðåçóëüòèðóþùåé ìàòðèöû C cij� { } âû÷èñëÿþòñÿ ñëåäóþùèì
îáðàçîì:
c s s si j ij ij ij3 2 3 2
6 14 19
� � � , ,
c s s s s s s si j ij ij ij ij ij ij ij3 2 3 1
1 4 5 6 12 14 15
� � � , ,
c s s s s s s si j ij ij ij ij ij ij ij3 2 3
6 7 9 10 14 16 18
� � , ,
c s s s s s s si j ij ij ij ij ij ij ij3 1 3 2
2 3 4 6 14 16 17
� � � , ,
c s s s s si j ij ij ij ij ij3 1 3 1
2 4 5 6 20
� � � , ,
c s s s s si j ij ij ij ij ij3 1 3
14 16 17 18 21
� � , , (4)
c s s s s s s si j ij ij ij ij ij ij ij3 3 2
6 7 8 11 12 13 14
, � � ,
c s s s s si j ij ij ij ij ij3 3 1
12 13 14 15 22
, � � ,
c s s s s si j ij ij ij ij ij3 3
6 7 8 9 23
, � ,
ãäå i j m, , , , ;�1 2 � m n� / 3.
Âûïîëíèì îöåíêó âû÷èñëèòåëüíîé ñëîæíîñòè ãèáðèäíîãî àëãîðèòìà
(1)–(4). Ìóëüòèïëèêàòèâíàÿ ñëîæíîñòü âû÷èñëåíèé (1) ñîñòàâëÿåò
W m
n
n nì
( ) ,1 3
3
3 323 23
3
23
27
0 85� �
�
�
�
� � � (îïåðàöèé óìíîæåíèÿ).
Àääèòèâíàÿ ñëîæíîñòü âû÷èñëåíèé (1) íàõîäèòñÿ ñëåäóþùèì îáðàçîì:
W m m
n n
na
( ) [ ( )] ,1 2
3 2
323 1 23
3
23
3
0 85 2� � �
�
�
�
� �
�
�
�
� � � ,56 2n (îïåðàöèé ñëîæåíèÿ).
Ñóììàðíàÿ àääèòèâíàÿ ñëîæíîñòü âû÷èñëåíèé (2), (3) è (4) îïðåäåëÿåòñÿ êàê
W W W W m m m
n
a a a a
( ),( ),( ) ( ) ( ) ( )2 3 4 2 3 4 2 2 228 28 42 98� � �
3
10 89
2
2
�
�
�
� � , n
(îïåðàöèé ñëîæåíèÿ).
Òàêèì îáðàçîì, ïîëíàÿ àääèòèâíàÿ ñëîæíîñòü àëãîðèòìà (1)–(4) ñîñòàâëÿåò
W W W n n n na a a� � � �( ) ( ),( ),( ) , , , ,1 2 3 4 3 2 20 85 2 56 10 89 0 85 3 28 33 , n
(îïåðàöèé ñëîæåíèÿ).
Ñëåäîâàòåëüíî, îáùàÿ âû÷èñëèòåëüíàÿ ñëîæíîñòü ðàññìîòðåííîãî àëãîðèòìà
îïðåäåëÿåòñÿ êàê
W W W n n n n nîáù ì a� � � ( ) , , , , ,1 3 3 2 3 20 85 0 85 8 33 1 70 8 33
(îïåðàöèé ñëîæåíèÿ / óìíîæåíèÿ).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 61
 àëãîðèòìå (1)–(4) äîñòèãíóòà îäíîâðåìåííàÿ ìèíèìèçàöèÿ ìóëüòèïëèêà-
òèâíîé, àääèòèâíîé è îáùåé âû÷èñëèòåëüíîé ñëîæíîñòè îòíîñèòåëüíî òðàäèöè-
îííîãî àëãîðèòìà [8]. Ïðè ýòîì âûèãðûø ïî ìóëüòèïëèêàòèâíîé ñëîæíîñòè ñî-
ñòàâëÿåò 15% ïðè âñåõ çíà÷åíèÿõ n. Ïðîöåíò ìèíèìèçàöèè àääèòèâíîé è îáùåé
ñëîæíîñòåé çàâèñèò îò n. Âûèãðûø ïî àääèòèâíîé ñëîæíîñòè íà÷èíàåòñÿ ïðè
n � 63 è äîñòèãàåò ìàêñèìóìà 15% ïðè n � 104 . Âûèãðûø ïî îáùåé âû÷èñëèòåëü-
íîé ñëîæíîñòè íà÷èíàåòñÿ ïðè n � 32 è äîñòèãàåò 15% ïðè n � 103 . Ïî ñðàâíåíèþ
ñ ãèáðèäíûì àëãîðèòìîì [1] ïðåäëîæåííûé àëãîðèòì (1)–(4) îáëàäàåò óìåíü-
øåííîé íà 2,6% ìóëüòèïëèêàòèâíîé ñëîæíîñòüþ ïðè âñåõ çíà÷åíèÿõ n. ×òî êàñà-
åòñÿ âûèãðûøà ïî àääèòèâíîé ñëîæíîñòè, òî ïîñëåäíèé óâåëè÷èâàåòñÿ, íà÷èíàÿ
ñ n � 275, è ïðèíèìàåò ìàêñèìàëüíîå çíà÷åíèå 2,6% ïðè n � 104 . Ñðàâíèâàåìûå
ãèáðèäíûå àëãîðèòìû èìåþò ðàâíóþ îáùóþ âû÷èñëèòåëüíóþ ñëîæíîñòü ïðè
n �125. Ñ óâåëè÷åíèåì n ïðîöåíò ìèíèìèçàöèè îáùåé ñëîæíîñòè ïîâûøàåòñÿ,
äîñòèãàÿ ìàêñèìóìà 2,6% ïðè n �103 .
ÁÛÑÒÐÛÉ ÃÈÁÐÈÄÍÛÉ ÀËÃÎÐÈÒÌ ÓÌÍÎÆÅÍÈß ÌÀÒÐÈÖ ÏÎÐßÄÊÀ n � 6� ( )� � 0
Ðàññìàòðèâàåìûé àëãîðèòì ïîñòðîåí íà îñíîâå àëãîðèòìà (1)–(4) ïóòåì ïðåîá-
ðàçîâàíèÿ åãî ñòðóêòóðû èíôîðìàöèîííûõ ñâÿçåé ïî ìåòîäó Âèíîãðàäà [5],
÷òî äàåò âîçìîæíîñòü ìèíèìèçèðîâàòü ìóëüòèïëèêàòèâíóþ ñëîæíîñòü. Äëÿ
ýòîãî êàæäàÿ èç äâàäöàòè òðåõ ôîðìóë âûðàæåíèÿ (1) ïðåîáðàçóåòñÿ ñëåäóþ-
ùèì îáðàçîì:
s h gij ij i j
1 1 1 1� � �� , s h gij ij i j
5 5 5 5� � �� ,
s h gij ij i j
2 2 2 2� � �� , s h gij ij i j
6 6 6 6� � �� , (5)
s h gij ij i j
3 3 3 3� � �� , � � � � � � �
s h gij ij i j
4 4 4 4� � �� , s h gij ij i j
23 23 23 23� � �� , i j m, , , , ;� 1 2 � m n� / 3 ,
ãäå
� � �ij i k k j k j i k
k
m
b b1
2 1
1
6 1 3 1 6 4 3 1 2
1
1
�
� � � � �
�
( )( )
, , , ,
/2
� ,
� � � � �ij i k k j k j i k
k
m
2
2 1
2
2
1
2 1
1
2
2
1
2
�
� �
�
� ( )( )
, , , ,
/
,
� � �ij i k k j k j i k
k
m
a a3
3 1 6 4 2
2
2 1
2
3 1 6 1
1
� � � � � �
�
( )( ), , , ,
/2
� ,
� � � � �ij i k k j k j i k
k
m
4
2 1
3
2
3
2 1
3
2
3
1
2
�
� �
�
� ( )( )
, , , ,
/
,
� � � � �ij i k k j k j i k
k
m
5
2 1
4
2
4
2 1
4
2
4
1
2
�
� �
�
� ( )( )
, , , ,
/
,
� ij i k k j k j i ka b b a6
3 2 6 5 6 2 3 2 6 5 3 2 3 2 6 2� � � � � � � � �( )(, , , , )
/
k
m
�
�
1
2
,
� � � � �ij i k k j k j i k
k
m
7
2 1
5
2
5
2 1
5
2
5
1
2
�
� �
�
� ( )( )
, , , ,
/
,
� � � � �ij i k k j k j i k
k
m
8
2 1
6
2
6
2 1
6
2
6
1
2
�
� �
�
� ( )( )
, , , ,
/
,
� � � � �ij i k k j k j i k
k
m
9
2 1
7
2
7
2 1
7
2
7
1
2
�
� �
�
� ( )( )
, , , ,
/
,
62 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
� � �ij i k k j k j i k
k
m
b b10
2 1
8
6 1 3 6 4 3 2
8
1
2
�
� � �
�
� ( )( )
, , , ,
/
,
� � �ij i k k j k j i k
k
m
a a11
3 6 4 2
8
2 1
8
3 6 1
1
2
� � � �
�
� ( )( ), , , ,
/
,
� � � � �ij i k k j k j i k
k
m
12
2 1
9
2
9
2 1
9
2
9
1
2
�
� �
�
� ( )( )
, , , ,
/
,
� � � � �ij i k k j k j i k
k
m
13
2 1
10
2
10
2 1
10
2
10
1
2
�
� �
�
( )( )
, , , ,
/
� ,
� ij i k k j k j i k
k
a b b a14
3 2 6 3 6 3 2 6 3 3 2 3 2 6� � � � � � �
�
( )( ), , , ,
1
2m /
� ,
� � � � �ij i k k j k j i k
k
m
15
2 1
11
2
11
2 1
11
2
11
1
2
�
� �
�
( )( )
, , , ,
/
� ,
� � � � �ij i k k j k j i k
k
m
16
2 1
12
2
12
2 1
12
2
12
1
2
�
� �
�
( )( )
, , , ,
/
� , (6)
� � � � �ij i k k j k j i k
k
m
17
2 1
13
2
13
2 1
13
2
13
1
2
�
� �
�
( )( )
, , , ,
/
� ,
� � � � �ij i k k j k j i k
k
m
18
2 1
14
2
14
2 1
14
2
14
1
2
�
� �
�
( )( )
, , , ,
/
� ,
� ij i k k j k j i ka b b a19
3 2 3 1 6 1 3 2 6 4 3 2 3 2 6� � � � � � � � �( )(, , , , 1
1
2
)
/
k
m
�
� ,
� ij i k k j k j i k
k
a b b a20
3 1 6 3 6 3 1 6 3 3 1 3 1 6� � � � � � �
�
( )( ), , , ,
1
2m /
� ,
� ij i k k j k j i k
k
a b b a21
3 1 6 5 6 2 3 6 5 3 3 1 6 2� � � � � � �
�
( )( ), , , ,
1
2m /
� ,
� ij i k k j k j i k
k
a b b a22
3 6 5 6 2 3 1 6 5 3 1 3 6 2� � � � � � �
�
( )( ), , , ,
1
2m /
� ,
� ij i k k j k j i k
k
m
a b b a23
3 6 3 6 3 6 3 3 3 6
1
2
� � �
�
� ( )( ), , , ,
/
,
ãäå i j m, , , ,� 1 2 � ; m n� / 3; k m� 1 2 2, , , /� ;
hi i k i k
k
m
1
2 1
1
2
1
1
2
�
�
�
� � �
, ,
/
, g b bj k j k j
k
m
1
6 1 3 1 6 4 3 1
1
2
� � � � �
�
� , ,
/
,
hi i k i k
k
m
2
2 1
2
2
2
1
2
�
�
�
� � �
, ,
/
, g j k j k j
k
m
2
2
1
2 1
1
1
2
�
�
�
� � �
, ,
/
,
h a ai i k i k
k
m
3
3 1 6 4 3 1 6 1
1
2
� � � � �
�
� , ,
/
, g j k j k j
k
m
3
2
2
2 1
2
1
2
�
�
�
� � �
, ,
/
,
hi i k i k
k
m
4
2 1
3
2
3
1
2
�
�
�
� � �
, ,
/
, g j k j k j
k
m
4
2
3
2 1
3
1
2
�
�
�
� � �
, ,
/
,
hi i k i k
k
m
5
2 1
4
2
4
1
2
�
�
�
� � �
, ,
/
, g j k j k j
k
m
5
2
4
2 1
4
1
2
�
�
�
� � �
, ,
/
,
h a ai i k i k
k
m
6
3 2 6 5 3 2 6 2
1
2
� � � � �
�
� , ,
/
, g b bj k j k j
k
m
6
6 2 3 2 6 5 3 2
1
2
� � � � �
�
� , ,
/
,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 63
hi i k i k
k
m
7
2 1
5
2
5
1
2
�
�
�
� � �
, ,
/
, g j k j k j
k
m
7
2
5
2 1
5
1
2
�
�
�
� � �
, ,
/
,
hi i k i k
k
m
8
2 1
6
2
6
1
2
�
�
�
� � �
, ,
/
, g j k j k j
k
m
8
2
6
2 1
6
1
2
�
�
�
� � �
, ,
/
,
hi i k i k
k
m
9
2 1
7
2
7
1
2
�
�
�
� � �
, ,
/
, g j k j k j
k
m
9
2
7
2 1
7
1
2
�
�
�
� � �
, ,
/
,
hi i k i k
k
m
10
2 1
8
2
8
1
2
�
�
�
� � �
, ,
/
, g b bj k j k j
k
m
10
6 1 3 6 4 3
1
2
� � �
�
� , ,
/
,
h a ai i k i k
k
m
11
3 6 4 3 6 1
1
2
� � �
�
� , ,
/
, g j k j k j
k
m
11
2
8
2 1
8
1
2
�
�
�
� � �
, ,
/
,
hi i k i k
k
m
12
2 1
9
2
9
1
2
�
�
�
� � �
, ,
/
, g j k j k j
k
m
12
2
9
2 1
9
1
2
�
�
�
� � �
, ,
/
,
hi i k i k
k
m
13
2 1
10
2
10
1
2
�
�
�
� � �
, ,
/
, g j k j k j
k
m
13
2
10
2 1
10
1
2
�
�
�
� � �
, ,
/
,
h a ai i k i k
k
m
14
3 2 6 3 3 2 6
1
2
� � � �
�
� , ,
/
, g b bj k j k j
k
m
14
6 3 2 6 3 3 2
1
2
� � � �
�
� , ,
/
,
hi i k i k
k
m
15
2 1
11
2
11
1
2
�
�
�
� � �
, ,
/
, g j k j k j
k
m
15
2
11
2 1
11
1
2
�
�
�
� � �
, ,
/
,
hi i k i k
k
m
16
2 1
12
2
12
1
2
�
�
�
� � �
, ,
/
, g j k j k j
k
m
16
2
12
2 1
12
1
2
�
�
�
� � �
, ,
/
,
hi i k i k
k
m
17
2 1
13
2
13
1
2
�
�
�
� � �
, ,
/
, g j k j k j
k
m
17
2
13
2 1
13
1
2
�
�
�
� � �
, ,
/
,
hi i k i k
k
m
18
2 1
14
2
14
1
2
�
�
�
� � �
, ,
/
, g j k j k j
k
m
18
2
14
2 1
14
1
2
�
�
�
� � �
, ,
/
,
h a ai i k i k
k
m
19
3 2 3 1 3 2 6 1
1
2
� � � � �
�
� , ,
/
, g b bj k j k j
k
m
19
6 1 3 2 6 4 3 2
1
2
� � � � �
�
� , ,
/
, (7)
h a ai i k i k
k
m
20
3 1 6 3 3 1 6
1
2
� � � �
�
� , ,
/
, g b bj k j k j
k
m
20
6 3 1 6 3 3 1
1
2
� � � �
�
� , ,
/
,
h a ai i k i k
k
m
21
3 1 6 5 3 1 6 2
1
2
� � � � �
�
� , ,
/
, g b bj k j k j
k
m
21
6 2 3 6 5 3
1
2
� � �
�
� , ,
/
,
h a ai i k i k
k
m
22
3 6 5 3 6 2
1
2
� � �
�
� , ,
/
, g b bj k j k j
k
m
22
6 2 3 1 6 5 3 1
1
2
� � � � �
�
� , ,
/
,
h a ai i k i k
k
m
23
3 6 3 3 6
1
2
� �
�
� , ,
/
, g b bj k j k j
k
m
23
6 3 6 3 3
1
2
� �
�
� , ,
/
,
ãäå i j m, , , , ;�1 2 � m n� / 3; k m�1 2 2, , , /� .
Êîýôôèöèåíòû � �
ik ik
1 14, ,� è � �
kj kj
1 14, ,� ñîîòâåòñòâåííî èìåþò âèä
�
ik i k i k i k i ka a a a1
3 2 3 2 3 2 3 1 3 2 3 3 1 3 2� � �� � � � � � �, , , ,
� � �� � �a a ai k i k i k3 1 3 1 3 3 2 3 3, , , ,
�
ik i k i ka a2
3 2 3 2 3 1 3 2� �� � � �, , ,
�
ik i k i k i ka a a3
3 2 3 2 3 1 3 2 3 1 3 1� � � � � � � �, , , ,
�
ik i k i ka a4
3 1 3 2 3 1 3 1� � � � �, , ,
64 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
�
ik i k i k i ka a a5
3 2 3 2 3 3 2 3 3 1� � � � � �, , , ,
�
ik i k i ka a6
3 2 3 2 3 3 2� � � � �, , ,
�
ik i k i ka a7
3 3 2 3 3 1� � �, , , (8)
�
ik i k i k i k i ka a a a8
3 2 3 2 3 2 3 1 3 2 3 3 1 3 1� � �� � � � � � �, , , ,
� � �� � �a a ai k i k i k3 1 3 3 3 2 3 3 1, , , ,
�
ik i k i k i ka a a9
3 2 3 3 3 1 3 3� � � �, , , ,
�
ik i k i ka a10
3 2 3 3 3� �� , , ,
�
ik i k i ka a11
3 3 1 3 3� �, , ,
�
ik i k i k i ka a a12
3 2 3 3 1 3 1 3 1 3� � � � � �, , , ,
�
ik i k i ka a13
3 2 3 3 1 3� �� �, , ,
�
ik i k i ka a14
3 1 3 1 3 1 3� � � �, , ,
ãäå i k m, , , , ;� 12 � m n� / 3;
�
kj k j k jb b1
3 2 3 1 3 1 3 1� � � � � �, , ,
�
kj k j k j k j k jb b b b2
3 2 3 2 3 2 3 1 3 1 3 2 3 1 3 1� � � �� � � � � � � �, , , ,
� � � �b b bk j k j k j3 1 3 3 3 2 3 3, , , ,
�
kj k j k j k jb b b3
3 2 3 2 3 2 3 1 3 1 3 1� � � � � � � �, , , ,
�
kj k j k jb b4
3 2 3 2 3 2 3 1� � � � � �, , ,
�
kj k j k j k jb b b5
3 2 3 2 3 2 3 3 1 3� � � � � �, , , ,
�
kj k j k jb b6
3 2 3 3 1 3� �� �, , ,
�
kj k j k jb b7
3 2 3 2 3 2 3� � � � �, , , (9)
�
kj k j k j k j k jb b b b8
3 2 3 2 3 2 3 3 1 3 2 3 1 3 1� � � �� � � � � � �, , , ,
� � � � �b b bk j k j k j3 1 3 3 3 2 3 3 1, , , ,
�
kj k j k j k jb b b9
3 1 3 1 3 3 2 3 3 1� �� � � �, , , ,
�
kj k j k jb b10
3 1 3 1 3 3 1� �� � �, , ,
�
kj k j k jb b11
3 3 2 3 3 1� � � �, , ,
�
kj k j k j k jb b b12
3 1 3 3 3 2 3 3� �� �, , , ,
�
kj k j k jb b13
3 1 3 3 3� �� , , ,
�
kj k j k jb b14
3 3 2 3 3� � �, , ,
ãäå j k m, , , , ;� 12 � m n� / 3.
Ýëåìåíòû ðåçóëüòèðóþùåé ìàòðèöû C cij� { } âû÷èñëÿþòñÿ ïî ñëåäóþùèì
ôîðìóëàì:
c s s si j ij ij ij3 2 3 2
6 14 19
� � � , ,
c s s s s s s si j ij ij ij ij ij ij ij3 2 3 1
1 4 5 6 12 14 15
� � � , ,
c s s s s s s si j ij ij ij ij ij ij ij3 2 3
6 7 9 10 14 16 18
� � , ,
c s s s s s s si j ij ij ij ij ij ij ij3 1 3 2
2 3 4 6 14 16 17
� � � , ,
c s s s s si j ij ij ij ij ij3 1 3 1
2 4 5 6 20
� � � , , (10)
c s s s s si j ij ij ij ij ij3 1 3
14 16 17 18 21
� � , ,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 65
c s s s s s s si j ij ij ij ij ij ij ij3 3 2
6 7 8 11 12 13 14
, � � ,
c s s s s si j ij ij ij ij ij3 3 1
12 13 14 15 22
, � � ,
c s s s s si j ij ij ij ij ij3 3
6 7 8 9 23
, � ,
ãäå i j m, , , , ;� 1 2 � m n� / 3.
Âûïîëíèì îöåíêó îïåðàöèîííîé ñëîæíîñòè àëãîðèòìà (5)–(10). Àääèòèâíàÿ
ñëîæíîñòü âû÷èñëåíèé (5) îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:
W m
n
n na
( ) ,5 2
2
2 223 2 46
3
46
9
5111� � �
�
�
�
� � � (îïåðàöèé âû÷èòàíèÿ).
Ìóëüòèïëèêàòèâíàÿ è àääèòèâíàÿ ñëîæíîñòè âû÷èñëåíèé (6) ñîîòâåòñòâåí-
íî ñîñòàâëÿþò
W
m
m
n
nì
( ) ,6 2
3
323
2
23
54
0 426�
�
�
�
� �
�
�
�
�
�
�
� (îïåðàöèé óìíîæåíèÿ),
W m
m
m
m n
a
( )6 2 2
3
23
2
1 23 2
2
69
54
� �
�
�
�
�
�
�
�
�
�
� �
�
�
�
� �
�
�
�
�
�
�
�
�
�
�
�
�
�
� �23
9
1278 2 556
2
3 2n
n n, ,
(îïåðàöèé ñëîæåíèÿ).
Ìóëüòèïëèêàòèâíàÿ è àääèòèâíàÿ ñëîæíîñòè âû÷èñëåíèé (7) ñîîòâåòñòâåí-
íî ðàâíû
W
m
m m
n
nì
( ) ,7 2
2
22 23
2
23 23
9
2 556� �
�
�
�
� � �
�
�
�
�
�
�
� (îïåðàöèé óìíîæåíèÿ),
W m
m n n
a
( )7
2
2 23
2
1 23
9
46
3
� � �
�
�
�
�
�
�
�
�
�
� �
�
�
�
�
�
�
�
�
�
�
� � �2 556 15 3332, ,n n
(îïåðàöèé ñëîæåíèÿ).
Ñóììàðíàÿ àääèòèâíàÿ ñëîæíîñòü âû÷èñëåíèé (8), (9), (10) ñîñòàâëÿåò
W W W W m m ma a a a
( ),( ),( ) ( ) ( ) ( )8 9 10 8 9 10 2 2 228 28 42 9� � � 8
9
10 889
2
2n
n
�
�
�
�
�
�
� ,
(îïåðàöèé ñëîæåíèÿ).
Ñëåäîâàòåëüíî, ìóëüòèïëèêàòèâíàÿ, àääèòèâíàÿ è îáùàÿ âû÷èñëèòåëüíàÿ
ñëîæíîñòè àëãîðèòìà (5)–(10) ñîîòâåòñòâåííî ðàâíû
W W W n nì ì a� � ( ) ( ) , ,6 7 3 20 426 2 556 (îïåðàöèé óìíîæåíèÿ),
W W W W W n na a a a a� � �( ) ( ) ( ) ( ),( ),( ) ,5 6 7 8 9 10 3 21278 16 15 333, n
(îïåðàöèé ñëîæåíèÿ),
W W W n n nîáù ì a� � �1 704 18 556 15 3333 2, , , (îïåðàöèé óìíîæåíèÿ/ñëîæåíèÿ).
Àëãîðèòì (5)–(10) èìååò ìèíèìèçèðîâàííóþ ìóëüòèïëèêàòèâíóþ ñëîæ-
íîñòü ïî ñðàâíåíèþ ñ àëãîðèòìîì (1)–(4) â 1,25 ðàçà ïðè n �10, â 1,9 ðàçà ïðè
n �102 , â 2 ðàçà ïðè n � 103 .  îòëè÷èå îò àëãîðèòìà Âèíîãðàäà â íåì äîñòèãíóòà
îäíîâðåìåííàÿ ìèíèìèçàöèÿ ìóëüòèïëèêàòèâíîé, àääèòèâíîé è îáùåé ñëîæíî-
ñòåé. Ïðè ýòîì âûèãðûø ïî ìóëüòèïëèêàòèâíîé ñëîæíîñòè ñîñòàâëÿåò
66 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6
11,5% ïðè n �102 , 14,5% ïðè n �103 , 14,8% ïðè n �104 è äîñòèãàåò ìàêñèìóìà
15% ïðè n �103 . Âûèãðûø ïî àääèòèâíîé ñëîæíîñòè íà÷èíàåòñÿ ïðè n � 63 è
ñîñòàâëÿåò 0,2%, ïðè n �102 ðàâåí 5,5%, ïðè n �103 óâåëè÷èâàåòñÿ äî 14%, ïðè
n �104 äîñòèãàåò 14,7%. Âûèãðûø ïî îáùåé ñëîæíîñòè ñîñòàâëÿåò 0,1% ïðè
n � 52 , 7% ïðè n �102 , 14% ïðè n �103 , 14,7% ïðè n �104 è äîñòèãàåò ìàêñèìó-
ìà 15% ïðè n �104 . Ïî ñðàâíåíèþ ñ áûñòðûì àëãîðèòìîì Øòðàññåíà ó ïðåäëî-
æåííîãî àëãîðèòìà âûèãðûøà ïî ìóëüòèïëèêàòèâíîé ñëîæíîñòè íåò, íî ïî àääè-
òèâíîé âû÷èñëèòåëüíîé ñëîæíîñòè ïðîöåíò ìèíèìèçàöèè ñîñòàâëÿåò 16% ïðè
n �10 , 40,5% ïðè n �102 , 18% ïðè n �103 , 2% ïðè n � �4 103 . Ïî îáùåé âû÷èñëè-
òåëüíîé ñëîæíîñòè âûèãðûø ñîñòàâëÿåò 12,5% ïðè n �10, 33% ïðè n �102 ,
7% ïðè n �103 , 0,8% ïðè n � �2 103 .
Òàêèì îáðàçîì, ðàññìîòðåííûå àëãîðèòìû (1)–(4) è (5)–(10) ñîâìåñòíî ñ àë-
ãîðèòìàìè èç ðàáîò [1, 2] îáðàçóþò ñåìåéñòâî áûñòðûõ ãèáðèäíûõ àëãîðèòìîâ,
îòëè÷àþùèõñÿ îò èçâåñòíûõ íàèìåíüøåé îïåðàöèîííîé ñëîæíîñòüþ. Íà îñíîâå
àëãîðèòìîâ (1)–(4) è (5)–(10) ìîæíî ïîñòðîèòü áûñòðûå àëãîðèòìû äëÿ áàçîâîé
îïåðàöèè êëåòî÷íûõ ìåòîäîâ ëèíåéíîé àëãåáðû. Ýòè àëãîðèòìû ìîãóò áûòü òàê-
æå ýôôåêòèâíî ðåàëèçîâàíû íà ðàçëè÷íûõ ïàðàëëåëüíûõ âû÷èñëèòåëüíûõ
ñèñòåìàõ.
CÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Å ë ô è ì î â à Ë . Ä . , Ê à ï è ò î í î â à Þ . Â . Áûñòðûé àëãîðèòì äëÿ óìíîæåíèÿ ìàòðèö è åãî
ýôôåêòèâíàÿ ðåàëèçàöèÿ íà ñèñòîëè÷åñêèõ ìàññèâàõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2001. —
¹ 1. — Ñ. 135–150.
2. Å ë ô è ì î â à Ë . Ä . Áûñòðûå ãèáðèäíûå àëãîðèòìû óìíîæåíèÿ ìàòðèö // Òàì æå. — 2010. — ¹ 4.
— Ñ. 49–59.
3. S t r a s s e n V . Gaussian elimination is not optimal // Numer. Math. — 1969. — 13. — P. 354–356.
4. W i n o g r a d S . On multiplication of 2 2� matrices // Linear Algebra and Its Application. — 1971. — 4.
— P. 381–388.
5. W i n o g r a d S . A . A new algorithm for inner product // IEEE Trans. Comp. — 1968. — C-18. —
P. 693–694.
6. L a d e r m a n J . D . A noncommutative algorithm for multiplying 3 x 3 matrices using 23 multiplications //
Bull. Amer. Math. Soc. — 1976. — 82, N 1. — P. 126–128.
7. M o d i J . J . Parallel algorithms and matrix computation. — Oxford: Clarendon Press, 1988. — 260 p.
8. Ô à ä ä å å â Ä . Ê . , Ô à ä ä å å â à  . Í . Âû÷èñëèòåëüíûå ìåòîäû ëèíåéíîé àëãåáðû. — Ì.; Ë.:
Ôèçìàòãèç, 1963. — 734 ñ.
Ïîñòóïèëà 23.03.2010
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 6 67
|
| id | nasplib_isofts_kiev_ua-123456789-84251 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T16:41:12Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Елфимова, Л.Д. 2015-07-04T14:51:15Z 2015-07-04T14:51:15Z 2011 Новые быстрые гибридные алгоритмы умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2011. — Т. 47, № 6. — С. 59-67. — Бібліогр.: 8 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84251 681.322.012 Запропоновано новi гiбриднi алгоритми множення (n x n)-матриць, при побудові яких використано алгоритм Лейдермана для множення (3 x 3)-матриць. Порівняно з відомими гібридними алгоритмами множення матриць нові алгоритми характеризуються мінімізованою обчислюваною складністю. Наведено оцінки мультиплікативної, адитивної та загальної складності в представлених алгоритмах. New hybrid algorithms are proposed for multiplying (n x n)-matrices. They are based on Laderman’s algorithm for multiplying (3 x 3)-matrices. As compared with the well-known hybrid matrix multiplication algorithms, the new algorithms are characterized by the minimum computational complexity. The multiplicative, additive, and overall complexities of the algorithms are estimated. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Новые быстрые гибридные алгоритмы умножения матриц Нові швидкi гiбриднi алгоритми множення матриць New fast hybrid matrix multiplication algorithms Article published earlier |
| spellingShingle | Новые быстрые гибридные алгоритмы умножения матриц Елфимова, Л.Д. Кибернетика |
| title | Новые быстрые гибридные алгоритмы умножения матриц |
| title_alt | Нові швидкi гiбриднi алгоритми множення матриць New fast hybrid matrix multiplication algorithms |
| title_full | Новые быстрые гибридные алгоритмы умножения матриц |
| title_fullStr | Новые быстрые гибридные алгоритмы умножения матриц |
| title_full_unstemmed | Новые быстрые гибридные алгоритмы умножения матриц |
| title_short | Новые быстрые гибридные алгоритмы умножения матриц |
| title_sort | новые быстрые гибридные алгоритмы умножения матриц |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84251 |
| work_keys_str_mv | AT elfimovald novyebystryegibridnyealgoritmyumnoženiâmatric AT elfimovald novíšvidkigibridnialgoritmimnožennâmatricʹ AT elfimovald newfasthybridmatrixmultiplicationalgorithms |