Объединенный клеточный метод умножения матриц

Запропоновано об’єднаний клітинний метод множення матриць, який являє собою гібрид трьох методів: рекурсивних методів Штрассена, Лейдермана та швидкого клітинного методу множення матриць. Взаємодія трьох методів забезпечує найвищий порівняно з відомими методами відсоток мінімізації (37 %) мультиплік...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Кибернетика и системный анализ
Datum:	2013
1. Verfasser:	Елфимова, Л.Д.
Format:	Artikel
Sprache:	Russisch
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Schlagworte:	Кибернетика
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/86268
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Объединенный клеточный метод умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2013. — Т. 49, № 5. — С. 28-37. — Бібліогр.: 6 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859583178767859712
author	Елфимова, Л.Д.
author_facet	Елфимова, Л.Д.
citation_txt	Объединенный клеточный метод умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2013. — Т. 49, № 5. — С. 28-37. — Бібліогр.: 6 назв. — рос.
collection	DSpace DC
container_title	Кибернетика и системный анализ
description	Запропоновано об’єднаний клітинний метод множення матриць, який являє собою гібрид трьох методів: рекурсивних методів Штрассена, Лейдермана та швидкого клітинного методу множення матриць. Взаємодія трьох методів забезпечує найвищий порівняно з відомими методами відсоток мінімізації (37 %) мультиплікативної, адитивної та загальної складності клітинних аналогів відомих алгоритмів множення матриць. Оцінку обчислювальної складності об’єднаного методу наведено на прикладі отримання клітинного аналога традиційного алгоритму множення матриць. A unified cellular method of matrix multiplication is proposed that is a hybrid of three methods, namely, Strassen’s and Laderman’s recursive methods and a fast cellular method for matrix multiplication. The interaction of these three methods provides the highest (in comparison with well-known methods) percentage (equal to 37%) of minimizing the multiplicative, additive, and overall complexities of cellular analogues of well-known matrix multiplication algorithms. The estimation of the computational complexity of the unified method is illustrated by the example of a model of obtaining a cellular analogue of the traditional matrix multiplication algorithm.
first_indexed	2025-11-27T08:22:42Z
format	Article
fulltext	ÓÄÊ 681.322.012 Ë.Ä. ÅËÔÈÌÎÂÀ ÎÁÚÅÄÈÍÅÍÍÛÉ ÊËÅÒÎ×ÍÛÉ ÌÅÒÎÄ ÓÌÍÎÆÅÍÈß ÌÀÒÐÈÖ Êëþ÷åâûå ñëîâà: ëèíåéíàÿ àëãåáðà, êëåòî÷íûå ìåòîäû óìíîæåíèÿ ìàòðèö, ðå- êóðñèâíûå ìåòîäû Øòðàññåíà è Ëåéäåðìàíà, àëãîðèòìû óìíîæåíèÿ ìàòðèö. Â íàñòîÿùåå âðåìÿ ðàçðàáîòàíî ñåìåéñòâî êëåòî÷íûõ ìåòîäîâ óìíîæåíèÿ ìàò- ðèö, âêëþ÷àþùåå äâà áûñòðûõ è äâà ñìåøàííûõ ìåòîäà [1–3], ïîçâîëÿþùèõ âàðüèðîâàòü ðàçìåð êëåòîê, íà êîòîðûå äåêîìïîçèðóþòñÿ èñõîäíûå ìàòðèöû, è ïîëó÷àòü êëåòî÷íûå àíàëîãè èçâåñòíûõ àëãîðèòìîâ óìíîæåíèÿ ìàòðèö ñ ìè- íèìèçèðîâàííîé âû÷èñëèòåëüíîé ñëîæíîñòüþ. Áûñòðûå êëåòî÷íûå ìåòîäû óìíîæåíèÿ ìàòðèö ïîðÿäêà n r� �2� [1] è n r� �3� [3] (ãäå � �1, r — ðàçìåð êëåòêè), îáåñïå÷èâàþò ìèíèìèçàöèþ ìóëüòèïëèêàòèâíîé, àääèòèâíîé è îáùåé ñëîæíîñòåé ìàòðè÷íûõ àëãîðèòìîâ ñîîòâåòñòâåííî íà 12,5 è 15%. Ñìåøàííûå êëåòî÷íûå ìåòîäû [2, 3] ÿâëÿþòñÿ ãèáðèäàìè äâóõ ìåòîäîâ. Ïåðâûé ñìåøàí- íûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö ïîðÿäêà n rq� � �2 � ( , )q � �1 1� [2] ñî÷åòàåò ðåêóðñèâíûé ìåòîä Øòðàññåíà [4] ñ áûñòðûì êëåòî÷íûì ìåòîäîì óìíîæåíèÿ ìàòðèö [1], âçàèìîäåéñòâèå êîòîðûõ ïðèâîäèò ê ìèíèìèçàöèè óêà- çàííûõ ñëîæíîñòåé ìàòðè÷íûõ àëãîðèòìîâ íà 25 %. Âòîðîé ñìåøàííûé êëå- òî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö ïîðÿäêà n rq� �3 � ( , )q � �1 1� [3] ñî÷åòàåò ðåêóðñèâíûé ìåòîä Ëåéäåðìàíà [5] ñ áûñòðûì êëåòî÷íûì ìåòîäîì óìíîæå- íèÿ ìàòðèö [3], ÷òî äàåò âîçìîæíîñòü ìèíèìèçèðîâàòü ìóëüòèïëèêàòèâíóþ, àääèòèâíóþ è îáùóþ ñëîæíîñòè ìàòðè÷íûõ àëãîðèòìîâ íà 28%. Öåëüþ äàííîé ðàáîòû ÿâëÿåòñÿ îïòèìèçàöèÿ âû÷èñëèòåëüíîé ñëîæíîñòè êëå- òî÷íûõ àíàëîãîâ èçâåñòíûõ àëãîðèòìîâ óìíîæåíèÿ ìàòðèö. Äàëåå ðàññìîòðåí îáúåäèíåííûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö ïîðÿäêà n rq� � �2 3� � ( , , )� �� 0 1 1q , ïðåäñòàâëÿþùèé ñîáîé ãèáðèä òðåõ ìåòîäîâ: ðåêóðñèâíûõ ìåòîäîâ Øòðàññåíà, Ëåéäåðìàíà è áûñòðîãî êëåòî÷íîãî ìåòîäà óìíîæåíèÿ ìàò- ðèö [3]. Òàêîå îáúåäèíåíèå äîñòèãàåòñÿ ñî÷åòàíèåì ìåòîäà Øòðàññåíà ñî ñìå- øàííûì êëåòî÷íûì ìåòîäîì óìíîæåíèÿ ìàòðèö [3], âçàèìîäåéñòâèå êîòîðûõ îáåñïå÷èâàåò íàèâûñøèé ïî ñðàâíåíèþ ñ èçâåñòíûìè êëåòî÷íûìè ìåòîäàìè, ïðîöåíò ìèíèìèçàöèè (37%) ìóëüòèïëèêàòèâíîé, àääèòèâíîé è îáùåé ñëîæíîñ- òåé êëåòî÷íûõ àíàëîãîâ èçâåñòíûõ àëãîðèòìîâ óìíîæåíèÿ ìàòðèö. Îöåíêà âû- ÷èñëèòåëüíîé ñëîæíîñòè ïðåäëàãàåìîãî ìåòîäà äàíà íà ïðèìåðå ïîëó÷åíèÿ êëå- òî÷íîãî àíàëîãà òðàäèöèîííîãî àëãîðèòìà [6]. Ðàññìîòðèì îáúåäèíåííûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö ïîðÿäêà n rq� � �2 3� � ( , , )� �� 0 1 1q . Ïóñòü A, B è C A B� � — òðè ( )n n� -ìàòðèöû, ãäå n rq� � �2 3� � (� � 0 , q �1, � �1, r — ðàçìåð êëåòêè). Èñõîäíûå ìàòðèöû A è B, ïðåäñòàâëåííûå íà ðèñ. 1 è 2, äåêîìïîçèðóþòñÿ íà êëåòêè Aij è Bij çàäàííîãî ïîðÿäêà r, â ðåçóëüòàòå ÷åãî îáðàçóþòñÿ êëåòî÷íûå ( )m m� -ìàòðèöû, ãäå m n r� / , l m� / 2, l � 3�, � � m / 6, i j m, , , ...,�1 2 . Êàæäàÿ ïî- ëó÷åííàÿ êëåòî÷íàÿ ìàòðèöà A è B ïîðÿäêà m ðàçáèâàåòñÿ â ñâîþ î÷åðåäü íà 36 ðàâíûõ êëåòî÷íûõ ïîäìàòðèö Aij �� è Bij �� ïîðÿäêà �, ãäå íèæíèå èíäåêñû i j, , , ...,�1 2 6 ïîêàçûâàþò ìåñòî ýòèõ ïîäìàòðèö â ïîëíîé ( )m m� -ìàòðèöå, à âåðõ- íèå èíäåêñû �� — ÷èñëî ìàòðè÷íûõ ñòðîê è ñòîëáöîâ óêàçàííûõ ïîäìàòðèö. 28 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 © Ë.Ä. Åëôèìîâà, 2013 Êðîìå òîãî, êàæäàÿ êëåòî÷íàÿ ( )m m� -ìàòðèöà A è B ðàçáèâàåòñÿ íà ÷åòûðå ðàâ- íûå êëåòî÷íûå ïîäìàòðèöû ïîðÿäêà l � 3�, îáîçíà÷åííûå A A A All ll ll ll 11 12 21 22 , , , è B B B Bll ll ll ll 11 12 21 22 , , , (ñì. ðèñ. 1, 2), ãäå íèæíèå èíäåêñû i j, ,�1 2 ïîêàçûâàþò ìåñòî ýòèõ ïîäìàòðèö â ïîëíûõ ( )m m� -ìàòðèöàõ, à âåðõíèå ll — ÷èñëî ìàòðè÷íûõ ñòðîê è ñòîëáöîâ óêàçàííûõ ïîäìàòðèö. Ïðîèçâåäåíèåì êëåòî÷íûõ ìàòðèö A è B ÿâëÿåòñÿ ìàòðèöà C (ðèñ. 3), èìåþùàÿ àíàëîãè÷íóþ êàæäîìó ñîìíîæèòåëþ êëå- òî÷íóþ ñòðóêòóðó. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 29 llll mmmmmmmm m m m m m m llll AA AAAAAAA AAAAAA AAAAAAA AAAAAA AAAAAAA AAAAAA AAAAAAA AAAAAA AAAAAAA AAAAAA AAAAAAA AAAAAA AAAAAAA A AA 2221 ,5,4,3,2,,1, 666564636261 ,55,54,53,52,5,51,5 565554535251 ,45,44,43,42,4,41,4 464544434241 ,35,34,33,32,3,31,3 363534333231 ,25,24,23,22,2,21,2 262524232221 5,4,3,2,1 161514131211 15,14,13,12,1111 1211 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Ðèñ. 1 r r llll mmmmmmmm m m m m m m llll BB BBBBBBB BBBBBB BBBBBBB BBBBBB BBBBBBB BBBBBB BBBBBBB BBBBBB BBBBBBB BBBBBB BBBBBBB BBBBBB BBBBBBB B BB 2221 ,5,4,3,2,,1, 666564636261 ,55,54,53,52,5,51,5 565554535251 ,45,44,43,42,4,41,4 464544434241 ,35,34,33,32,3,31,3 363534333231 ,25,24,23,22,2,21,2 262524232221 5,4,3,2,1 161514131211 15,14,13,12,1111 1211 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Ðèñ. 2 r r Ïðè òàêîì ðàçáèåíèè ìàòðèö âçàèìîäåéñòâèå òðåõ ìåòîäîâ îñóùåñòâëÿåòñÿ ñëåäóþùèì îáðàçîì. Ìåòîä Øòðàññåíà îïåðèðóåò êëåòî÷íûìè ïîäìàòðèöàìè Aij ll , Bij ll ïîðÿäêà l � 3�, ìåòîä Ëåéäåðìàíà — êëåòî÷íûìè ïîäìàòðèöàìè Aij �� , Bij �� ïîðÿäêà �, áûñòðûé êëåòî÷íûé ìåòîä [3] —ïîäìàòðèöàìè Aij , Bij ïîðÿäêà r. Ðàçìåð êëåòêè r çàâèñèò îò âûáðàííîãî âíóòðåííåãî àëãîðèòìà, â êà÷åñòâå êîòî- ðîãî èñïîëüçóþòñÿ èçâåñòíûå àëãîðèòìû óìíîæåíèÿ ìàòðèö, îïåðèðóþùèå ÷èñëàìè. Ðàññìîòðèì ïåðâûé øàã ðåêóðñèè ìåòîäîâ Øòðàññåíà è Ëåéäåðìàíà. Â ýòîì ñëó÷àå ìåòîä Øòðàññåíà â ìàòðè÷íîì âèäå ïðèìåíèòåëüíî ê êëåòî÷íûì ïîäìàò- ðèöàì ïîðÿäêà l èìååò ñëåäóþùèé âèä: Z A A B Bll ll ll ll1 11 22 11 22 � � �( )( ) , Z A A Bll ll ll2 21 22 11 � �( ) , Z A B Bll ll ll3 11 12 22 � ( ), Z A B Bll ll ll4 22 21 11 � ( ), Z A A Bll ll ll5 11 12 22 � �( ) , (1) Z A A B Bll ll ll ll6 21 11 11 12 � �( )( ), Z A A B Bll ll ll ll7 12 22 21 22 � �( )( ) ; C Z Z Z Zll 11 1 4 5 7� � � , C Z Zll 12 3 5� � , (2) C Z Zll 21 2 4� � , C Z Z Z Zll 22 1 2 3 6� � � . Êàê îòìå÷àëîñü âûøå, âû÷èñëåíèå ìàòðè÷íûõ ïðîèçâåäåíèé Z Z1 7� �� (1) îñóùåñòâëÿåòñÿ ñ èñïîëüçîâàíèåì ñìåøàííîãî êëåòî÷íîãî ìåòîäà óìíîæåíèÿ ìàòðèö [3], âêëþ÷àþùåãî ìåòîä Ëåéäåðìàíà è áûñòðûé êëåòî÷íûé ìåòîä [3]. Òà- êîå ñî÷åòàíèå òðåõ ìåòîäîâ îáðàçóåò îáúåäèíåííûé êëåòî÷íûé ìåòîä óìíîæå- íèÿ ìàòðèö, êîòîðûé ñîñòîèò èç ïÿòè ýòàïîâ è ôîðìàëèçóåòñÿ ñëåäóþùèì îáðàçîì. Îáîçíà÷èì X i è Y i ( i �1 2 5, , ..., ) ñóììû êëåòî÷íûõ ( )l l� -ïîäìàòðèö, âõîäÿ- ùèå â (1): X A All ll1 11 22 � �( ), Y B Bll ll1 11 22 � �( ), 30 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 llll mmmmmmmm m m m m m m llll CC CCCCCCC CCCCCC CCCCCCC CCCCCC CCCCCCC CCCCCC CCCCCCC CCCCCC CCCCCCC CCCCCC CCCCCCC CCCCCC CCCCCCC C CC 2221 ,5,4,3,2,,1, 666564636261 ,55,54,53,52,5,51,5 565554535251 ,45,44,43,42,4,41,4 464544434241 ,35,34,33,32,3,31,3 363534333231 ,25,24,23,22,2,21,2 262524232221 5,4,3,2,1 161514131211 15,14,13,12,1111 1211 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � � �� Ðèñ. 3 r r X A All ll2 21 22 � �( ), Y B Bll ll2 12 22 � ( ), X A All ll3 11 12 � �( ), Y B Bll ll3 21 11 � ( ), (3) X A All ll4 21 11 � ( ), Y B Bll ll4 11 12 � �( ), X A All ll5 12 22 � ( ), Y B Bll ll5 21 22 � �( ). Ýòàï 1. Îïåðèðóÿ ( )r r� -êëåòêàìè è ïðèìåíÿÿ èçâåñòíóþ îïåðàöèþ ìàòðè÷- íîãî ñëîæåíèÿ [6], âû÷èñëÿåì ìàòðè÷íûå ñóììû ñîãëàñíî (3) ïî ñëåäóþùèì ôîðìóëàì: X A Aij ij i j 1 3 3� � � �( ),� � , Y B Bij ij i j 1 3 3� � � �( ),� � , X A Aij i j i j 2 3 3 3� �� ( ), ,� � � , Y B Bij i j i j 2 3 3 3� � � �( ), ,� � � , X A Aij ij i j 3 3� � �( ), � , Y B Bij i j ij 3 3� �( ),� , (4) X A Aij i j ij 4 3� �( ),� , Y B Bij ij i j 4 3� � �( ), � , X A Aij i j i j 5 3 3 3� � � �( ), ,� � � , Y B Bij i j i j 5 3 3 3� �� ( ), ,� � � , ãäå i j, , ...,�1 3�. Ýòàï 2. Èñïîëüçóÿ îáîçíà÷åíèÿ (3), ïðåäñòàâëÿåì ñåìü ìàòðè÷íûõ ïðîèçâå- äåíèé Z Z1 7� �� ñîãëàñíî (1) â ñëåäóþùåì âèäå: Z X Y Z X B Z A Y Z A Y Z X B ll ll ll l 1 1 1 2 2 11 3 11 2 4 22 3 5 3 22 � � � � � , , , , l Z X Y Z X Y, , .6 4 4 7 5 5� � (5) Äëÿ íàõîæäåíèÿ ïåðâîãî ìàòðè÷íîãî ïðîèçâåäåíèÿ Z X Y1 1 1� èñïîëüçóþò- ñÿ ïðåäñòàâëåííûå íà ðèñ. 4 è 5 êëåòî÷íûå ïîäìàòðèöû-îïåðàíäû { }X ij 1 è { }Yij 1 ïîðÿäêà 3�. Ïðîèçâåäåíèåì êëåòî÷íûõ ïîäìàòðèö X 1 è Y 1 ÿâëÿåòñÿ ìàòðèöà Z1 (ðèñ. 6), èìåþùàÿ àíàëîãè÷íóþ êàæäîìó ñîìíîæèòåëþ êëåòî÷íóþ ñòðóêòóðó. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 31 � � � � � � � � � � � � � � � � � � � � � � � � � � � � 1 3,3 1 12, 1 2, 1 1, 11 1 )(1 33 )(1 32 )(1 31 1 3,12 1 12,12 1 2,12 1 1,12 1 ,12 1 1,12 1 3,2 1 12,2 1 2,2 1 1,2 1 ,2 1 1,2 )(1 23 )(1 22 )(1 21 1 3,1 1 12,1 1 2,1 1 1,1 1 ,1 1 1,1 1 3, 1 12, 1 2, 1 1, 11 1 )(1 13 )(1 12 )(1 11 1 3,1 1 12,1 1 2,1 1 1,1 1 1 1 11 1 �� XXXXXX XXX XXXXXX XXXXXX XXX XXXXXX XXXXXX XXX XXXXXX X mmmmm �� Ðèñ. 4 r r Ñîãëàñíî ñìåøàííîìó êëåòî÷íîìó ìåòîäó [3] îïðåäåëÿåì ìàòðè÷íûå ñóììû N ij t è Pij t ( t �1 2 14, , ..., ) ïî ñëåäóþùèì ôîðìóëàì: N X X X X X Xij ij i j i j i j i j 1 1 1 2 1 1 1 2 � � � � � � � � �( , , , ,� � � � � � i j i j X , , ) � � �� 1 2 2 1 , N X Xij ij i j 2 1 1� �( ) ,� , N X X Xij ij i j i j 3 1 1 1� � �� ( ) , ,� � � , N X Xij i j i j 4 1 1� �� ( ) , ,� � � , N X X Xij ij i j i j 5 1 2 1 2 1� � �� ( ) , ,� � � , N X Xij ij i j 6 1 2 1� � �( ) ,� , N X Xij i j i j 7 2 1 2 1� �� ( ) , ,� � � , (6) N X X X X X Xij ij i j i j i j i j 8 1 1 2 1 1 2 1� � � � � � � � � ( , , , ,� � � � � � 2 1 2 1 � � �� i j i j X , , ) , 32 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 � � � � � � � � � � � � � � � � � � � � � � � � � 1 3,3 1 12, 1 2, 1 1, 11 1 )(1 33 )(1 32 )(1 31 1 3,12 1 12,12 1 2,12 1 1,12 1 ,12 1 1,12 1 3,2 1 12,2 1 2,2 1 1,2 1 ,2 1 1,2 )(1 23 )(1 22 )(1 21 1 3,1 1 12,1 1 2,1 1 1,1 1 ,1 1 1,1 1 3, 1 12, 1 2, 1 1, 11 1 )(1 13 )(1 12 )(1 11 1 3,1 1 12,1 1 2,1 1 1,1 1 1 1 11 1 �� YYYYYY YYY YYYYYY YYYYYY YYY YYYYYY YYYYYY YYY YYYYYY Y mmmmm �� Ðèñ. 5 r r � � � � � � � � � � � � � � � � � � � � � � � � � 1 3,3 1 12, 1 2, 1 1, 11 1 )(1 33 )(1 32 )(1 31 1 3,12 1 12,12 1 2,12 1 1,12 1 ,12 1 1,12 1 3,2 1 12,2 1 2,2 1 1,2 1 ,2 1 1,2 )(1 23 )(1 22 )(1 21 1 3,1 1 12,1 1 2,1 1 1,1 1 ,1 1 1,1 1 3, 1 12, 1 2, 1 1, 11 1 )(1 13 )(1 12 )(1 11 1 3,1 1 12,1 1 2,1 1 1,1 1 1 1 11 1 �� ZZZZZZ ZZZ ZZZZZZ ZZZZZZ ZZZ ZZZZZZ ZZZZZZ ZZZ ZZZZZZ Z mmmmm �� Ðèñ. 6 r r N X X Xij i j i j i j 9 2 1 2 1 2 2 1� � �� ( ) , , ,� � � � � , N X Xij i j i j 10 2 1 2 2 1� � � �( ) , ,� � � , N X Xij i j i j 11 2 1 2 2 1� �� ( ) , ,� � � � , N X X Xij i j i j i j 12 2 1 1 2 1� � �� ( ) , , ,� � � � � , N X Xij i j i j 13 2 1 2 1� � � �( ) , ,� � � , N X Xij i j i j 14 1 2 1� �� ( ) , ,� � � � , ãäå i j, , , ..., ;�1 2 � P Y Yij i j i j 1 1 1� �� ( ) , ,� � � , P Y Y Y Y Y Yij ij i j i j i j i j 2 1 1 1 1 2 1� � � � � � � � �( , , , ,� � � � � � 2 1 2 2 1 � � �� i j i j Y , , ), P Y Y Yij ij i j i j 3 1 1 1� �� ( ) , ,� � � , P Y Yij ij i j 4 1 1� � �( ) ,� , P Y Y Yij ij i j i j 5 1 2 1 2 1� �� ( ) , ,� � � , P Y Yij i j i j 6 2 1 2 1� � � �( ) , ,� � � , P Y Yij ij i j 7 1 2 1� � �( ) , � , P Y Y Y Y Yij ij i j i j i j i j 8 1 2 1 1 1 2 1� � � � � � � � � ( , , , ,� � � � � � Y Y i j i j2 1 2 1 � � �� , , ), (7) P Y Y Yij i j i j i j 9 1 2 1 2 1� � � � � � �( ) , , ,� � � � � , P Y Yij i j i j 10 1 2 1� � � � �( ) , ,� � � � , P Y Yij i j i j 11 2 1 2 1� �� ( ) , ,� � � , P Y Y Yij i j i j i j 12 2 1 2 1 2 2 1� � � � � � �( ) , , ,� � � � � , P Y Yij i j i j 13 2 1 2 2 1� � � � �( ) , ,� � � � , P Y Yij i j i j 14 2 1 2 2 1� �� ( ) , ,� � � , ãäå i j, , , ...,�1 2 �. Ýòàï 3. Â ñîîòâåòñòâèè ñî ñìåøàííûì êëåòî÷íûì ìåòîäîì [3], âêëþ÷àþ- ùèì ìåòîä Ëåéäåðìàíà, âû÷èñëåíèå 23 ìàòðè÷íûõ ïðîèçâåäåíèé S S1 23, ..., îñó- ùåñòâëÿåì ïî ñëåäóþùèì ôîðìóëàì: S N Y1 1 22 1� ( )�� , S N P2 2 1� , S X P3 22 1 2� ( )�� , S N P4 3 3� , S N P5 4 4� , S X Y6 11 1 11 1� ( ) ( )�� , S N P7 5 5� , S N P8 6 6� , S N P9 7 7� , S N Y10 8 23 1� ( )�� , S X P11 1 8� ( )�� , S N P12 9 9� , S N P13 10 10� , S X Y14 13 1 31 1� ( ) ( )�� , (8) S N P15 11 11� , S N P16 12 12� , S N P17 13 13� , S N P18 14 14� , S X Y19 12 1 21 1� ( ) ( )�� , S X Y20 23 1 32 1� ( ) ( )�� , S X Y21 21 1 13 1� ( ) ( )�� , S X Y22 31 1 12 1� ( ) ( )�� , S X Y23 33 1 33 1� ( ) ( )�� . Äëÿ ðåàëèçàöèè êàæäîãî èç óêàçàííûõ ìàòðè÷íûõ ïðîèçâåäåíèé ïðèìåíÿåì áûñòðûé êëåòî÷íûé ìåòîä [3]. Äëÿ âû÷èñëåíèÿ ïåðâîãî ìàòðè÷íîãî ïðîèçâåäå- íèÿ S N Y1 1 22 1� � ( )�� èñïîëüçóþòñÿ ïðåäñòàâëåííûå íà ðèñ. 7 ïîäìàòðèöû-îïå- ðàíäû { }N ij 1 è { }Yij 1 ïîðÿäêà �. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 33 � � � � � � � � � � � � � � � � � � � � � � � � � � � � � 11 2 1 1 1 2 1 22 1 21 1 1 1 12 1 11 11 2 1 1 1 2 1 22 1 21 1 1 1 12 1 11 11 2 1 1 1 2 1 22 1 21 1 1 1 12 1 11 1(1 22 1 �� SSS SSS SSS YYY YYY YYY NNN NNN NNN SYN � �� Ðèñ. 7 r r r r r r Ñîãëàñíî áûñòðîìó êëåòî÷íîìó ìåòîäó [3] âíà÷àëå îïðåäåëÿåì ìàòðè÷íûå êîýôôèöèåíòû R ik S è F kj S (s �1 14, ..., ): R N N N Nik 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� � � , , , , N N Ni k i k i k3 1 3 1 1 3 3 2 1 3 3 1 , , , , R N N ik i k i k 2 3 2 3 2 1 3 1 3 2 1� , , , R N N N ik i k i k i k 3 3 2 3 2 1 3 1 3 2 1 3 1 3 1 1� � � , , , , R N N ik i k i k 4 3 1 3 2 1 3 1 3 1 1� � , , , R N N N ik i k i k i k 5 3 2 3 2 1 3 3 2 1 3 3 1 1� � � , , , , R N N ik i k i k 6 3 2 3 2 1 3 3 2 1� � , , , R N N ik i k i k 7 3 3 2 1 3 3 1 1� � , , , (9) R N N N Nik 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� � � , , , , N N Ni k i k i k3 1 3 1 3 3 2 1 3 3 1 1 , , , , R N N N ik i k i k i k 9 3 2 3 1 3 3 1 1 3 3 1� � � , , , , R N N ik i k i k 10 3 2 3 1 3 3 1� , , , R N N ik i k i k 11 3 3 1 1 3 3 1� � , , , R N N N ik i k i k i k 12 3 2 3 1 3 1 3 1 1 3 1 3 1� � � , , , , R N N ik i k i k 13 3 2 3 1 3 1 3 1� , , , R N N ik i k i k 14 3 1 3 1 1 3 1 3 1� � , , , ãäå i j k p, , , , ...,�1 2 ; p n r� /18 ; F Y Y kj k j k j 1 3 2 3 1 1 3 1 3 1 1� � , , , F Y Y Y Y kj k j k j k j k j 2 3 2 3 2 1 3 2 3 1 1 3 1 3 2 1 3 1 3 � � � , , , , � 1 1 3 1 3 1 3 3 2 1 3 3 1Y Y Y k j k j k j, , , , F Y Y Y kj k j k j k j 3 3 2 3 2 1 3 2 3 1 1 3 1 3 1 1� � , , , , F Y Y kj k j k j 4 3 2 3 2 1 3 2 3 1 1� � , , , F Y Y Y kj k j k j k j 5 3 2 3 2 1 3 2 3 1 3 1 3 1� � , , , , F Y Y kj k j k j 6 3 2 3 1 3 1 3 1� , , , F Y Y kj k j k j 7 3 2 3 2 1 3 2 3 1� � , , , (10) F Y Y Y Ykj k j k j k j k j 8 3 2 3 2 1 3 2 3 1 3 1 3 2 1 3 1 3 1� � � , , , , 1 3 1 3 1 3 3 2 1 3 3 1 1 � Y Y Yk j k j k j, , , , F Y Y Y kj k j k j k j 9 3 1 3 1 1 3 3 2 1 3 3 1 1� � , , , , F Y Y kj k j k j 10 3 1 3 1 1 3 3 1 1� , , , F Y Y kj k j k j 11 3 3 2 1 3 3 1 1� � , , , F Y Y Y kj k j k j k j 12 3 1 3 1 3 3 2 1 3 3 1� � , , , , F Y Y kj k j k j 13 3 1 3 1 3 3 1� , , , F Y Y kj k j k j 14 3 3 2 1 3 3 1� � , , , ãäå i j k p, , , , ...,�1 2 ; p n r� /18 . Çàòåì âû÷èñëÿåì ïðîìåæóòî÷íûå ìàòðèöû Qij : Q R Yij ik k p k j 1 1 1 3 1 3 1 1� � � � , , Q R Fij ik k p kj 2 2 1 1� � � � , Q N 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 N Yij i k k p k j 6 3 2 3 2 1 1 3 2 3 2 1� � � � , , , 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 Yij ik k p k j 10 8 1 3 1 3 1� � � � , , Q N Fij i k k p kj 11 3 3 1 1 1 8� � � � , , Q R Fij ik k p kj 12 9 1 9� � � � , (11) 34 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 Q R Fij ik k p kj 13 10 1 10� � � � , Q N Yij i k k p k j 14 3 2 3 1 1 3 3 2 1� � � � , , , 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 N Yij i k k p k j 19 3 2 3 1 1 1 3 1 3 2 1� � � � , , , Q N Yij i k k p k j 20 3 1 3 1 1 3 3 1 1� � � � , , , Q N Yij i k k p k j 21 3 1 3 2 1 1 3 2 3 1� � � � , , , Q N Yij k p i k k j 22 1 3 3 2 1 3 2 3 1 1� � � � , , , Q N Yij i k k p k j 23 3 3 1 1 3 3 1� � � � , , , ãäå i j k p, , , , ...,�1 2 . È â çàâåðøåíèå ýòàïà íàõîäèì ìàòðèöû S ij 1 : S Q Q Q i j ij ij ij3 2 3 2 1 6 14 19 � � � , , S 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 � � � � � � � , , S 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 � � � � � � � , , S 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 � � � � � � � , , S Q Q Q Q Q i j ij ij ij ij ij3 1 3 1 1 2 4 5 6 20 � � � � � , , (12) S Q Q Q Q Q i j ij ij ij ij ij3 1 3 1 14 16 17 18 21 � � � � � , , S 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 , � � � � � � � , S Q Q Q Q Q i j ij ij ij ij ij3 3 1 1 12 13 14 15 22 , � � � � � , S Q Q Q Q Q i j ij ij ij ij ij3 3 1 6 7 8 9 23 , � � � � � , ãäå i j p, , , ...,�1 2 . Ýòàï 4. Àíàëîãè÷íî âû÷èñëÿåì îñòàëüíûå ìàòðè÷íûå ïðîèçâåäåíèÿ S S2 23, ..., ñîãëàñíî (8). Ïîñëå íàõîæäåíèÿ óêàçàííûõ ïðîèçâåäåíèé îïðåäåëÿåì ìàòðèöû Zij 1 : Z S S Sij ij ij ij 1 6 14 19� � � , Z S S S S S S S i j ij ij ij ij ij ij ij, , �� 1 1 4 5 6 12 14 15 Z S S S S S S S i j ij ij ij ij ij ij ij,2 1 6 7 9 10 14 16 18 �� , Z S S S S S S S i j ij ij ij ij ij ij ij�� , 1 2 3 4 6 14 16 17 , Z S S S S S i j ij ij ij ij ij� �� , 1 2 4 5 6 20 , (13) Z S S S S S i j ij ij ij ij ij� �� , , 2 1 14 16 17 18 21 Z S S S S S S S i j ij ij ij ij ij ij ij2 1 6 7 8 11 12 13 14 �� , , Z S S S S S i j ij ij ij ij ij2 1 12 13 14 15 22 � �� , Z S S S S S i j ij ij ij ij ij2 2 1 6 7 8 9 23 � �� , , ãäå i j p, , , ...,�12 . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 35 Ýòàï 5. Â çàêëþ÷åíèå âû÷èñëÿåì ìàòðè÷íûå ïðîèçâåäåíèÿ Z Zij ij 2 7, ..., ñîãëàñíî (5) è íàõîäèì ðåçóëüòèðóþùèå ìàòðèöû ñîãëàñíî (2) ïî ñëåäóþùèì ôîðìóëàì: C Z Z Z Zij ij ij ij ij� � �1 4 5 7 , C Z Zi j ij ij,3 3 5 �� , C Z Zi j ij ij3 2 4 �� , , (14) C Z Z Z Zi j ij ij ij ij3 3 1 2 3 6 � �� , , ãäå i j, , , ...,�1 2 3�. Îöåíèì âû÷èñëèòåëüíóþ ñëîæíîñòü îáúåäèíåííîãî êëåòî÷íîãî ìåòîäà (4)–(14). Ïðè âû÷èñëåíèè ìàòðè÷íûõ âûðàæåíèé (4) è (14) ýòîò ìåòîä òðåáóåò ñî- îòâåòñòâåííî 10 2l è 8 2l ìàòðè÷íûõ îïåðàöèé ñëîæåíèÿ, äëÿ êàæäîé èç êîòîðûõ âíóòðåííèé àëãîðèòì òðåáóåò r 2 ñêàëÿðíûõ îïåðàöèé ñëîæåíèÿ. Ñóììàðíàÿ àääè- òèâíàÿ ñëîæíîñòü âû÷èñëåíèé (4) è (14), îïðåäåëÿåìàÿ êîëè÷åñòâîì ñêàëÿðíûõ îïåðàöèé ñëîæåíèÿ, ñîñòàâëÿåò W W W l r l ra a a ( ),( ) ( ) ( )4 14 4 14 2 2 2 210 8� � � � � � � � � � � � � � � � � � � � � � � � � �18 18 2 18 2 4 52 2 2 2 2 2 2l r m r n r r n, îïåðàöèé ñëîæåíèÿ. Îïðåäåëèì ñëîæíîñòü âû÷èñëåíèé îäíîãî èç ñåìè ìàòðè÷íûõ ïðîèçâåäåíèé Z1, ò.å. âû÷èñëåíèé (6)–(13). Ïðè âû÷èñëåíèè ìàòðè÷íûõ âûðàæåíèé (6), (7) è (13) òðåáóåòñÿ ñîîòâåòñòâåííî 28 2� , 28 2� è 42 2� ìàòðè÷íûõ îïåðàöèé ñëîæåíèÿ, äëÿ êàæäîé èç êîòîðûõ âíóòðåííèé àëãîðèòì òðåáóåò r 2 ñêàëÿðíûõ îïåðàöèé ñëîæå- íèÿ. Òàêèì îáðàçîì, ñóììàðíàÿ àääèòèâíàÿ ñëîæíîñòü óêàçàííûõ âû÷èñëåíèé ñî- ñòàâëÿåò W r m r n r a ( ),( ),( )6 7 13 2 2 2 2 2 98 98 6 98 6 � � � � � � � � � � � � � � � � �� r n2 22 7, îïåðàöèé ñëîæåíèÿ. Îïðåäåëèì ñëîæíîñòü âû÷èñëåíèé 23 ìàòðè÷íûõ ïðîèçâåäåíèé S S1 23� �� , ò.å. âû÷èñëåíèé (8)–(12). Ïðè íàõîæäåíèè ìàòðè÷íûõ êîýôôèöèåíòîâ Rik (9), Fkj (10) è ìàòðèö S ij 1 (12) âíåøíèå àëãîðèòìû òðåáóþò ñîîòâåòñòâåííî 28 2p , 28 2p è 42 2p ìàòðè÷íûõ îïåðàöèé ñëîæåíèÿ, äëÿ êàæäîé èç êîòîðûõ âíóòðåííèé àëãîðèòì òðåáóåò r 2 ñêàëÿðíûõ îïåðàöèé ñëîæåíèÿ. Ñóììàðíàÿ àääèòèâíàÿ ñëîæíîñòü óêàçàííûõ âû÷èñëåíèé ñîñòàâëÿåò W p ra ( ),( ),( )9 10 12 2 298� � � � � � � � � � � �98 18 0 3024 2 2 2n r r n, îïåðàöèé ñëîæåíèÿ. Ïðè âû÷èñëåíèè ìàòðè÷íûõ âûðàæåíèé (11) âíåøíèé àëãîðèòì òðåáóåò 23 2p ìàòðè÷íûõ îïåðàöèé óìíîæåíèÿ è 23 3 2( )p p ìàòðè÷íûõ îïåðàöèé ñëî- æåíèÿ. Èñïîëüçóÿ â êà÷åñòâå âíóòðåííåãî òðàäèöèîííûé àëãîðèòì óìíîæåíèÿ ìàòðèö [6], òðåáóþùèé r 3ñêàëÿðíûõ îïåðàöèé óìíîæåíèÿ è ( )r r3 2 ñêàëÿðíûõ îïåðàöèé ñëîæåíèÿ, ïîëó÷àåì äëÿ ìóëüòèïëèêàòèâíîé è àääèòèâíîé ñëîæíîñòåé âû÷èñëåíèé (11) ñîîòâåòñòâåííî ñëåäóþùèå çíà÷åíèÿ: � W p r n r r nì ( ) ,11 3 3 3 3 323 23 18 0 00394� � � � � � � � � � � îïåðàöèé óìíîæåíèÿ; � W p p r p r r n r ra ( ) [( ) ( )]11 3 2 2 3 3 2 3 323 23 18 23� � � � � � � � � � n r r 18 2 2� � � � � � � � � 0 00394 0 07093 2, ,n n îïåðàöèé ñëîæåíèÿ. Èñïîëüçóÿ ïîëó÷åííûå âûøå îöåíêè, îïðåäåëÿåì ìóëüòèïëèêàòèâíóþ è àä- äèòèâíóþ ñëîæíîñòü âû÷èñëåíèé 23 ìàòðè÷íûõ ïðîèçâåäåíèé S S1 23� �� , ò.å. âû÷èñëåíèé (8): 36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 � W W n nì ì ( ) ( ) , ,8 11 3 323 23 0 00394 0 0897� � � � � îïåðàöèé óìíîæåíèÿ; � W W W Wa a a a 8 9 10 12 11 6 7 1323 23 0� � � �( ) (( ),( ),( ) ( ) ( ),( ),( ) , , , )3024 0 0039 0 07092 3 2n n n� � � � �2 7 0 0897 8 0242 3 2, , ,n n n îïåðàöèé ñëîæåíèÿ. Òîãäà ìóëüòèïëèêàòèâíàÿ è àääèòèâíàÿ ñëîæíîñòè âû÷èñëåíèé ñåìè ìàò- ðè÷íûõ ïðîèçâåäåíèé Z Z1 7� �� , ò.å. âû÷èñëåíèé (5), ñîîòâåòñòâåííî ðàâíû � W W n nì ì ( ) ( ) , ,5 8 3 37 7 0 0897 0 6279� � � � � îïåðàöèé óìíîæåíèÿ; � W W n n na a ( ) ( ) ( , , ) , ,5 8 3 2 37 7 0 0897 8 024 0 6279 56168� � � � � � � n2 îïåðàöèé ñëîæåíèÿ. Òàêèì îáðàçîì, íà îñíîâå îáúåäèíåííîãî êëåòî÷íîãî ìåòîäà (4)–(14) ïîëó- ÷àåì êëåòî÷íûé àíàëîã òðàäèöèîííîãî àëãîðèòìà óìíîæåíèÿ ìàòðèö ñî ñëåäóþ- ùèìè çíà÷åíèÿìè ìóëüòèïëèêàòèâíîé, àääèòèâíîé è îáùåé ñëîæíîñòåé: � W W n nì ì� � �( ) , ,5 3 30 6279 0 63 îïåðàöèé óìíîæåíèÿ; � W W W n n na a a� � � � � �( ) ( ),( ) , , , ,5 4 14 3 2 20 6279 56168 4 5 0 6279n n3 260 668� �, � �0 63 613 2, n n îïåðàöèé ñëîæåíèÿ; � W W W n n n nîáù ì a� � � � � � �0 6279 0 6279 60 668 12558 603 3 2 3, , , , ,668 2n � � �126 613 2, n n îïåðàöèé óìíîæåíèÿ/ñëîæåíèÿ. Ðàññìîòðåííûé êëåòî÷íûé ìåòîä (4)–(14) îáåñïå÷èâàåò ìèíèìèçàöèþ íà 37 % ìóëüòèïëèêàòèâíîé ñëîæíîñòè òðàäèöèîííîãî àëãîðèòìà ïðè âñåõ çíà÷åíèÿõ n, à òàêæå àääèòèâíîé è îáùåé ñëîæíîñòåé ïðè n � 105 , êîãäà ñëîæíîñòü O n O n( ) ( )2 3�� . Îòìåòèì, ÷òî ïðè n �105 ñëîæíîñòü O n( )2 â çíà÷åíèÿõ àääèòèâ- íîé è îáùåé ñëîæíîñòåé ñîñòàâëÿåò ñîîòâåòñòâåííî 0,09 % è 0,04 % ñëîæíîñòè O n( )3 . Àíàëîãè÷íî ìîæíî ïîëó÷èòü îöåíêè âû÷èñëèòåëüíîé ñëîæíîñòè äðóãèõ èç- âåñòíûõ àëãîðèòìîâ óìíîæåíèÿ ìàòðèö. Ñóùåñòâóåò âòîðîé âàðèàíò îáúåäèíåíèÿ òðåõ ìåòîäîâ, êîòîðûé ñî÷åòàåò ðåêóðñèâíûé ìåòîä Ëåéäåðìàíà [5] ñî ñìåøàííûì êëåòî÷íûì ìåòîäîì óìíîæå- íèÿ ìàòðèö ïîðÿäêà 2q r� �� ( , )q � �1 1� [2]. Â ýòîì ñëó÷àå îáúåäèíåííûé êëå- òî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö ïîðÿäêà 3 2� �� q r ( , , )� �� 0 1 1q äàåò âîç- ìîæíîñòü ïîëó÷àòü êëåòî÷íûå àëãîðèòìû óìíîæåíèÿ ìàòðèö ñ ìèíèìèçèðîâàí- íîé íà 35,4 % âû÷èñëèòåëüíîé ñëîæíîñòüþ. Ïðåäëîæåííûé â äàííîé ñòàòüå îáúåäèíåííûé ìåòîä ðàñøèðÿåò ñåìåéñòâî êëåòî÷íûõ ìåòîäîâ óìíîæåíèÿ ìàòðèö è ïîçâîëÿåò ïîëó÷èòü íàèâûñøèé ïðî- öåíò ìèíèìèçàöèè ìóëüòèïëèêàòèâíîé, àääèòèâíîé è îáùåé ñëîæíîñòåé èçâåñòíûõ àëãîðèòìîâ óìíîæåíèÿ ìàòðèö. CÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Å ë ô è ì î â à Ë . Ä . Áûñòðûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2008. — ¹ 3. — Ñ. 55–59. 2. Å ë ô è ì î â à Ë . Ä . Ñìåøàííûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö // Òàì æå. — 2009. — ¹ 1. — Ñ. 22–27. 3. Å ë ô è ì î â à Ë . Ä . Íîâûå êëåòî÷íûå ìåòîäû óìíîæåíèÿ ìàòðèö // Òàì æå. — 2013. — ¹ 1. — Ñ. 19–29. 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, N1. — P.126–128. 6. Ô à ä ä å å â Ä . Ê . , Ô à ä ä å å â à Â . Í . Âû÷èñëèòåëüíûå ìåòîäû ëèíåéíîé àëãåáðû. — Ì.; Ë.: Ôèç- ìàòãèç, 1963. — 734ñ. Ïîñòóïèëà 23.11.2012 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 5 37
id	nasplib_isofts_kiev_ua-123456789-86268
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	0023-1274
language	Russian
last_indexed	2025-11-27T08:22:42Z
publishDate	2013
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
record_format	dspace
spelling	Елфимова, Л.Д. 2015-09-11T19:55:29Z 2015-09-11T19:55:29Z 2013 Объединенный клеточный метод умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2013. — Т. 49, № 5. — С. 28-37. — Бібліогр.: 6 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86268 681.322.012 Запропоновано об’єднаний клітинний метод множення матриць, який являє собою гібрид трьох методів: рекурсивних методів Штрассена, Лейдермана та швидкого клітинного методу множення матриць. Взаємодія трьох методів забезпечує найвищий порівняно з відомими методами відсоток мінімізації (37 %) мультиплікативної, адитивної та загальної складності клітинних аналогів відомих алгоритмів множення матриць. Оцінку обчислювальної складності об’єднаного методу наведено на прикладі отримання клітинного аналога традиційного алгоритму множення матриць. A unified cellular method of matrix multiplication is proposed that is a hybrid of three methods, namely, Strassen’s and Laderman’s recursive methods and a fast cellular method for matrix multiplication. The interaction of these three methods provides the highest (in comparison with well-known methods) percentage (equal to 37%) of minimizing the multiplicative, additive, and overall complexities of cellular analogues of well-known matrix multiplication algorithms. The estimation of the computational complexity of the unified method is illustrated by the example of a model of obtaining a cellular analogue of the traditional matrix multiplication algorithm. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Объединенный клеточный метод умножения матриц Об’єднаний клітинний метод множення матриць A unified cellular method for matrix multiplication Article published earlier
spellingShingle	Объединенный клеточный метод умножения матриц Елфимова, Л.Д. Кибернетика
title	Объединенный клеточный метод умножения матриц
title_alt	Об’єднаний клітинний метод множення матриць A unified cellular method for matrix multiplication
title_full	Объединенный клеточный метод умножения матриц
title_fullStr	Объединенный клеточный метод умножения матриц
title_full_unstemmed	Объединенный клеточный метод умножения матриц
title_short	Объединенный клеточный метод умножения матриц
title_sort	объединенный клеточный метод умножения матриц
topic	Кибернетика
topic_facet	Кибернетика
url	https://nasplib.isofts.kiev.ua/handle/123456789/86268
work_keys_str_mv	AT elfimovald obʺedinennyikletočnyimetodumnoženiâmatric AT elfimovald obêdnaniiklítinniimetodmnožennâmatricʹ AT elfimovald aunifiedcellularmethodformatrixmultiplication

Объединенный клеточный метод умножения матриц

Institution

Ähnliche Einträge