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

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

Повний опис

Збережено в:

Бібліографічні деталі
Опубліковано в: :	Кибернетика и системный анализ
Дата:	2013
Автор:	Елфимова, Л.Д.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2013
Теми:	Кибернетика
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/86268
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Объединенный клеточный метод умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2013. — Т. 49, № 5. — С. 28-37. — Бібліогр.: 6 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-86268
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
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Объединенный клеточный метод умножения матриц
spellingShingle	Объединенный клеточный метод умножения матриц Елфимова, Л.Д. Кибернетика
title_short	Объединенный клеточный метод умножения матриц
title_full	Объединенный клеточный метод умножения матриц
title_fullStr	Объединенный клеточный метод умножения матриц
title_full_unstemmed	Объединенный клеточный метод умножения матриц
title_sort	объединенный клеточный метод умножения матриц
author	Елфимова, Л.Д.
author_facet	Елфимова, Л.Д.
topic	Кибернетика
topic_facet	Кибернетика
publishDate	2013
language	Russian
container_title	Кибернетика и системный анализ
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Об’єднаний клітинний метод множення матриць A unified cellular method for matrix multiplication
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.
issn	0023-1274
url	https://nasplib.isofts.kiev.ua/handle/123456789/86268
citation_txt	Объединенный клеточный метод умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2013. — Т. 49, № 5. — С. 28-37. — Бібліогр.: 6 назв. — рос.
work_keys_str_mv	AT elfimovald obʺedinennyikletočnyimetodumnoženiâmatric AT elfimovald obêdnaniiklítinniimetodmnožennâmatricʹ AT elfimovald aunifiedcellularmethodformatrixmultiplication
first_indexed	2025-11-27T08:22:42Z
last_indexed	2025-11-27T08:22:42Z
_version_	1850808119616077824
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

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

Репозитарії

Схожі ресурси