Быстрые гибридные алгоритмы умножения матриц
Запропоновано новi гiбриднi алгоритми множення матриць, якi вiдрiзняються вiд вiдомих найменшою операцiйною cкладнiстю. Наведено оцiнки обчислювальної складностi представлених алгоритмiв. The paper proposes new hybrid algorithms of matrix multiplication with the lowest computational complexity as c...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2010 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/45243 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Быстрые гибридные алгоритмы умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2010. — № 4. — С. 49-59. — Бібліогр.: 17 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860146250471440384 |
|---|---|
| author | Елфимова, Л.Д. |
| author_facet | Елфимова, Л.Д. |
| citation_txt | Быстрые гибридные алгоритмы умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2010. — № 4. — С. 49-59. — Бібліогр.: 17 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано новi гiбриднi алгоритми множення матриць, якi вiдрiзняються вiд вiдомих найменшою операцiйною cкладнiстю. Наведено оцiнки обчислювальної складностi представлених алгоритмiв.
The paper proposes new hybrid algorithms of matrix multiplication with the lowest computational complexity as compared with well-known matrix multiplication algorithms. The computational complexity of the above-mentioned algorithms is estimated.
|
| first_indexed | 2025-12-07T17:49:58Z |
| format | Article |
| fulltext |
ÓÄÊ 681.322.012
Ë.Ä. ÅËÔÈÌÎÂÀ
ÁÛÑÒÐÛÅ ÃÈÁÐÈÄÍÛÅ ÀËÃÎÐÈÒÌÛ ÓÌÍÎÆÅÍÈß ÌÀÒÐÈÖ
Êëþ÷åâûå ñëîâà: ëèíåéíàÿ àëãåáðà, àëãîðèòìû óìíîæåíèÿ ìàòðèö, êëåòî÷íûå
ìåòîäû, áàçîâàÿ îïåðàöèÿ.
Îäíîé èç ôóíäàìåíòàëüíûõ îïåðàöèé ïðè ïîñòðîåíèè ìíîãèõ àëãîðèòìîâ âû-
÷èñëèòåëüíîé ëèíåéíîé àëãåáðû (ËÀ) (ðåøåíèå ñèñòåì ëèíåéíûõ àëãåáðàè÷åñ-
êèõ óðàâíåíèé, îáðàùåíèå ìàòðèö, âû÷èñëåíèå îïðåäåëèòåëåé è äð.) ÿâëÿåòñÿ
ìàòðè÷íîå óìíîæåíèå, îáùàÿ âû÷èñëèòåëüíàÿ ñëîæíîñòü êîòîðîãî îïðåäåëÿåò
àñèìïòîòè÷åñêóþ ñëîæíîñòü ýòèõ àëãîðèòìîâ [1]. Äàííàÿ îïåðàöèÿ ÿâëÿåòñÿ
îñíîâíîé âî ìíîãèõ ïðåäìåòíûõ îáëàñòÿõ, îñîáåííî â öèôðîâîé îáðàáîòêå ñèã-
íàëîâ ïðè âûïîëíåíèè âûñîêîñêîðîñòíûõ âû÷èñëåíèé â ðåàëüíîì âðåìåíè [2].
Ñ ïîìîùüþ áûñòðûõ àëãîðèòìîâ ìàòðè÷íîãî óìíîæåíèÿ ðåàëèçóåòñÿ áàçîâàÿ
îïåðàöèÿ êëåòî÷íûõ ìåòîäîâ ðåøåíèÿ çàäà÷ ËÀ âèäà D C AB� � èëè
D C A Bl l
l
� �
�
�
1
�
, ãäå A B C D, , , — êâàäðàòíûå ìàòðèöû ðàçìåðà êëåòêè [3, 4].
Ïîÿâëåíèå ñåìåéñòâà àëãîðèòìîâ óìíîæåíèÿ ìàòðèö [1, 5–13] è èõ êëåòî÷íûõ
àíàëîãîâ [14, 15] îáóñëîâëåíî ñòðåìëåíèåì àâòîðîâ ðåøèòü çàäà÷ó îïòèìèçàöèè
âû÷èñëèòåëüíîé ñëîæíîñòè íàèáîëåå ýôôåêòèâíî. Êàê èçâåñòíî, â òðàäèöèîííîì
(êëàññè÷åñêîì) àëãîðèòìå [1] äâå ìàòðèöû ðàçìåðà n n� ìîæíî ïåðåìíîæèòü, èñ-
ïîëüçóÿ n3 îïåðàöèé óìíîæåíèÿ è ( )n n3 2� îïåðàöèé ñëîæåíèÿ. Îáùàÿ âû÷èñëè-
òåëüíàÿ ñëîæíîñòü àëãîðèòìà ñîñòàâëÿåò W n nîáù � �( )2 3 2 îïåðàöèé óìíîæå-
íèÿ/ñëîæåíèÿ. Ïîñêîëüêó óìíîæåíèå ÷èñåë — îïåðàöèÿ áîëåå òðóäîåìêàÿ, ÷åì èõ
ñëîæåíèå, âîçíèêàåò íåîáõîäèìîñòü â óìåíüøåíèè ìóëüòèïëèêàòèâíîé ñëîæíîñòè
àëãîðèòìîâ. Â 1968 ã. S. Winograd [5] ðàçðàáîòàë áûñòðûé ðåãóëÿðíûé àëãîðèòì
óìíîæåíèÿ ìàòðèö, ìóëüòèïëèêàòèâíàÿ ñëîæíîñòü êîòîðîãî ðàâíà
W n nì � �( , )0 5 3 2 îïåðàöèé óìíîæåíèÿ. Îäíàêî ìèíèìèçàöèÿ ìóëüòèïëèêàòèâíîé
ñëîæíîñòè ïðàêòè÷åñêè íà 50% îáóñëîâèëà óâåëè÷åíèå áîëåå ÷åì íà 50% àääèòèâ-
íîé ñëîæíîñòè, à èìåííî W n n na � � �( , )15 2 23 2 îïåðàöèé ñëîæåíèÿ. Òàêèì îáðà-
çîì, îáùàÿ âû÷èñëèòåëüíàÿ ñëîæíîñòü àëãîðèòìà [5] ñîñòàâëÿåò
W n n nîáù � � �( )2 3 23 2 îïåðàöèé óìíîæåíèÿ/ñëîæåíèÿ. Â 1969 ã. V. Strassen [6]
ïðåäëîæèë áûñòðûé ðåêóðñèâíûé àëãîðèòì, ìóëüòèïëèêàòèâíàÿ è àääèòèâíàÿ
ñëîæíîñòè êîòîðîãî ñîîòâåòñòâåííî ðàâíû W n nì
log2� 7 2 807~ , îïåðàöèé óìíîæå-
íèÿ è W
n n
a
log log� �6 7 22 22
( ) îïåðàöèé ñëîæåíèÿ. Äëÿ óìíîæåíèÿ ( )2 2� -ìàòðèö îí
èñïîëüçîâàë ñåìü îïåðàöèé óìíîæåíèÿ è 18 îïåðàöèé ñëîæåíèÿ â îòëè÷èå îò òðà-
äèöèîííîãî àëãîðèòìà, òðåáóþùåãî âîñåìü îïåðàöèé óìíîæåíèÿ è ÷åòûðå îïåðà-
öèè ñëîæåíèÿ. Ïðèìåíåíèå ýòîãî àëãîðèòìà â êà÷åñòâå áàçîâîãî äëÿ ïîñòðîåíèÿ ðå-
êóðñèâíîãî àëãîðèòìà óìíîæåíèÿ ( )n n� -ìàòðèö ( ãäå n k� 2 , k — íàòóðàëüíîå ÷èñ-
ëî) äàåò ñëåäóþùåå ñîîòíîøåíèå äëÿ âû÷èñëåíèÿ îáùåãî ÷èñëà àðèôìåòè÷åñêèõ
îïåðàöèé: W W k k k
îáù îáù� � � ��( ) ( )2 7 6 21 2 îïåðàöèé óìíîæåíèÿ / ñëîæåíèÿ. Òà-
êèì îáðàçîì, ðåêóðñèÿ ÿâëÿåòñÿ ýôôåêòèâíûì ñïîñîáîì ïîñòðîåíèÿ áûñòðîãî àë-
ãîðèòìà óìíîæåíèÿ ìàòðèö , ïîñêîëüêó ïðèâîäèò ê óìåíüøåíèþ åãî ìóëüòèïëèêà-
òèâíîé ñëîæíîñòè îòíîñèòåëüíî èñõîäíîãî òðàäèöèîííîãî àëãîðèòìà, îäíàêî ïðè
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 49
© Ë.Ä. Åëôèìîâà, 2010
ýòîì ñóùåñòâåííî óâåëè÷èâàåòñÿ àääèòèâíàÿ ñëîæíîñòü.  1971ã. S. Winograd [7]
ïðåäëîæèë àëãîðèòì, êîòîðûé ïîçâîëèë ìèíèìèçèðîâàòü àääèòèâíóþ ñëîæíîñòü
ðåêóðñèâíîãî àëãîðèòìà [6]. Äëÿ óìíîæåíèÿ (2 2� )-ìàòðèö åìó óäàëîñü èñïîëüçî-
âàòü ñåìü óìíîæåíèé è 15 ñëîæåíèé âìåñòî 18 ñëîæåíèé â àëãîðèòìå [6]. Ýòî äàëî
âîçìîæíîñòü ìèíèìèçèðîâàòü îáùóþ âû÷èñëèòåëüíóþ ñëîæíîñòü äàííîãî ðåêóð-
ñèâíîãî àëãîðèòìà, îïðåäåëÿåìóþ ñîîòíîøåíèåì W k k k
îáù ( ) ( )2 6 7 5 22� � � � îïå-
ðàöèé óìíîæåíèÿ/ñëîæåíèÿ. Â äàëüíåéøåì ïîêàçàòåëü ñòåïåíè ìóëüòèïëèêàòèâíîé
ñëîæíîñòè íîâûõ àëãîðèòìîâ ìàòðè÷íîãî óìíîæåíèÿ ïîñëåäîâàòåëüíî ñíèæàëñÿ.
Òàê, â 1978 ã. V.Ya. Pan [8] ïîëó÷èë ìóëüòèïëèêàòèâíóþ ñëîæíîñòü àëãîðèòìà,
ðàâíóþ Î( ),n2 796 . Â 1979 ã. D. Bini è ñîàâòîðû ðàáîòû [9] ìèíèìèçèðîâàëè åå äî
çíà÷åíèÿ Î( ),n2 7799 .  1981 ã. A. Sch��înhage [10] äîáèëñÿ ñëîæíîñòè, ðàâíîé
Î( ),n2 522 . Â 1982 ã. D. Coppersmith è S. Winograd [11] ïðåäëîæèëè àëãîðèòì, ñëîæ-
íîñòü êîòîðîãî ñîñòàâèëà Î( ),n2 495 . Íàèìåíüøåãî çíà÷åíèÿ ìóëüòèïëèêàòèâíîé
ñëîæíîñòè, ðàâíîãî Î( ),n2 376 , äîñòèãëè D. Coppersmith è S.Winograd [12] â 1990 ã.,
èñïîëüçóÿ àðèôìåòè÷åñêèå ïðîãðåññèè.  2001ã. Ë.Ä. Åëôèìîâà è Þ.Â. Êàïèòîíî-
âà [13] ïðåäëîæèëè áûñòðûé ãèáðèäíûé àëãîðèòì, â êîòîðîì âïåðâûå äîñòèãíóòà
îäíîâðåìåííàÿ ìèíèìèçàöèÿ ìóëüòèïëèêàòèâíîé è àääèòèâíîé ñëîæíîñòåé. Äàí-
íûé àëãîðèòì â îòëè÷èå îò àëãîðèòìà Âèíîãðàäà [5] õàðàêòåðèçóåòñÿ óìåíüøåííû-
ìè ìóëüòèïëèêàòèâíîé, àääèòèâíîé è îáùåé ñëîæíîñòÿìè, ðàâíûìè ñîîòâåòñòâåí-
íî W n nì � �( , , )0 4375 1753 2 îïåðàöèé óìíîæåíèÿ, W n n na � � �( , )13125 8 73 2 îïåðà-
öèé ñëîæåíèÿ è W n n nîáù � � �( , , )175 9 75 73 2 îïåðàöèé óìíîæåíèÿ/ñëîæåíèÿ.
Ïåðå÷èñëèìûå áûñòðûå àëãîðèòìû [8–12] èìåþò áîëüøîå òåîðåòè÷åñêîå çíà÷åíèå,
îäíàêî ïðàêòè÷åñêè öåííûìè ÿâëÿþòñÿ àëãîðèòìû [5–7, 13] ââèäó ïðîñòîòû èõ ðå-
àëèçàöèè è íàèìåíüøåé òðóäîåìêîñòè ïðîãðàììèðîâàíèÿ.
Íàñòîÿùàÿ ñòàòüÿ ÿâëÿåòñÿ ïðîäîëæåíèåì èññëåäîâàíèé â íàïðàâëåíèè îïòè-
ìèçàöèè êàê ìóëüòèïëèêàòèâíîé, òàê è àääèòèâíîé ñëîæíîñòåé óêàçàííûõ àëãîðèò-
ìîâ. Çäåñü ðàññìàòðèâàþòñÿ íîâûå ãèáðèäíûå àëãîðèòìû óìíîæåíèÿ ìàòðèö, îòëè-
÷àþùèåñÿ îò èçâåñòíûõ íàèìåíüøåé îïåðàöèîííîé ñëîæíîñòüþ. Íà èõ îñíîâå ïî-
ñòðîåíû ýôôåêòèâíûå àëãîðèòìû äëÿ óêàçàííîé âûøå êëåòî÷íîé îïåðàöèè
D C A Bl l
l
� �
�
�
1
�
.
ÁÛÑÒÐÛÉ ÃÈÁÐÈÄÍÛÉ ÀËÃÎÐÈÒÌ ÓÌÍÎÆÅÍÈß ÌÀÒÐÈÖ ÏÎÐßÄÊÀ n 2� �� �( )1
Ïðè ïîñòðîåíèè àëãîðèòìà óìíîæåíèÿ äâóõ êâàäðàòíûõ ìàòðèö A aij� ( ) è
B bij� ( ) ïîðÿäêà n � 2� ( )� � 1 èñïîëüçóåòñÿ àëãîðèòì Âèíîãðàäà–Øòðàññåíà äëÿ
óìíîæåíèÿ ( )2 2� -ìàòðèö [7]. Îñíîâíûì âû÷èñëèòåëüíûì ÿäðîì ðàññìàòðèâàå-
ìîãî àëãîðèòìà ÿâëÿþòñÿ ñëåäóþùèå ðåãóëÿðíûå ïðåîáðàçîâàíèÿ:
p s sij ik
k
m
kj
1 2
1
6� �
�
� ,
p a bij i k
k
m
k j
2
2 1 2 1
1
2 1 2 1� �� �
�
� �� , , ,
p a bij i k
k
m
k j
3
2 1 2
1
2 2 1� ��
�
�� , , ,
p s sij ik
k
m
kj
4 3
1
7� �
�
� , (1)
50 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
p s sij ik
k
m
kj
5 1
1
5� �
�
� ,
p s bij ik
k
m
k j
6 4
1
2 2� �
�
� , ,
p a sij i k
k
m
kj
7
2 2
1
8� �
�
� , ,
ãäå i j k m, , , ,... ,� 1 2 ; m n� / 2 .
Êîýôôèöèåíòû s s
ik ik
1 4, ,� è s s
kj kj
5 8,.. , îïðåäåëÿþòñÿ ïî ôîðìóëàì
s a a
ik i k i k
1
2 2 1 2 2� ��, , , s b b
kj k j k j
5
2 1 2 2 1 2 1� �� � �, , ,
s s a
ik ik i k
2 1
2 1 2 1� � � �, , s b s
kj k j kj
6
2 2
5� �, ,
(2)
s a a
ik i k i k
3
2 1 2 1 2 2 1� �� � �, , , s b b
kj k j k j
7
2 2 2 1 2� � �, , ,
s a s
ik i k ik
4
2 1 2
2� �� , , s s b
kj kj k j
8 6
2 2 1� � �, ,
ãäå i j k m, , , ,... ,� 1 2 ; m n� / 2 .
Äëÿ íàõîæäåíèÿ ðåçóëüòèðóþùåé ìàòðèöû C âûïîëíÿþòñÿ ñëåäóþùèå ïðîìå-
æóòî÷íûå âû÷èñëåíèÿ:
t p pij ij ij
1 1 2� � , t t pij ij ij
2 1 4� � , t p pij ij ij
3 5 6� � , ãäå i j m, , ,... ,� 1 2 ; m n� / 2 . (3)
Òîãäà ýëåìåíòû ðåçóëüòèðóþùåé ìàòðèöû C cij� ( ) âû÷èñëÿþòñÿ ïî ñëåäóþùèì
ôîðìóëàì:
c p pi j ij ij2 1 2 1
2 3
� � � �, ,
c t ti j ij ij2 1 2
1 3
� � �, ,
(4)
c t pi j ij ij2 2 1
2 7
, � � � ,
c t pi j ij ij2 2
2 5
, � � ,
ãäå i j m, , ,... ,� 1 2 ; m n� / 2 .
Îöåíèì îïåðàöèîííóþ ñëîæíîñòü àëãîðèòìà (1)–(4). Ìóëüòèïëèêàòèâíàÿ
ñëîæíîñòü âû÷èñëåíèé (1), îïðåäåëÿåìàÿ êîëè÷åñòâîì ñêàëÿðíûõ îïåðàöèé
óìíîæåíèÿ, ñîñòàâëÿåò
W m n nì
( ) ( / ) ,1 3 3 37 7 8 0 875� � � (îïåðàöèé óìíîæåíèÿ).
Àääèòèâíàÿ ñëîæíîñòü âû÷èñëåíèé (1), îïðåäåëÿåìàÿ êîëè÷åñòâîì ñêàëÿðíûõ
îïåðàöèé ñëîæåíèÿ / âû÷èòàíèÿ, íàõîäèòñÿ ñëåäóþùèì îáðàçîì:
W m m n na
( ) [ ( )] ( / ) ( / )1 2 3 27 1 7 8 7 4� � � � �
� �0 875 1753 2, ,n n (îïåðàöèé ñëîæåíèÿ/âû÷èòàíèÿ).
Ñóììàðíàÿ àääèòèâíàÿ ñëîæíîñòü âû÷èñëåíèé (2), (3), (4) îïðåäåëÿåòñÿ
âûðàæåíèåì
W W W W m m ma a a a
( , , ) ( ) ( ) ( )2 3 4 2 3 4 2 2 28 3 4� � � � � � �
� �15 4 3 752 2( / ) ,n n (îïåðàöèé ñëîæåíèÿ / âû÷èòàíèÿ).
Ïîëíàÿ àääèòèâíàÿ ñëîæíîñòü àëãîðèòìà (1)–(4) ñîñòàâëÿåò
W W W n na a a� � � �( ) ( , , ) ,1 2 3 4 3 20 875 2 (îïåðàöèé ñëîæåíèÿ / âû÷èòàíèÿ).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 51
Ñëåäîâàòåëüíî, îáùàÿ âû÷èñëèòåëüíàÿ ñëîæíîñòü ðàññìîòðåííîãî àëãîðèòìà
ñîñòàâëÿåò
W W W n n nîáù ì a� � � � � �( ) , ,1 3 3 20 875 0 875 2
� �175 23 2, n n (îïåðàöèé óìíîæåíèÿ / ñëîæåíèÿ / âû÷èòàíèÿ).
Îñîáåííîñòü ðàññìîòðåííîãî àëãîðèòìà (1)–(4) ñîñòîèò â òîì, ÷òî â íåì îñó-
ùåñòâëåíà îäíîâðåìåííàÿ ìèíèìèçàöèÿ ìóëüòèïëèêàòèâíîé, àääèòèâíîé è îáùåé
ñëîæíîñòåé îòíîñèòåëüíî òðàäèöèîííîãî àëãîðèòìà [1]. Ïðè ýòîì âûèãðûø ïî
ìóëüòèïëèêàòèâíîé ñëîæíîñòè ñîñòàâëÿåò 12,5% ïðè ëþáûõ çíà÷åíèÿõ n. Ïðîöåíò
ìèíèìèçàöèè àääèòèâíîé è îáùåé ñëîæíîñòåé çàâèñèò îò âåëè÷èíû n. Äëÿ àääè-
òèâíîé ñëîæíîñòè îí ðàâåí 1% ïðè n � 26, ñîñòàâëÿåò 9,6% ïðè n � 102 è 12,2% ïðè
n � 103 , äîñòèãàåò ìàêñèìàëüíîãî çíà÷åíèÿ 12,5% ïðè n � 104 . Âûèãðûø ïî îáùåé
âû÷èñëèòåëüíîé ñëîæíîñòè ñîñòàâëÿåò 2,6% ïðè n � 15, ðàâåí 11% ïðè n � 102 è
12,36% ïðè n � 103 , äîñòèãàåò ìàêñèìàëüíîãî çíà÷åíèÿ 12,5% ïðè n 104 . Ïî ñðàâ-
íåíèþ ñ áûñòðûì àëãîðèòìîì Âèíîãðàäà [5] ïðåäëîæåííûé àëãîðèòì õàðàêòåðèçó-
åòñÿ óìåíüøåííîé îáùåé âû÷èñëèòåëüíîé ñëîæíîñòüþ ïðè âñåõ çíà÷åíèÿõ n.
Îòíîñèòåëüíî áûñòðûõ àëãîðèòìîâ Øòðàññåíà [6], Âèíîãðàäà–Øòðàññåíà [7],
Åëôèìîâîé–Êàïèòîíîâîé [13] âûèãðûø ïî îáùåé âû÷èñëèòåëüíîé ñëîæíîñòè íà-
áëþäàåòñÿ ñîîòâåòñòâåííî ïðè n
103 , n
600, n
104 . Îòìå÷åííûå ïðåèìóùåñòâà,
à òàêæå ïðîñòîòà è ðåãóëÿðíîñòü âû÷èñëåíèé, îïòèìàëüíîå ñîîòíîøåíèå ìåæäó
ìóëüòèïëèêàòèâíîé è àääèòèâíîé ñëîæíîñòÿìè ýòîãî àëãîðèòìà ñîçäàþò ïðåäïî-
ñûëêè äëÿ åãî øèðîêîãî ïðèìåíåíèÿ.
ÁÛÑÒÐÛÉ ÃÈÁÐÈÄÍÛÉ ÀËÃÎÐÈÒÌ ÓÌÍÎÆÅÍÈß ÌÀÒÐÈÖ
ÏÎÐßÄÊÀ n � �4 0� �( )
Ñòðóêòóðà èíôîðìàöèîííûõ ñâÿçåé àëãîðèòìà (1)–(4) îáåñïå÷èâàåò âîçìîæíîñòü
äàëüíåéøåé ìèíèìèçàöèè åãî ìóëüòèïëèêàòèâíîé ñëîæíîñòè. Ïðè ïîñòðîåíèè
íîâîãî àëãîðèòìà óìíîæåíèÿ äâóõ ìàòðèö ïîðÿäêà n � 4�, ãäå � — íàòóðàëüíîå
÷èñëî, èñïîëüçóåì ìåòîä Âèíîãðàäà [5] äëÿ êàæäîé èç ñåìè ôîðìóë âûðàæå-
íèÿ (1).  ðåçóëüòàòå ïîëó÷èì ñëåäóþùèå ñîîòíîøåíèÿ:
p zij ij i j
1 1 1 1� � �� � ,
p zij ij i j
2 2 2 2� � �� � ,
p zij ij i j
3 3 3 3� � �� � ,
p zij ij i j
4 4 4 4� � �� � , (5)
p zij ij i j
5 5 5 5� � �� � ,
p zij ij i j
6 6 6 6� � �� � ,
p zij ij i j
7 7 7 7� � �� � , i j m, , , , ;� 1 2 � m n� / 2 ,
ãäå
z s s s sij i k k j
k
m
k j i k
1
2 1
2
2
6
1
2
2 1
6
2
2� � �
�
�
�� ( )( )
, ,
/
, ,
,
z a b b aij i k k j
k
m
k j i
2
2 1 4 3 4 1 2 1
1
2
4 3 2 1 2� � �� � � �
�
� �� ( )(, ,
/
, � �1 4 1, )k ,
z a b b aij i k k j
k
m
k j i
3
2 1 4 2 4 2 1
1
2
4 2 2 1 2 1� � �� � �
�
� � �� ( )(, ,
/
, , )4k ,
52 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
z s s s sij i k k j
k
m
k j i k
4
2 1
3
2
7
1
2
2 1
7
2
3� � �
�
�
�� ( )( )
, ,
/
, ,
,
z s s s sij i k k j
k
m
k j i k
5
2 1
1
2
5
1
2
2 1
5
2
1� � �
�
�
�� ( )( )
, ,
/
, ,
,
z s b b sij i k k j
k
m
k j i k
6
2 1
4
4 2
1
2
4 2 2 2
4� � �
�
�
�� ( )( )
, ,
/
, ,
, (6)
z a s s aij i k k j
k
m
k j i k
7
2 4 2 2
8
1
2
2 1
8
2 4� � ��
�
�� ( )( ), ,
/
, , , i j m, , , ,� 1 2 � , k m� 1 2 2, , , /� ,
�i i k
k
m
i k
s s1
2 1
2
1
2
2
2� �
�
�
� ,
/
,
, � j k j k j
k
m
s s1
2
6
2 1
6
1
2
� �
�
�
� , ,
/
,
�i i k
k
m
i ka a2
2 1 4 3
1
2
2 1 4 1� �� �
�
� �� ,
/
, , � j k j k j
k
m
b b2
4 1 2 1 4 3 2 1
1
2
� �� � � �
�
� , ,
/
,
�i i k
k
m
i ka a3
2 1 4 2
1
2
2 1 4� �� �
�
�� ,
/
, , � j k j k j
k
m
b b3
4 2 1 4 2 2 1
1
2
� �� � �
�
� , ,
/
,
�i i k
k
m
i k
s s4
2 1
3
1
2
2
3� �
�
�
� ,
/
,
, � j k j
k
m
k j
s s4
2
7
1
2
2 1
7� �
�
�� ,
/
,
,
(7)
�i i k
k
m
i k
s s5
2 1
1
1
2
2
1� �
�
�
� ,
/
,
, � j k j
k
m
k j
s s5
2
5
1
2
2 1
5� �
�
�� ,
/
,
,
�i i k
k
m
i k
s s6
2 1
4
1
2
2
4� �
�
�
� ,
/
,
, � j k j
k
m
k jb b6
4 2
1
2
4 2 2� �
�
�� ,
/
, ,
�i i k
k
m
i ka a7
2 4 2
1
2
2 4� ��
�
� ,
/
, , � j k j
k
m
k j
s s7
2
8
1
2
2 1
8� �
�
�� ,
/
,
,
ãäå i j m, , , ,� 1 2 � ; m n� / 2 ; k m� 1 2 2, , , /� .
Êîýôôèöèåíòû s s
ik ik
1 4,.. , è s s
kj kj
5 8,.. , îïðåäåëÿþòñÿ ñëåäóþùèì îáðàçîì:
s a a
ik i k i k
1
2 2 1 2 2� ��, , , s b b
kj k j k j
5
2 1 2 2 1 2 1� �� � �, , ,
s s a
ik ik i k
2 1
2 1 2 1� � � �, , s b s
kj k j kj
6
2 2
5� �, ,
(8)
s a a
ik i k i k
3
2 1 2 1 2 2 1� �� � �, , , s b b
kj k j k j
7
2 2 2 1 2� � �, , ,
s a s
ik i k ik
4
2 1 2
2� �� , , s s b
kj kj k j
8 6
2 2 1� � �, ,
ãäå i j k m, , , , ,� 1 2 � ; m n� / 2 .
Ýëåìåíòû ðåçóëüòèðóþùåé ìàòðèöû âû÷èñëÿþòñÿ ïî ôîðìóëàì
c p pi j ij ij2 1 2 1
2 3
� � � �, ,
c t ti j ij ij2 1 2
1 3
� � �, ,
(9)
c t pi j ij ij2 2 1
2 7
, � � � ,
c t pi j ij ij2 2
2 5
, � � , i j m, , ,... ,� 1 2 ; m n� / 2 ,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 53
ãäå
t p pij ij ij
1 1 2� � , t t pij ij ij
2 1 4� � , (10)
t p pij ij ij
3 5 6� � , i j m, , , ,� 1 2 � ; m n� / 2 .
Îöåíèì îïåðàöèîííóþ ñëîæíîñòü àëãîðèòìà (5)–(10). Àääèòèâíàÿ ñëîæíîñòü
âû÷èñëåíèé (5) îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:
W m n na
( ) ( / ) ,5 2 2 22 7 14 4 3 5� � � � (îïåðàöèé âû÷èòàíèÿ).
Ìóëüòèïëèêàòèâíàÿ è àääèòèâíàÿ ñëîæíîñòè âû÷èñëåíèé (6) ñîîòâåòñòâåííî
ñîñòàâëÿþò
W
m
m m n nì
( ) ( / ) , ( / ) ,6 2 3 3 37
2
7 2 3 5 8 0 4375� ��
�
�
�
� � � � (îïåðàöèé óìíîæåíèÿ),
W m
m
m
m
a
( )6 2 27
2
1 7 2
2
� ��
�
�
�
�
�
�
�
�
�
� � � ��
�
�
�
� �
� � � � �0 4375 0 875 175 13125 1753 3 2 3 2, , , , ,n n n n n (îïåðàöèé ñëîæåíèÿ).
Ìóëüòèïëèêàòèâíàÿ è àääèòèâíàÿ ñëîæíîñòè âû÷èñëåíèé (7) ñîîòâåòñòâåííî
îïðåäåëÿþòñÿ êàê
W
m
m m nì
( ) ,7 2 22 7
2
7 175� � ��
�
�
�
� � � (îïåðàöèé óìíîæåíèÿ),
W m
m
m m n na
( ) ,7 2 22 7
2
1 7 14 175 7� � ��
�
�
�
�
�
�
�
�
�
� � � � � (îïåðàöèé ñëîæåíèÿ).
Ïðè âû÷èñëåíèè êîýôôèöèåíòîâ s
ik
r è s
kj
l (r l� �1 4 5 8, ; , ) (8) íåîáõîäèìî 8 2m
îïåðàöèé ñëîæåíèÿ / âû÷èòàíèÿ, òàê êàê îíè îïðåäåëÿþòñÿ òîëüêî îäèí ðàç è èñ-
ïîëüçóþòñÿ äëÿ âñåé ñòðîêè i (ñîîòâåòñòâåííî ñòîëáöà j ) ìàòðèöû C. Ïðè âû÷èñëå-
íèè ýëåìåíòîâ cij (9) è ïðîìåæóòî÷íûõ äàííûõ t ij (10) íåîáõîäèìî ñîîòâåòñòâåííî
4 2m è 3 2m îïåðàöèé ñëîæåíèÿ / âû÷èòàíèÿ. Ñóììàðíàÿ àääèòèâíàÿ ñëîæíîñòü
âû÷èñëåíèé (8)–(10) ñîñòàâëÿåò
W W W Wa a a a
( , , ) ( ) ( ) ( )8 9 10 8 9 10� � � �
� � � � �8 4 3 15 4 3 752 2 2 2 2m m m n n( / ) , (îïåðàöèé ñëîæåíèÿ / âû÷èòàíèÿ).
Ñëåäîâàòåëüíî, ìóëüòèïëèêàòèâíàÿ, àääèòèâíàÿ è îáùàÿ îïåðàöèîííàÿ ñëîæíîñòè
àëãîðèòìà (5)-(10) ñîîòâåòñòâåííî ñîñòàâëÿþò
W W W n nì ì ì� � � �( ) ( ) , ,6 7 3 20 4375 175 (îïåðàöèé óìíîæåíèÿ),
W W W W Wa a a a a� � � � �( ) ( ) ( ) ( , , )5 6 7 8 9 10
� � �13125 7 25 73 2, ,n n n (îïåðàöèé ñëîæåíèÿ / âû÷èòàíèÿ),
W W W n n nîáù ì a� � � � �175 9 73 2, (îïåðàöèé óìíîæåíèÿ / ñëîæåíèÿ).
Òàêèì îáðàçîì, ðàññìîòðåííûé àëãîðèòì (5)–(10) ïî ñðàâíåíèþ ñ àëãîðèòìîì
(1)–(4) èìååò ìèíèìèçèðîâàííóþ ìóëüòèïëèêàòèâíóþ ñëîæíîñòü ïðè n � 10
â 1 4, ðàçà, ïðè n � 102 — â 1,9 ðàçà, ïðè n 103 — â 2 ðàçà. Â ýòîì àëãîðèòìå äî-
ñòèãíóòà îäíîâðåìåííàÿ ìèíèìèçàöèÿ ìóëüòèïëèêàòèâíîé, àääèòèâíîé è îáùåé
ñëîæíîñòåé â îòëè÷èå îò àëãîðèòìà Âèíîãðàäà [5]. Ïðè ýòîì âûèãðûø ïî ìóëüòè-
ïëèêàòèâíîé ñëîæíîñòè ïðè n � 13 ñîñòàâëÿåò 1%, ïðè n � 103 ñîñòàâëÿåò 12,42%
54 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
è äîñòèãàåò ìàêñèìàëüíîãî çíà÷åíèÿ 12,6% ïðè n 104 . Ïî àääèòèâíîé ñëîæíîñòè
âûèãðûø 1% íàáëþäàåòñÿ ïðè n � 28 , ñîñòàâëÿåò 12,2% ïðè n � 103 è äîñòèãàåò
ìàêñèìóìà 12,5% ïðè n 104 . Âûèãðûø ïî îáùåé ñëîæíîñòè èìååò ìåñòî ïðè
n 25 è äîñòèãàåò ìàêñèìóìà 12,5% ïðè n 104 . Ïî îòíîøåíèþ ê áûñòðûì àëãî-
ðèòìàì Øòðàññåíà [6] è Âèíîãðàäà–Øòðàññåíà [7] ìèíèìèçàöèÿ ìóëüòèïëèêàòèâ-
íîé ñëîæíîñòè àëãîðèòìà (5)–(10) äîñòèãàåòñÿ ïðè n
45. Êðîìå òîãî, ðàññìàòðèâà-
åìûé çäåñü àëãîðèòì îáëàäàåò óìåíüøåííîé àääèòèâíîé (ïðè n
103 ) è îáùåé
(ïðè n
965) ñëîæíîñòÿìè. Ïî ñðàâíåíèþ ñ áûñòðûì àëãîðèòìîì Åëôèìîâîé-Êà-
ïèòîíîâîé [13] ïðåäëîæåííûé àëãîðèòì îáëàäàåò óìåíüøåííûìè àääèòèâíîé è îá-
ùåé ñëîæíîñòÿìè ïðè ðàâíîé ìóëüòèïëèêàòèâíîé ñëîæíîñòè.
ÝÔÔÅÊÒÈÂÍÛÅ ÀËÃÎÐÈÒÌÛ ÄËß ÁÀÇÎÂÎÉ ÎÏÅÐÀÖÈÈ D C A Bl l
l
� �
�
�
1
�
ÊËÅÒÎ×ÍÛÕ ÌÅÒÎÄΠËÈÍÅÉÍÎÉ ÀËÃÅÁÐÛ, ÏÎÑÒÐÎÅÍÍÛÅ ÍÀ ÎÑÍÎÂÅ
ÀËÃÎÐÈÒÌÎÂ (1)–(4) È (5)–(10)
 íàñòîÿùåå âðåìÿ äëÿ áîëüøèíñòâà ÷èñëåííûõ ìåòîäîâ ëèíåéíîé àëãåáðû è
ìíîãèõ çàäà÷ âû÷èñëèòåëüíîé ìàòåìàòèêè ðàçðàáîòàíû èõ êëåòî÷íûå àíàëîãè
[3, 4], ñâîéñòâà êîòîðûõ îáåñïå÷èâàþò âîçìîæíîñòü áûñòðîãî ðåøåíèÿ çàäà÷
ïðîèçâîëüíûõ ðàçìåðîâ íà ðàçëè÷íûõ âû÷èñëèòåëüíûõ ñèñòåìàõ è ñîçäàíèÿ ýô-
ôåêòèâíîãî ïðîãðàììíîãî îáåñïå÷åíèÿ äëÿ òàêèõ ñèñòåì. Óêàçàííûå êëåòî÷íûå
àíàëîãè òðåáóþò äëÿ ñâîåé ðåàëèçàöèè òîëüêî äâà òèïà îïåðàöèé: áàçîâóþ îïå-
ðàöèþ âèäà
D C AB� � (11)
èëè
D C A Bl l
l
� �
�
�
1
�
(12)
(ãäå A B C D, , , — êâàäðàòíûå ìàòðèöû ðàçìåðà r, � — ïåðåìåííûé èíäåêñ ñóì-
ìèðîâàíèÿ) è íåñòàíäàðòíóþ îïåðàöèþ, êîòîðûå ñîñòàâëÿþò ìàëûé ïðîöåíò îá-
ùåãî ÷èñëà îïåðàöèé àëãîðèòìà è ìîãóò áûòü ïðîèçâîëüíûìè àëãîðèòìàìè ËÀ.
Êëåòî÷íûå îïåðàöèè (11), (12) âû÷èñëÿþòñÿ ñ ïîìîùüþ èçâåñòíûõ áûñòðûõ
àëãîðèòìîâ óìíîæåíèÿ ìàòðèö è ðåàëèçóþòñÿ íà ðàçëè÷íûõ âû÷èñëèòåëüíûõ ñèñ-
òåìàõ è ïðîöåññîðíûõ ìàññèâàõ ñ ñèñòîëè÷åñêîé îðãàíèçàöèåé âû÷èñëåíèé
[13, 16]. Íàèáîëåå ýôôåêòèâíî îïåðàöèÿ (11) ðåàëèçîâàíà íà áûñòðîì ñèñòîëè÷åñ-
êîì ìàññèâå ñ öèëèíäðè÷åñêîé àðõèòåêòóðîé [17] ñ èñïîëüçîâàíèåì ÑÁÈÑ-îðè-
åíòèðîâàííîé âåðñèè áûñòðîãî àëãîðèòìà [13]. Äàííûé ìàññèâ îòëè÷àåòñÿ îò
èçâåñòíûõ íàèáîëüøåé ïðîèçâîäèòåëüíîñòüþ, ìèíèìàëüíûìè ðàçìåðàìè ðåøàþ-
ùåãî ïîëÿ è ýôôåêòèâíîé ðåàëèçàöèåé íà ÑÁÈÑ.
Ðàññìîòðåííûå âûøå ãèáðèäíûå àëãîðèòìû (1)–(4) è (5)–(10) ìîãóò áûòü èñ-
ïîëüçîâàíû äëÿ óñêîðåíèÿ âû÷èñëåíèÿ êëåòî÷íîé îïåðàöèè (12) çà ñ÷åò ïðåîáðàçî-
âàíèÿ èõ ñòðóêòóðû èíôîðìàöèîííûõ ñâÿçåé ñ ïðèâëå÷åíèåì ñâîéñòâ êîììóòàòèâ-
íîñòè è àññîöèàòèâíîñòè îïåðàöèè ñëîæåíèÿ.  ýòîì ñëó÷àå áûñòðûé ðåãóëÿðíûé
ïðîöåññ âû÷èñëåíèÿ óêàçàííîé îïåðàöèè íà îñíîâå àëãîðèòìà (1)–(4) îñóùåñòâëÿ-
åòñÿ ïóòåì ïðåîáðàçîâàíèÿ âûðàæåíèé (1) è (2) ñëåäóþùèì îáðàçîì:
p s sij ik
l
k
r
kj
l
l
1 2
1
2
6
1
�
��
�� ( )
/
( )
�
,
p a bij i k
l
k
r
k j
l
l
2
2 1 2 1
1
2
2 1 2 1
1
�
� �
�
� �
�
�� ,
( )
/
,
( )
�
,
p a bij i k
l
k
r
k j
l
l
3
2 1 2
1
2
2 2 1
1
�
�
�
�
�
�� ,
( )
/
,
( )
�
,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 55
p s sij ik
l
k
r
kj
l
l
4 3
1
2
7
1
�
��
�� ( )
/
( )
�
,
p s sij ik
l
k
r
kj
l
l
5 1
1
2
5
1
�
��
�� ( )
/
( )
�
,
p s bij ik
l
k
r
k j
l
l
6 4
1
2
2 2
1
�
��
�� ( )
/
,
( )
�
, (13)
p a sij i k
l
k
r
kj
l
l
7
2 2
1
2
8
1
�
��
�� ,
( )
/
( )
�
, i j k r, , , ,... , /� 1 2 2; l � 1 2, ,... ,�,
ãäå
s a a
ik
l
i k
l
i k
l1
2 2 1 2 2
( )
,
( )
,
( )� �
�
, s b b
kj
l
k j
l
k j
l5
2 1 2 2 1 2 1
( )
,
( )
,
( )� �
� � �
,
s s a
ik
l
ik
l
i k
l2 1
2 1 2 1
( ) ( )
,
( )� �
� �
, s b s
kj
l
k j
l
kj
l6
2 2
5( )
,
( ) ( )� � ,
(14)
s a a
ik
l
i k
l
i k
l3
2 1 2 1 2 2 1
( )
,
( )
,
( )� �
� � �
, s b b
kj
l
k j
l
k j
l7
2 2 2 1 2
( )
,
( )
,
( )� �
�
,
s a s
ik
l
i k
l
ik
l4
2 1 2
2( )
,
( ) ( )� �
�
, s s b
kj
l
kj
l
k j
l8 6
2 2 1
( ) ( )
,
( )� �
�
,
i j k r, , , ,... , /� 1 2 2 ; l � 1 2, ,... ,� .
Ñëåäóþùèå âû÷èñëåíèÿ âûïîëíÿþòñÿ åäèíîæäû â êîíöå ïðîöåññà:
t p pij ij ij
1 1 2� � , t t pij ij ij
2 1 4� � ,
t p pij ij ij
3 5 6� � , i j r, , ,... , /� 1 2 2 ; (15)
d c p pi j i j ij ij2 1 2 1 2 1 2 1
2 3
� � � �� � �, , ,
d c t ti j i j ij ij2 1 2 2 1 2
1 3
� �� � �, , ,
d c t pi j i j ij ij2 2 1 2 2 1
2 7
, ,� �� � � ,
d c t pi j i j ij ij2 2 2 2
2 5
, ,� � � , i j r, , ,... , /� 1 2 2 . (16)
Ìóëüòèïëèêàòèâíàÿ ñëîæíîñòü àëãîðèòìà (13)–(16) ñîñòàâëÿåò
W W
r
rì ì� � � �
�
�
�
� � �( ) ,13
3
37
2
0 875� � (îïåðàöèé óìíîæåíèÿ).
Àääèòèâíàÿ ñëîæíîñòü àëãîðèòìà îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:
W W
r r
a a� � � �
�
�
�
� ��
�
�
�
�
�
�
�
�
�
�
�
�
� � ��( ) ( )13 16
2
7
2 2
1 1� � 7
2
8
2
3
2
8
2
2 2 2 2
r r r r�
�
�
�
� � � �
�
�
�
� � �
�
�
�
� � �
�
�
�
� ��
� � ��( , )0 875 23 2 2r r r (îïåðàöèé ñëîæåíèÿ).
Îáùàÿ âû÷èñëèòåëüíàÿ ñëîæíîñòü àëãîðèòìà (13)–(16) ñîñòàâëÿåò
W W W r r rîáù ì a� � � � � �� ( , )175 23 2 2 (îïåðàöèé óìíîæåíèÿ / ñëîæåíèÿ).
Ýôôåêòèâíîñòü ðàññìîòðåííîãî àëãîðèòìà (13)–(16) ñîñòîèò â ìèíèìèçàöèè
åãî àääèòèâíîé ñëîæíîñòè ïî ñðàâíåíèþ ñî ñëîæíîñòüþ âû÷èñëåíèÿ îïåðàöèè (12)
ñ ïîìîùüþ àëãîðèòìà (1)–(4). Ïðè ýòîì âûèãðûø ñîñòàâëÿåò � �� �( )1 2r îïåðàöèé
56 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
ñëîæåíèÿ, ÷òî ïðè îãðàíè÷åííîì ðàçìåðå êëåòêè ÿâëÿåòñÿ ñóùåñòâåííûì óñêîðåíèåì
âû÷èñëåíèÿ îïåðàöèè (12).
Àíàëîãè÷íûì ñïîñîáîì âîñïîëüçóåìñÿ ïðè ïîñòðîåíèè áûñòðîãî àëãîðèòìà
äëÿ âû÷èñëåíèÿ êëåòî÷íîé îïåðàöèè (12) íà îñíîâå ãèáðèäíîãî àëãîðèòìà (5)–(10).
 ýòîì ñëó÷àå âûðàæåíèÿ (5)–(7) ïðåîáðàçóþòñÿ ñëåäóþùèì îáðàçîì:
p zij ij
l
i
l
j
l
l
1 1 1 1
1
� � �
�
� ( )( ) ( ) ( )� �
�
,
p zij ij
l
i
l
j
l
l
2 2 2 2
1
� � �
�
� ( )( ) ( ) ( )� �
�
,
p zij ij
l
i
l
j
l
l
3 3 3 3
1
� � �
�
� ( )( ) ( ) ( )� �
�
,
p zij ij
l
i
l
j
l
l
4 4 4 4
1
� � �
�
� ( )( ) ( ) ( )� �
�
,
(17)
p zij ij
l
i
l
j
l
l
5 5 5 5
1
� � �
�
� ( )( ) ( ) ( )� �
�
,
p zij ij
l
i
l
j
l
l
6 6 6 6
1
� � �
�
� ( )( ) ( ) ( )� �
�
,
p zij ij
l
i
l
j
l
l
7 7 7 7
1
� � �
�
� ( )( ) ( ) ( )� �
�
, i j r, , , , /� 1 2 2� ; l � 1 2, , ,� � ,
ãäå
z s s s
ij
l
i k
l
k j
l
k
r
k j
l1
2 1
2
2
6
1
4
2 1
6( )
,
( )
,
( )
/
,
( )( )(� �
�
�
�� � s
i k
l
,
( ) )
2
2 ,
z a b b
ij
l
i k
l
k j
l
k
r
k
2
2 1 4 3 4 1 2 1
1
4
4 3
( )
,
( )
,
( )
/
( )(� �
� � � �
�
�� ,
( )
,
( ) )
2 1 2 1 4 1j
l
i k
la
� � �
� ,
z a b b
ij
l
i k
l
k j
l
k
r
k
3
2 1 4 2 4 2 1
1
4
4 2 2
( )
,
( )
,
( )
/
,
( )(� �
� � �
�
�� j
l
i k
la
� �
�
1 2 1 4
( )
,
( ) ) ,
z s s s
ij
l
i k
l
k j
l
k
r
k j
l4
2 1
3
2
7
1
4
2 1
7( )
,
( )
,
( )
/
,
( )( )(� �
�
�
�� � s
i k
l
,
( ) )
2
3 ,
(18)
z s s s
ij
l
i k
l
k j
l
k
r
k j
l5
2 1
1
2
5
1
4
2 1
5( )
,
( )
,
( )
/
,
( )( )(� �
�
�
�� � s
i k
l
,
( ) )
2
1 ,
z s b b
ij
l
i k
l
k j
l
k
r
k j
l6
2 1
4
4 2
1
4
4 2 2
( )
,
( )
,
( )
/
,
( )( )(� �
�
�
�� � s
i k
l
,
( ) )
2
4 ,
z a s s
ij
l
i k
l
k j
l
k
r
k j
l7
2 4 2 2
8
1
4
2 1
8( )
,
( )
,
( )
/
,
( )( )(� �
�
�
�� � a
i k
l
2 4,
( ) ) ,
à òàêæå
�
i
l
i k
l
k
r
i k
ls s1
2 1
2
1
4
2
2( )
,
( )
/
,
( )� �
�
�
� , �
j
l
k j
l
k
r
k j
ls s1
2
6
1
4
2 1
6( )
,
( )
/
,
( )� �
�
�� ,
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 57
�
i
l
i k
l
k
r
i k
la a2
2 1 4 3
1
4
2 1 4 1
( )
,
( )
/
,
( )� �
� �
�
� �� , �
j
l
k j
l
k
r
k j
lb b2
4 1 2 1
1
4
4 3 2 1
( )
,
( )
/
,
( )� �
� �
�
� �� ,
�
i
l
i k
l
k
r
i k
la a3
2 1 4 2
1
4
2 1 4
( )
,
( )
/
,
( )� �
� �
�
�� , �
j
l
k j
l
k j
l
k
r
b b3
4 2 1 4 2 2 1
1
4
( )
,
( )
,
( )
/
� �
� � �
�
� ,
�
i
l
i k
l
k
r
i k
ls s4
2 1
3
1
4
2
3( )
,
( )
/
,
( )� �
�
�
� , �
j
l
k j
l
k
r
k j
ls s4
2
7
1
4
2 1
7( )
,
( )
/
,
( )� �
�
�� ,
�
i
l
i k
l
k
r
i k
ls s5
2 1
1
1
4
2
1( )
,
( )
/
,
( )� �
�
�
� , �
j
l
k j
l
k
r
k j
ls s5
2
5
1
4
2 1
5( )
,
( )
/
,
( )� �
�
�� , (19)
�
i
l
i k
l
k
r
i k
ls s6
2 1
4
1
4
2
4( )
,
( )
/
,
( )� �
�
�
� , �
j
l
k j
l
k
r
k j
lb b6
4 2
1
4
4 2 2
( )
,
( )
/
,
( )� �
�
�� ,
�
i
l
i k
l
k
r
i k
la a7
2 4 2
1
4
2 4
( )
,
( )
/
,
( )� �
�
�
� , �
j
l
k j
l
k
r
k j
ls s7
2
8
1
4
2 1
8( )
,
( )
/
,
( )� �
�
�� ,
ïðè ýòîì
s a a
ik
l
i k
l
i k
l1
2 2 1 2 2
( )
,
( )
,
( )� �
�
, s b b
kj
l
k j
l
k j
l5
2 1 2 2 1 2 1
( )
,
( )
,
( )� �
� � �
,
s s a
ik
l
ik
l
i k
l2 1
2 1 2 1
( ) ( )
,
( )� �
� �
, s b s
kj
l
k j
l
kj
l6
2 2
5( )
,
( ) ( )� � ,
(20)
s a a
ik
l
i k
l
i k
l3
2 1 2 1 2 2 1
( )
,
( )
,
( )� �
� � �
, s b b
kj
l
k j
l
k j
l7
2 2 2 1 2
( )
,
( )
,
( )� �
�
,
s a s
ik
l
i k
l
ik
l4
2 1 2
2( )
,
( ) ( )� �
�
, s s b
kj
l
kj
l
k j
l8 6
2 2 1
( ) ( )
,
( )� �
�
,
ãäå i j r, , , , /� 1 2 2� ; k r� 1 2 4, ,... , / ; l � 1 2, , ,� �.
Äëÿ âû÷èñëåíèÿ ýëåìåíòîâ ìàòðèö T i (i � 1 2 3, , ) è D èñïîëüçóþòñÿ ñîîòíîøåíèÿ
t p pij ij ij
1 1 2� � , t t pij ij ij
2 1 4� � ,
t p pij ij ij
3 5 6� � , i j r, , , , /� 1 2 2� , (21)
à òàêæå
d c p pi j i j ij ij2 1 2 1 2 1 2 1
2 3
� � � �� � �, , ,
d c t ti j i j ij ij2 1 2 2 1 2
1 3
� �� � �, , , (22)
d c t pi j i j ij ij2 2 1 2 2 1
2 7
, ,� �� � � ,
d c t pi j i j ij ij2 2 2 2
2 5
, ,� � � , i j r, , ,... , /� 1 2 2 .
Ìóëüòèïëèêàòèâíàÿ, àääèòèâíàÿ è îáùàÿ âû÷èñëèòåëüíàÿ ñëîæíîñòè àëãîðèò-
ìà (17)–(22) ñîîòâåòñòâåííî îïðåäåëÿþòñÿ ôîðìóëàìè
W W W r rì ì ì� � � �( ) ( ) ( , , )17 18 3 20 4375 175� (îïåðàöèé óìíîæåíèÿ),
W W r r r r ra a� � � � � � ��( ) ( , , ) ( , )17 22 3 2 2 213125 175 175 7 2� � � � � �( ) ,� 1 3 5 2r
� � � � �2 75 13125 5 5 7 0 752 3 2 2, ( , , ) ,r r r r r� (îïåðàöèé ñëîæåíèÿ),
W W W r r r rîáù ì a� � � � � ��( , , ) ,175 7 25 7 0 753 2 2 (îïåðàöèé óìíîæåíèÿ / ñëîæåíèÿ).
Ïîñêîëüêó âû÷èñëåíèÿ (21), (22) âûïîëíÿþòñÿ òîëüêî îäèí ðàç, âûèãðûø ïî
àääèòèâíîé ñëîæíîñòè àëãîðèòìà (17)–(22) ñîñòàâëÿåò � �� � �( , , )2 75 0 752 2r r îïå-
ðàöèé ñëîæåíèÿ îòíîñèòåëüíî ñëîæíîñòè âû÷èñëåíèÿ îïåðàöèè (12) ñ ïîìîùüþ
àëãîðèòìà (5)–(10).
58 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4
Òàêèì îáðàçîì, ðàññìîòðåííûå âûøå ãèáðèäíûå àëãîðèòìû (1)–(4) è (5)–(10)
èìåþò ïðàêòè÷åñêóþ öåííîñòü è ðàñøèðÿþò ñåìåéñòâî àëãîðèòìîâ óìíîæåíèÿ
ìàòðèö. Íàèìåíüøàÿ îïåðàöèîííàÿ ñëîæíîñòü è ðåãóëÿðíîñòü âû÷èñëåíèé ýòèõ àë-
ãîðèòìîâ, à òàêæå ïîñòðîåííûõ íà èõ îñíîâå áûñòðûõ àëãîðèòìîâ (13)–(16)
è (17)–(22) äëÿ áàçîâîé îïåðàöèè êëåòî÷íûõ ìåòîäîâ ËÀ ñîçäàþò âñå ïðåäïîñûëêè
äëÿ èõ ýôôåêòèâíîé ðåàëèçàöèè íà ðàçëè÷íûõ ïàðàëëåëüíûõ âû÷èñëèòåëüíûõ
ñèñòåìàõ è ïðîöåññîðíûõ ìàññèâàõ ñ ñèñòîëè÷åñêîé îðãàíèçàöèåé âû÷èñëåíèé.
CÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Ô à ä ä å å â Ä . Ê . , Ô à ä ä å å â à  . Í . Âû÷èñëèòåëüíûå ìåòîäû ëèíåéíîé àëãåáðû. — Ì.; Ë.:
Ôèçìàòãèç, 1963. — 734 ñ.
2. Ñ â å ð õ á î ë ü ø è å èíòåãðàëüíûå ñõåìû è ñîâðåìåííàÿ îáðàáîòêà ñèãíàëîâ / Ïîä ðåä. Ñ. Ãóíà,
Õ. Óàéòõàóñà, Ò. Êàéëîòà. — Ì.: Ðàäèî è ñâÿçü, 1989. — 472 ñ.
3.  î å â î ä è í À .  . Î êëàññå êëåòî÷íûõ àëãîðèòìîâ è åãî ñâîéñòâàõ // Âîïð. êèáåðíåòèêè. — 1988.
— ¹ 135. — Ñ. 50–64.
4. Ë û ñ à í î â Ñ . Þ . Êëåòî÷íûå ìåòîäû ðåøåíèÿ çàäà÷ ëèíåéíîé àëãåáðû // Òàì æå. — Ñ. 64–73.
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. S t r a s s e n V . Gaussian elimination is not optimal // Numer. Math. — 1969. — 13. — P. 354–356.
7. 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.
8. P a n V . Y a . Strassen’s algorithm is not optimal // Proc. 19th IEEE Symposium on Foundation of Com-
puter Science, 1978. — P. 166–176.
9. B i n i D . , C a p o v a n i M . , L o t t i G . , R o m a n i F . Î ( ),n2 7799 complexity for approximate matrix
multiplication // Information Proc. Letters. — 1979. — 8. — P. 234–235.
10. S c h ��î n h a g e A . Partial and total matrix multiplication // SIAM J. Comput. — 1981. — 10, No. 3. —
P. 434–435.
11. C o p p e r s m i t h D . , W i n o g r a d S . On the asymptotic complexity of matrix multiplication // SIAM
J. Comput. — 1982. – 11, No. 3. — P. 472–492.
12. C o p p e r s m i t h D . , W i n o g r a d S . Matrix multiplication via arithmetic progressions // J. of Sym-
bolic Comput., 1990, No. 9. — P. 251–280.
13. Å ë ô è ì î â à Ë . Ä . , Ê à ï è ò î í î â à Þ . Â . Áûñòðûé àëãîðèòì äëÿ óìíîæåíèÿ ìàòðèö è åãî
ýôôåêòèâíàÿ ðåàëèçàöèÿ íà ñèñòîëè÷åñêèõ ìàññèâàõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2001.
— ¹ 1. — Ñ. 135–150.
14. Å ë ô è ì î â à Ë . Ä . Áûñòðûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö // Òàì æå. — 2008. — ¹ 3. —
Ñ. 55–59.
15. Å ë ô è ì î â à Ë . Ä . Ñìåøàííûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö // Òàì æå. — 2009. — ¹ 1.
— Ñ. 22–27.
16. J e l f i m o v a L . A new fast systolic array for modified Winograd algorithm // Proc. Sevens Int. Work-
shop on Parallel Processing by Cellular Automata and Array, PARCELLA-96 (Berlin, Germany,
Sept. 1996). — Berlin: Akad. Verlag. — 1996. — 96. — P. 157–164.
17. Å ë ô è ì î â à Ë . Ä . , Ê à ï è ò î í î â à Þ . Â . Èíòåãðèðîâàííûé ïîäõîä ê ïðîåêòèðîâàíèþ ïðî-
öåññîðíûõ ìàññèâîâ ñ ñèñòîëè÷åñêîé îðãàíèçàöèåé âû÷èñëåíèé // Êèáåðíåòèêà è ñèñòåìíûé
àíàëèç. — 2002. — ¹ 6. — Ñ. 3–15.
Ïîñòóïèëà 09.07.2009
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 4 59
|
| id | nasplib_isofts_kiev_ua-123456789-45243 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T17:49:58Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Елфимова, Л.Д. 2013-06-10T16:21:56Z 2013-06-10T16:21:56Z 2010 Быстрые гибридные алгоритмы умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2010. — № 4. — С. 49-59. — Бібліогр.: 17 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45243 681.322.012 Запропоновано новi гiбриднi алгоритми множення матриць, якi вiдрiзняються вiд вiдомих найменшою операцiйною cкладнiстю. Наведено оцiнки обчислювальної складностi представлених алгоритмiв. The paper proposes new hybrid algorithms of matrix multiplication with the lowest computational complexity as compared with well-known matrix multiplication algorithms. The computational complexity of the above-mentioned algorithms is estimated. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Быстрые гибридные алгоритмы умножения матриц Швидкi гiбриднi алгоритми множення матриць Fast hybrid matrix multiplication algorithms Article published earlier |
| spellingShingle | Быстрые гибридные алгоритмы умножения матриц Елфимова, Л.Д. Кибернетика |
| title | Быстрые гибридные алгоритмы умножения матриц |
| title_alt | Швидкi гiбриднi алгоритми множення матриць 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/45243 |
| work_keys_str_mv | AT elfimovald bystryegibridnyealgoritmyumnoženiâmatric AT elfimovald švidkigibridnialgoritmimnožennâmatricʹ AT elfimovald fasthybridmatrixmultiplicationalgorithms |