Быстрые алгоритмы для базовой операции клеточных методов линейной алгебры

Быстрые алгоритмы для базовой операции клеточных методов линейной алгебры

Рассмотрены быстрые алгоритмы для клеточной операции D = C + ΣAlBl, построенные на основе гибридных алгоритмов умножения матриц порядка n = 3μ (μ > 1), n = 6μ (μ > 0) и отличающиеся от известных алгоритмов наименьшей операционной сложностью. Даны оценки мультипликативной, аддитивной и общей сл...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Veröffentlicht in:Кибернетика и системный анализ
Datum:2015
1. Verfasser: Елфимова, Л.Д.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2015
Schlagworte:
Кибернетика
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/124926
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:Быстрые алгоритмы для базовой операции клеточных методов линейной алгебры / Л.Д. Елфимова // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 35-45. — Бібліогр.: 13 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-124926
record_format dspace
spelling Елфимова, Л.Д.
2017-10-12T08:52:47Z
2017-10-12T08:52:47Z
2015
Быстрые алгоритмы для базовой операции клеточных методов линейной алгебры / Л.Д. Елфимова // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 35-45. — Бібліогр.: 13 назв. — рос.
0023-1274
https://nasplib.isofts.kiev.ua/handle/123456789/124926
681.322.012
Рассмотрены быстрые алгоритмы для клеточной операции D = C + ΣAlBl, построенные на основе гибридных алгоритмов умножения матриц порядка n = 3μ (μ > 1), n = 6μ (μ > 0) и отличающиеся от известных алгоритмов наименьшей операционной сложностью. Даны оценки мультипликативной, аддитивной и общей сложностей представленных алгоритмов.
Розглянуто швидкі алгоритми для клітинної операції D = C + ΣAlBl, які побудовані на основі гібридних алгоритмів множення матриць порядку n = 3μ (μ > 1) n = 6μ (μ > 0) та відрізняються від відомих алгоритмів найменшою операційною складністю. Наведено оцінки мультиплікативної, адитивної та загальної складності зазначених алгоритмів.
This paper proposes fast algorithms for the cellular operation D = C + ΣAlBl that are based on hybrid multiplication algorithms for matrices of order n = 3μ (μ > 1) , n = 6μ (μ > 0) and are characterized by the lowest computational complexity as compared with the well-known algorithms. The multiplicative, additive, and overall complexities of the above-mentioned algorithms are estimated.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Кибернетика и системный анализ
Кибернетика
Быстрые алгоритмы для базовой операции клеточных методов линейной алгебры
Швидкі алгоритми для базової операції клітинних методів лінійної алгебри
Fast algorithms for the basic operation of linear algebra cellular methods
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 2015
language Russian
container_title Кибернетика и системный анализ
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Швидкі алгоритми для базової операції клітинних методів лінійної алгебри
Fast algorithms for the basic operation of linear algebra cellular methods
description Рассмотрены быстрые алгоритмы для клеточной операции D = C + ΣAlBl, построенные на основе гибридных алгоритмов умножения матриц порядка n = 3μ (μ > 1), n = 6μ (μ > 0) и отличающиеся от известных алгоритмов наименьшей операционной сложностью. Даны оценки мультипликативной, аддитивной и общей сложностей представленных алгоритмов. Розглянуто швидкі алгоритми для клітинної операції D = C + ΣAlBl, які побудовані на основі гібридних алгоритмів множення матриць порядку n = 3μ (μ > 1) n = 6μ (μ > 0) та відрізняються від відомих алгоритмів найменшою операційною складністю. Наведено оцінки мультиплікативної, адитивної та загальної складності зазначених алгоритмів. This paper proposes fast algorithms for the cellular operation D = C + ΣAlBl that are based on hybrid multiplication algorithms for matrices of order n = 3μ (μ > 1) , n = 6μ (μ > 0) and are characterized by the lowest computational complexity as compared with the well-known algorithms. The multiplicative, additive, and overall complexities of the above-mentioned algorithms are estimated.
issn 0023-1274
url https://nasplib.isofts.kiev.ua/handle/123456789/124926
citation_txt Быстрые алгоритмы для базовой операции клеточных методов линейной алгебры / Л.Д. Елфимова // Кибернетика и системный анализ. — 2015. — Т. 51, № 6. — С. 35-45. — Бібліогр.: 13 назв. — рос.
work_keys_str_mv AT elfimovald bystryealgoritmydlâbazovoioperaciikletočnyhmetodovlineinoialgebry
AT elfimovald švidkíalgoritmidlâbazovoíoperacííklítinnihmetodívlíníinoíalgebri
AT elfimovald fastalgorithmsforthebasicoperationoflinearalgebracellularmethods
first_indexed 2025-11-25T21:02:33Z
last_indexed 2025-11-25T21:02:33Z
_version_ 1850542944420888576
fulltext ÓÄÊ 681.322.012 Ë.Ä. ÅËÔÈÌÎÂÀ ÁÛÑÒÐÛÅ ÀËÃÎÐÈÒÌÛ ÄËß ÁÀÇÎÂÎÉ ÎÏÅÐÀÖÈÈ ÊËÅÒÎ×ÍÛÕ ÌÅÒÎÄΠËÈÍÅÉÍÎÉ ÀËÃÅÁÐÛ Àííîòàöèÿ. Ðàññìîòðåíû áûñòðûå àëãîðèòìû äëÿ êëåòî÷íîé îïåðàöèè D C A Bl l l = + = å 1 x , ïîñòðîåííûå íà îñíîâå ãèáðèäíûõ àëãîðèòìîâ óìíîæåíèÿ ìàòðèö ïîðÿäêà n = >3 1m m( ) , n = >6 0m m( ) è îòëè÷àþùèåñÿ îò èçâåñòíûõ àëãîðèòìîâ íàèìåíüøåé îïåðàöèîííîé ñëîæ- íîñòüþ. Äàíû îöåíêè ìóëüòèïëèêàòèâíîé, àääèòèâíîé è îáùåé ñëîæíîñòåé ïðåäñòàâëåí- íûõ àëãîðèòìîâ. Êëþ÷åâûå ñëîâà: ëèíåéíàÿ àëãåáðà, êëåòî÷íûå ìåòîäû, áàçîâàÿ îïåðàöèÿ, áûñòðûå àëãî- ðèòìû óìíîæåíèÿ ìàòðèö. ÂÂÅÄÅÍÈÅ Â íàñòîÿùåå âðåìÿ äëÿ ÷èñëåííûõ ìåòîäîâ ëèíåéíîé àëãåáðû (ËÀ) ðàçðàáîòà- íû èõ êëåòî÷íûå àíàëîãè, ñâîéñòâà êîòîðûõ îáåñïå÷èâàþò âîçìîæíîñòü áû- ñòðîãî ðåøåíèÿ çàäà÷ áîëüøèõ ðàçìåðîâ íà ðàçëè÷íûõ ïàðàëëåëüíûõ âû÷èñ- ëèòåëüíûõ ñèñòåìàõ è ñîçäàíèÿ íà èõ îñíîâå ýôôåêòèâíîãî ìàøèííî-íåçàâè- ñèìîãî ïðîãðàììíîãî îáåñïå÷åíèÿ [1, 2]. Óêàçàííûå êëåòî÷íûå àíàëîãè òðåáóþò äëÿ ñâîåé ðåàëèçàöèè âûïîëíåíèÿ áàçîâîé îïåðàöèè âèäà D C AB= + (1) è / èëè D C A Bl l l = + = å 1 x (2) (ãäå A B Ñ D, , , — êâàäðàòíûå ìàòðèöû ðàçìåðà êëåòêè r; x — ïåðåìåííûé èíäåêñ ñóììèðîâàíèÿ) è íåñòàíäàðòíûõ îïåðàöèé, êîòîðûå ñîñòàâëÿþò äîñòà- òî÷íî ìàëûé ïðîöåíò îáùåãî ÷èñëà îïåðàöèé àëãîðèòìà è ìîãóò áûòü ïðîèç- âîëüíûìè àëãîðèòìàìè ËÀ. Äëÿ áûñòðîãî âû÷èñëåíèÿ êëåòî÷íûõ îïåðàöèé (1) è (2), ñîñòàâëÿþùèõ áîëüøîé ïðîöåíò îáùåãî ÷èñëà àðèôìåòè÷åñêèõ îïåðàöèé àëãîðèòìà, èñïîëüçó- þòñÿ áûñòðûå àëãîðèòìû óìíîæåíèÿ ( )n n´ -ìàòðèö, à èìåííî øèðîêî ïðèìåíÿå- ìûå íà ïðàêòèêå ðåêóðñèâíûå àëãîðèòìû Øòðàññåíà [3], Âèíîãðàäà–Øòðàññå- íà [4], Ëåéäåðìàíà [5] è ðåãóëÿðíûé àëãîðèòì Âèíîãðàäà [6]. Êðîìå òîãî, â ðàáî- òàõ [7–9] ïðåäñòàâëåíî ñåìåéñòâî íîâûõ áûñòðûõ àëãîðèòìîâ óìíîæåíèÿ ìàòðèö ïîðÿäêà n = 2m ( )m >1 [7, 8], n = 3m ( )m >1 [9], n = 4m ( )m > 0 [7, 8], n = >6 0m m( ) [9], ïðè ïîñòðîåíèè êîòîðûõ èñïîëüçîâàëèñü àëãîðèòìû óìíîæåíèÿ (2 2´ )-ìàòðèö Øòðàññåíà [3] è Âèíîãðàäà–Øòðàññåíà [4], (3 3´ )-ìàòðèö Ëåéäåðìàíà [5] è äëÿ ñêàëÿðíîãî ïðîèçâåäåíèÿ Âèíîãðàäà [6]. Äàííûå ãèáðèäíûå àëãîðèòìû, ïîëó÷åííûå íîâûì ñïîñîáîì ïîñòðîåíèÿ áûñòðûõ àëãîðèòìîâ, ñî÷åòàÿ â ñåáå äîñòîèíñòâà ïåðå÷èñëåííûõ èçâåñòíûõ àëãî- ðèòìîâ, îáëàäàþò ðÿäîì îòëè÷èòåëüíûõ îñîáåííîñòåé. Âî-ïåðâûõ, îíè õàðàêòå- ðèçóþòñÿ íàèìåíüøåé ïî ñðàâíåíèþ ñ èçâåñòíûìè àëãîðèòìàìè îïåðàöèîííîé ñëîæíîñòüþ, îáóñëîâëåííîé âïåðâûå äîñòèãíóòîé â íèõ îäíîâðåìåííîé ìèíè- ìèçàöèåé ìóëüòèïëèêàòèâíîé è àääèòèâíîé ñëîæíîñòåé. Âî-âòîðûõ, ãèáðèäíûå àëãîðèòìû óìíîæåíèÿ ìàòðèö ïîðÿäêà n = >2 1m m( ) è n = >3 1m m( ) âïåðâûå ñòàëè ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 35 © Ë.Ä. Åëôèìîâà, 2015 îñíîâîé äëÿ ïîñòðîåíèÿ áûñòðûõ êëåòî÷íûõ ìåòîäîâ óìíîæåíèÿ ìàòðèö, êîòî- ðûå ñîâìåñòíî ñ ðåêóðñèâíûìè ìåòîäàìè Øòðàññåíà è Ëåéäåðìàíà ïðèâåëè ê ðàçðàáîòêå ñåìåéñòâà êëåòî÷íûõ ìåòîäîâ óìíîæåíèÿ ìàòðèö [10–13], ïîçâîëÿþ- ùèõ âàðüèðîâàòü ðàçìåð êëåòêè è ïîëó÷àòü êëåòî÷íûå àíàëîãè èçâåñòíûõ àëãî- ðèòìîâ óìíîæåíèÿ ìàòðèö ñ ìèíèìèçèðîâàííûìè ìóëüòèïëèêàòèâíîé, àääèòèâ- íîé è îáùåé ñëîæíîñòÿìè. Â-òðåòüèõ, ðåãóëÿðíàÿ ñòðóêòóðà èíôîðìàöèîííûõ çàâèñèìîñòåé âñåõ áûñòðûõ ãèáðèäíûõ àëãîðèòìîâ äàåò âîçìîæíîñòü óñêîðèòü âû÷èñëåíèå áàçîâîé îïåðàöèè (2) çà ñ÷åò ìèíèìèçàöèè åå îïåðàöèîííîé ñëîæíîñòè. Òàê, â ðàáîòå [8] îïèñàíû áûñòðûå àëãîðèòìû äëÿ óêàçàííîé îïåðàöèè, ïîñòðîåííûå íà îñíîâå ãèáðèäíûõ àëãîðèòìîâ óìíîæåíèÿ ìàòðèö ÷åòíîãî ïîðÿäêà n = >2 1m m( ) è n = >4 0m m( ) . Öåëü íàñòîÿùåé ñòàòüè — îïòèìèçàöèÿ âû÷èñëèòåëüíîé ñëîæíîñòè àëãî- ðèòìîâ âû÷èñëåíèÿ êëåòî÷íîé îïåðàöèè (2).  äàííîé ðàáîòå ðàññìàòðèâàþòñÿ íàèáîëåå áûñòðûå àëãîðèòìû äëÿ äàííîé îïåðàöèè, êîòîðûå ïîñòðîåíû íà îñíî- âå ãèáðèäíûõ àëãîðèòìîâ óìíîæåíèÿ ìàòðèö íå òîëüêî ÷åòíîãî, íî è íå÷åòíîãî ïîðÿäêà n = >3 1m m( ) , n = >6 0m m( ) è îòëè÷àþòñÿ îò èçâåñòíûõ àëãîðèòìîâ âû- ÷èñëåíèÿ äàííîé îïåðàöèè íàèìåíüøåé îïåðàöèîííîé ñëîæíîñòüþ. Äàíû îöåíêè âû÷èñëèòåëüíîé ñëîæíîñòè ïðåäëîæåííûõ àëãîðèòìîâ. ÁÛÑÒÐÛÉ ÀËÃÎÐÈÒÌ ÄËß ÊËÅÒÎ×ÍÎÉ ÎÏÅÐÀÖÈÈ D C A Bl l l = + å = 1 x , ÏÎÑÒÐÎÅÍÍÛÉ ÍÀ ÎÑÍÎÂÅ ÃÈÁÐÈÄÍÎÃÎ ÀËÃÎÐÈÒÌÀ ÓÌÍÎÆÅÍÈß ÌÀÒÐÈÖ ÏÎÐßÄÊÀ n = >3 1m m( ) Ãèáðèäíûé àëãîðèòì óìíîæåíèÿ äâóõ êâàäðàòíûõ ìàòðèö A a ij= { } è B bij= { } ïîðÿäêà n = 3m ( )m >1 [9] èìååò íàèìåíüøóþ ïî ñðàâíåíèþ ñ èçâåñòíûìè àëãî- ðèòìàìè îïåðàöèîííóþ ñëîæíîñòü, êîòîðàÿ ñîñòàâëÿåò W n nîáù * , ,» +1 70 8 33 2 îïåðàöèé óìíîæåíèÿ/ñëîæåíèÿ. Ïðè ýòîì ìóëüòèïëèêàòèâíàÿ è àääèòèâíàÿ ñëîæíîñòè äàííîãî àëãîðèòìà ñîîòâåòñòâåííî ñîñòàâëÿþò W nì * ,» 0 85 3 îïåðà- öèé óìíîæåíèÿ è W n na * , ,» +0 85 8 33 2 îïåðàöèé ñëîæåíèÿ. Äëÿ óñêîðåíèÿ âû÷èñëåíèÿ îïåðàöèè D C A Bl l l = + = å 1 x íàä ìàòðèöàìè A B Ñ D, , , ïîðÿäêà r , ðåàëèçóåìîé ñ ïîìîùüþ óêàçàííîãî àëãîðèòìà, ïðåîáðàçó- åì åãî ñòðóêòóðó èíôîðìàöèîííûõ çàâèñèìîñòåé, èñïîëüçóÿ ñâîéñòâà êîììóòà- òèâíîñòè è àññîöèàòèâíîñòè îïåðàöèè ñëîæåíèÿ.  ýòîì ñëó÷àå áûñòðûé ðåãó- ëÿðíûé ïðîöåññ âû÷èñëåíèÿ êëåòî÷íîé îïåðàöèè (2) èìååò ñëåäóþùèé âèä: 36 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 s bij ik l k r k j l l 1 1 1 3 3 1 3 1 1 = × = - - = åå a x ( ) / , ( ) , sij ik l k r kj l l 2 2 1 3 1 1 = × == åå a b x ( ) / ( ) , s aij i k l k r kj l l 3 3 1 3 1 1 3 2 1 = × - - == åå , ( ) / ( )b x , sij ik l k r kj l l 4 3 1 3 3 1 = × == åå a b x ( ) / ( ) , sij ik l k r kj l l 5 4 1 3 4 1 = × == åå a b x ( ) / ( ) , s a bij i k l k r k j l l 6 3 2 3 2 1 3 3 2 3 2 1 = × - - = - - = åå , ( ) / , ( ) x , sij ik l k r kj l l 7 5 1 3 5 1 = × == åå a b x ( ) / ( ) , sij ik l k r kj l l 8 6 1 3 6 1 = × == åå a b x ( ) / ( ) , ãäå i j k r, , , , , / ;=1 2 3K l =1 2, , ,K x , x — ïåðåìåííûé èíäåêñ ñóììèðîâàíèÿ. Êîýôôèöèåíòû a a ik l ik l1 14( ) ( ), ,K è b b kj l kj l1 14( ) ( ), ,K îïðåäåëÿþòñÿ ïî ñëåäóþ- ùèì ôîðìóëàì: a ik l i k l i k l i k l a a a a 1 3 2 3 2 3 2 3 1 3 2 3 3 ( ) , ( ) , ( ) , ( )= + + - - - - - - i k l i k l i k l i k l a a a - - - - - - - - 1 3 2 3 1 3 1 3 3 2 3 3, ( ) , ( ) , ( ) , , ( ) a ik l i k l i k l a a 2 3 2 3 2 3 1 3 2 ( ) , ( ) , ( )= - - - - - , a ik l i k l i k l i k l a a a 3 3 2 3 2 3 1 3 2 3 1 3 1 ( ) , ( ) , ( ) , ( )= - + + - - - - - - , a ik l i k l i k l a a 4 3 1 3 2 3 1 3 1 ( ) , ( ) , ( )= + - - - - , a ik l i k l i k l i k l a a a 5 3 2 3 2 3 3 2 3 3 1 ( ) , ( ) , ( ) , ( )= - + + - - - - , a ik l i k l i k l a a 6 3 2 3 2 3 3 2 ( ) , ( ) , ( )= - + - - - , a ik l i k l i k l a a 7 3 3 2 3 3 1 ( ) , ( ) , ( )= + - - , (4) a ik l i k l i k l i k l a a a a 8 3 2 3 2 3 2 3 1 3 2 3 3 ( ) , ( ) , ( ) , ( )= + + - - - - - - i k l i k l i k l i k l a a a - - - - - - - - 1 3 1 3 1 3 3 3 2 3 3 1, ( ) , ( ) , ( ) , ( ) , a ik l i k l i k l i k l a a a 9 3 2 3 3 3 1 3 3 ( ) , ( ) , ( ) , ( )= - + + - - , a ik l i k l i k l a a 10 3 2 3 3 3 ( ) , ( ) , ( )= - - , a ik l i k l i k l a a 11 3 3 1 3 3 ( ) , ( ) , ( )= + - , a ik l i k l i k l i k l a a a 12 3 2 3 3 1 3 1 3 1 3 ( ) , ( ) , ( ) , ( )= - + + - - - - , a ik l i k l i k l a a 13 3 2 3 3 1 3 ( ) , ( ) , ( )= - - - , a ik l i k l i k l a a 14 3 1 3 1 3 1 3 ( ) , ( ) , ( )= + - - - , ãäå i k r, , , , /= 1 2 3K ; l = 1 2, , ,K x ; ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 37 sij ik l k r kj l l 9 7 1 3 7 1 = × == åå a b x ( ) / ( ) , s bij ik l k r k j l l 10 8 1 3 3 1 3 1 = × = - = åå a x ( ) / , ( ) , s aij i k l k r kj l l 11 3 3 1 1 3 8 1 = × - == åå , ( ) / ( )b x , sij ik l k r kj l l 12 9 1 3 9 1 = × == åå a b x ( ) / ( ) , sij ik l k r kj l l 13 10 1 3 10 1 = × == åå a b x ( ) / ( ) , s a bij i k l k r k j l l 14 3 2 3 1 3 3 3 2 1 = × - = - = åå , ( ) / , ( ) x , sij ik l k r kj l l 15 11 1 3 11 1 = × == åå a b x ( ) / ( ) , sij ik l k r kj l l 16 12 1 3 12 1 = × == åå a b x ( ) / ( ) , sij ik l k r kj l l 17 13 1 3 13 1 = × == åå a b x ( ) / ( ) , sij ik l k r kj l l 18 14 1 3 14 1 = × == åå a b x ( ) / ( ) , (3) s a bij i k l k r k j l l 19 3 2 3 1 1 3 3 1 3 2 1 = × - - = - - = åå , ( ) / , ( ) x , s a bij i k l k r k j l l 20 3 1 3 1 3 3 3 1 1 = × - = - = åå , ( ) / , ( ) x , s a bij i k l k r k j l l 21 3 1 3 2 1 3 3 2 3 1 = × - - = - = åå , ( ) / , ( ) x , s a bij i k l k r k j l l 22 3 3 2 1 3 3 2 3 1 1 = × - = - - = åå , ( ) / , ( ) x , s a bij i k l k r k j l l 23 3 3 1 3 3 3 1 = × == åå , ( ) / , ( ) x , b kj l k j l k j l b b 1 3 2 3 1 3 1 3 1 ( ) , ( ) , ( )= - + - - - - , b kj l k j l k j l k j l b b b 2 3 2 3 2 3 2 3 1 3 1 3 2 ( ) , ( ) , ( ) , ( )= - + + - - - - - - - - - + - - - - b b b b k j l k j l k j l k j l 3 1 3 1 3 1 3 3 3 2 3 3, ( ) , ( ) , ( ) , ( ) , b kj l k j l k j l k j l b b b 3 3 2 3 2 3 2 3 1 3 1 3 1 ( ) , ( ) , ( ) , ( )= - + - - - - - - , b kj l k j l k j l b b 4 3 2 3 2 3 2 3 1 ( ) , ( ) , ( )= - + - - - - , b kj l k j l k j l k j l b b b 5 3 2 3 2 3 2 3 3 1 3 ( ) , ( ) , ( ) , ( )= - + - - - - , b kj l k j l k j l b b 6 3 2 3 3 1 3 ( ) , ( ) , ( )= - - - , b kj l k j l k j l b b 7 3 2 3 2 3 2 3 ( ) , ( ) , ( )= - + - - - , (5) b kj l k j l k j l k j l b b b b 8 3 2 3 2 3 2 3 3 1 3 2 ( ) , ( ) , ( ) , ( )= - + + - - - - - - 3 1 3 1 3 1 3 3 3 2k j l k j l k j l b b - - - - - - + , ( ) , ( ) , ( ) + - b k j l 3 3 1, ( ) , b kj l k j l k j l k j l b b b 9 3 1 3 1 3 3 2 3 3 1 ( ) , ( ) , ( ) , ( )= + - - - - - , b kj l k j l k j l b b 10 3 1 3 1 3 3 1 ( ) , ( ) , ( )= - - - - , b kj l k j l k j l b b 11 3 3 2 3 3 1 ( ) , ( ) , ( )= - + - - , b kj l k j l k j l k j l b b b 12 3 1 3 3 3 2 3 3 ( ) , ( ) , ( ) , ( )= + - - - , b kj l k j l k j l b b 13 3 1 3 3 3 ( ) , ( ) , ( )= - - , b kj l k j l k j l b b 14 3 3 2 3 3 ( ) , ( ) , ( )= - + - , ãäå j k r, , , , / ;= 1 2 3K l = 1 2, , ,K x . Ýëåìåíòû ðåçóëüòèðóþùåé ìàòðèöû D dij= { } âû÷èñëÿþòñÿ åäèíîæäû â êîíöå ïðîöåññà: d c s s si j i j ij ij ij3 2 3 2 3 2 3 2 6 14 19 - - - -= + + +, , , d c s s s s s si j i j ij ij ij ij ij i3 2 3 1 3 2 3 1 1 4 5 6 12 - - - -= + + + + + +, , j ijs 14 15+ , d c s s s s s si j i j ij ij ij ij ij ij3 2 3 3 2 3 6 7 9 10 14 16 - -= + + + + + +, , + sij 18 , d c s s s s s si j i j ij ij ij ij ij i3 1 3 2 3 1 3 2 2 3 4 6 14 - - - -= + + + + + +, , j ijs 16 17+ , d c s s s s si j i j ij ij ij ij ij3 1 3 1 3 1 3 1 2 4 5 6 20 - - - -= + + + + +, , , (6) d c s s s s si j i j ij ij ij ij ij3 1 3 3 1 3 14 16 17 18 21 - -= + + + + +, , , d c s s s s s si j i j ij ij ij ij ij ij3 3 2 3 3 2 6 7 8 11 12 13 , ,- -= + + + + + + + sij 14 , d c s s s s si j i j ij ij ij ij ij3 3 1 3 3 1 12 13 14 15 22 , ,- -= + + + + + , d c s s s s si j i j ij ij ij ij ij3 3 3 3 6 7 8 9 23 , ,= + + + + + , ãäå i j r, , , , /=1 2 3K . Îöåíèì âû÷èñëèòåëüíóþ ñëîæíîñòü ðàññìîòðåííîãî àëãîðèòìà (3)–(6). Ìóëüòèïëèêàòèâíàÿ ñëîæíîñòü äàííîãî àëãîðèòìà ñîîòâåòñòâóåò ñëîæíîñòè âû- ÷èñëåíèé (3) è ñîñòàâëÿåò W W r r rì ì= = × æ è ç ö ø ÷ = × » ×( ) ,3 3 3 323 3 23 27 0 85x x x îïåðàöèé óìíîæåíèÿ. Àääèòèâíàÿ ñëîæíîñòü àëãîðèòìà îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì: W W W W Wa a a a a= + + +( ) ( ) ( ) ( )3 4 5 6 , 38 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 W r r r a ( ) ( )3 2 23 3 3 1 1 23 3 = × æ è ç ö ø ÷ × - æ è ç ö ø ÷ é ë ê ê ù û ú ú + - × æ x x è ç ö ø ÷ = × æ è ç ö ø ÷ - æ è ç ö ø ÷ é ë ê ê ù û ú ú + × æ è ç 2 3 2 23 3 23 3 23 3 x x r r r ö ø ÷ - 2 - æ è ç ö ø ÷ = × - × + × - » ×23 3 0 85 2 56 2 56 2 56 0 2 3 2 2 2r r r r rx x x x, , , , , ,85 2 563 2 r r- îïåðà- öèé ñëîæåíèÿ, W W W W r a a a a ( ), ( ), ( ) ( ) ( ) ( )4 5 6 4 5 6 2 28 3 28= + + = × æ è ç ö ø ÷ + ×x x r r r 3 51 3 56 3 2 2 2 æ è ç ö ø ÷ + æ è ç ö ø ÷ = × æ è ç ö ø ÷ +x + æ è ç ö ø ÷ » × +51 3 6 22 5 66 2 2 2r r rx , , îïåðàöèé ñëîæåíèÿ. Òîãäà ïîëíàÿ àääèòèâíàÿ ñëîæíîñòü àëãîðèòìà (3)–(6) ñîñòàâëÿåò W W W W W r r ra a a a a= + + + » × - + ×( ) ( ) ( ) ( ) , , ,3 4 5 6 3 20 85 2 56 6 22x x 2 2 35 66 0 85+ » × +, ,r rx + × +x 6 2 312 2, ,r r îïåðàöèé ñëîæåíèÿ. Òàêèì îáðàçîì, îáùàÿ âû÷èñëèòåëüíàÿ ñëîæíîñòü àëãîðèòìà (3)–(6) ñîñòàâëÿåò W W W r r r r r îáù ì a= + » × + × + × + » ×x x x x0 85 0 85 6 2 31 1 703 3 2 2, , , , , 3 2 26 2 31+ × +x , ,r r îïåðàöèé óìíîæåíèÿ/ñëîæåíèÿ. Ïîñêîëüêó ýëåìåíòû ðåçóëüòèðóþùåé ìàòðèöû (6) âû÷èñëÿþòñÿ òîëüêî îäèí ðàç, âûèãðûø ïî àääèòèâíîé è îáùåé ñëîæíîñòÿì îòíîñèòåëüíî ñëîæíîñòè âû÷èñëåíèÿ îïåðàöèè (2) ñ ïîìîùüþ ãèáðèäíîãî àëãîðèòìà [9] ñîîòâåòñòâåííî ñîñòàâëÿåò d x x x x x xa a a= × + - + - » × + × + × - ×W r r W r r r * ( ) , , ,1 0 85 8 3 0 82 2 3 2 2 5 3 r - - × - » × - » -x x x6 2 31 31 31 31 12 2 2 2 2, , , , , ( )r r r r r îïåðàöèé ñëîæåíèÿ, d x x x x xîáù îáù îáù = × + - + - » × + × + ×W r r W r r r * ( ) , ,1 1 70 8 32 2 3 2 2 - × -x 1 70 3, r - × - » -x x6 2 31 31 12 2 2, , , ( )r r r îïåðàöèé óìíîæåíèÿ/ñëîæåíèÿ. Äàííûé âûèãðûø ïðè îãðàíè÷åííîì ðàçìåðå êëåòêè r ÿâëÿåòñÿ ñóùåñòâåí- íûì óñêîðåíèåì âû÷èñëåíèÿ îïåðàöèè (2). ÁÛÑÒÐÛÉ ÀËÃÎÐÈÒÌ ÄËß ÊËÅÒÎ×ÍÎÉ ÎÏÅÐÀÖÈÈ D C A Bl l l = + = å 1 x , ÏÎÑÒÐÎÅÍÍÛÉ ÍÀ ÎÑÍÎÂÅ ÃÈÁÐÈÄÍÎÃÎ ÀËÃÎÐÈÒÌÀ ÓÌÍÎÆÅÍÈß ÌÀÒÐÈÖ ÏÎÐßÄÊÀ n = >6 0m m( ) Ãèáðèäíûé àëãîðèòì óìíîæåíèÿ äâóõ êâàäðàòíûõ ìàòðèö: A a ij= { } è B bij= { } ïîðÿäêà n = >6 0m m( ) [9] õàðàêòåðèçóåòñÿ íàèìåíüøåé ïî ñðàâíåíèþ ñ èçâåñòíûìè àëãîðèòìàìè ìóëüòèïëèêàòèâíîé ñëîæíîñòüþ, ñîñòàâëÿþùåé Wì * » +0 426 2 53 2, ,n n îïåðàöèé óìíîæåíèÿ. Ïðè ýòîì àääèòèâíàÿ è îáùàÿ ñëîæíîñòè âû÷èñëåíèé ñî- îòâåòñòâåííî ñîñòàâëÿþò W n n na * , ,» + -1 278 16 15 33 2 îïåðàöèé ñëîæåíèÿ, W n n nîáù * , , ,» + -1 70 18 5 15 33 2 îïåðàöèé óìíîæåíèÿ/ñëîæåíèÿ. Äëÿ ïîñòðîåíèÿ áûñòðîãî àëãîðèòìà âû÷èñëåíèÿ êëåòî÷íîé îïåðàöèè (2) íà îñíîâå äàííîãî àëãîðèòìà ïðåîáðàçóåì åãî ñòðóêòóðó èíôîðìàöèîííûõ ñâÿçåé, èñïîëüçóÿ ñâîéñòâà êîììóòàòèâíîñòè è àññîöèàòèâíîñòè îïåðàöèé ñëîæåíèÿ.  ýòîì ñëó÷àå îñíîâíûì âû÷èñëèòåëüíûì ÿäðîì àëãîðèòìà ÿâëÿþòñÿ ñëåäóþùèå ðåãóëÿðíûå âû÷èñëåíèÿ: ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 39 s h gij ij l i l j l l 1 1 1 1 1 = - - = å ( )( ) ( ) ( )q x , s h gij ij l i l j l l 5 5 5 5 1 = - - = å ( )( ) ( ) ( )q x , s h gij ij l i l j l l 2 2 2 2 1 = - - = å ( )( ) ( ) ( )q x , s h gij ij l i l j l l 6 6 6 6 1 = - - = å ( )( ) ( ) ( )q x , (7) s h gij ij l i l j l l 3 3 3 3 1 = - - = å ( )( ) ( ) ( )q x , M M M M M , s h gij ij l i l j l l 4 4 4 4 1 = - - = å ( )( ) ( ) ( )q x , s h gij ij l i l j l l 23 23 23 23 1 = - - = å ( )( ) ( ) ( )q x , i j r, , , , / ;= 1 2 3K l = 1 2, , ,K x . Çäåñü q a ij l i k l k j l k j l b b 1 2 1 1 6 1 3 1 6 4 3 1 ( ) , ( ) , ( ) , ( )( )(= + + - - - - - a i k l k r , ( ) / ) 2 1 1 6 = å , q a b b a ij l i k l k j l k j l i k 2 2 1 2 2 1 2 1 1 2 2( ) , ( ) , ( ) , ( ) , ( )(= + + - - ( ) / )l k r = å 1 6 , q b b ij l i k l k j l k j l i a a 3 3 1 6 4 2 2 2 1 2 3 ( ) , ( ) , ( ) , ( )( )(= + + - - - -1 6 1 1 6 , ( ) / ) k l k r - = å , q a b b a ij l i k l k j l k j l i k 4 2 1 3 2 3 2 1 3 2 3( ) , ( ) , ( ) , ( ) , ( )(= + + - - ( ) / )l k r = å 1 6 , (8) q a b b a ij l i k l k j l k j l i k 5 2 1 4 2 4 2 1 4 2 4( ) , ( ) , ( ) , ( ) , ( )(= + + - - ( ) / )l k r = å 1 6 , q ij l i k l k j l k j l a b b 6 3 2 6 5 6 2 3 2 6 5 3 2 ( ) , ( ) , ( ) , (( )(= + - - - - - - ) , ( ) / )+ - - = å a i k l k r 3 2 6 2 1 6 , q a b b a ij l i k l k j l k j l i k 7 2 1 5 2 5 2 1 5 2 5( ) , ( ) , ( ) , ( ) , ( )(= + + - - ( ) / )l k r = å 1 6 , q a b b a ij l i k l k j l k j l i k 8 2 1 6 2 6 2 1 6 2 6( ) , ( ) , ( ) , ( ) , ( )(= + + - - ( ) / )l k r = å 1 6 , q a b b a ij l i k l k j l k j l i k 9 2 1 7 2 7 2 1 7 2 7( ) , ( ) , ( ) , ( ) , ( )(= + + - - ( ) / )l k r = å 1 6 , q a a ij l i k l k j l k j l i b b 10 2 1 8 6 1 3 6 4 3 ( ) , ( ) , ( ) , ( ) , ( )(= + + - - - 2 8 1 6 k l k r ( ) / ) = å , q b b ij l i k l k j l k j l i a a 11 3 6 4 2 8 2 1 8 3 6 ( ) , ( ) , ( ) , ( ) , ( )(= + + - - k l k r - = å 1 1 6 ( ) / ) , q a b b a ij l i k l k j l k j l i k 12 2 1 9 2 9 2 1 9 2 ( ) , ( ) , ( ) , ( ) , ( )(= + + - - 9 1 6 ( ) / )l k r = å , q a b b a ij l i k l k j l k j l i 13 2 1 10 2 10 2 1 10( ) , ( ) , ( ) , ( )( )(= + + - - , ( ) / ) 2 10 1 6 k l k r = å , q ij l i k l k j l k j l a b b 14 3 2 6 3 6 3 2 6 3 3 2 ( ) , ( ) , ( ) , ( )( )(= + - - - - - + - = å a i k l k r 3 2 6 1 6 , ( ) / ) , q a b b a ij l i k l k j l k j l i 15 2 1 11 2 11 2 1 11( ) , ( ) , ( ) , ( )( )(= + + - - , ( ) / ) 2 11 1 6 k l k r = å , q a b b a ij l i k l k j l k j l i 16 2 1 12 2 12 2 1 12( ) , ( ) , ( ) , ( )( )(= + + - - , ( ) / ) 2 12 1 6 k l k r = å , 40 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 q a b b a ij l i k l k j l k j l i 17 2 1 13 2 13 2 1 13( ) , ( ) , ( ) , ( )( )(= + + - - , ( ) / ) 2 13 1 6 k l k r = å , q a b b a ij l i k l k j l k j l i 18 2 1 14 2 14 2 1 14( ) , ( ) , ( ) , ( )( )(= + + - - , ( ) / ) 2 14 1 6 k l k r = å , q ij l i k l k j l k j a b b 19 3 2 3 1 6 1 3 2 6 4 3 2 ( ) , ( ) , ( ) , (( )(= + - - - - - - l i k l k r a ) , ( ) / )+ - - = å 3 2 6 1 1 6 , q ij l i k l k j l k j l a b b 20 3 1 6 3 6 3 1 6 3 3 1 ( ) , ( ) , ( ) , ( )( )(= + - - - - - + - = å a i k l k r 3 1 6 1 6 , ( ) / ) , q ij l i k l k j l k j l a b b a 21 3 1 6 5 6 2 3 6 5 3 ( ) , ( ) , ( ) , ( )( )(= + + - - - - 3 1 6 2 1 6 i k l k r - - = å , ( ) / ) , q ij l i k l k j l k j l a b b 22 3 6 5 6 2 3 1 6 5 3 1 ( ) , ( ) , ( ) , ( )( )(= + - - - - - + - = å a i k l k r 3 6 2 1 6 , ( ) / ) , q ij l i k l k j l k j l i a b b a 23 3 6 3 6 3 6 3 3 3 6 ( ) , ( ) , ( ) , ( ) , ( )(= + + - - k l k r ( ) / ) = å 1 6 , ãäå i j r, , , , /=1 2 3K ; k r=1 2 6, , , / ;K ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 41 h i l i k l i k l k r 1 2 1 1 2 1 1 6 ( ) , ( ) , ( ) / = - = å a a , h i l i k l i k l k r 2 2 1 2 2 2 1 6 ( ) , ( ) , ( ) / = - = å a a , h a a i l i k l i k l k r 3 3 1 6 4 3 1 6 1 1 6 ( ) , ( ) , ( ) / = - - - - = å , h i l i k l i k l k r 4 2 1 3 2 3 1 6 ( ) , ( ) , ( ) / = - = å a a , h i l i k l i k l k r 5 2 1 4 2 4 1 6 ( ) , ( ) , ( ) / = - = å a a , h a a i l i k l i k l k r 6 3 2 6 5 3 2 6 2 1 6 ( ) , ( ) , ( ) / = - - - - = å , h i l i k l i k l k r 7 2 1 5 2 5 1 6 ( ) , ( ) , ( ) / = - = å a a , h i l i k l i k l k r 8 2 1 6 2 6 1 6 ( ) , ( ) , ( ) / = - = å a a , h i l i k l i k l k r 9 2 1 7 2 7 1 6 ( ) , ( ) , ( ) / = - = å a a , h i l i k l i k l k r 10 2 1 8 2 8 1 6 ( ) , ( ) , ( ) / = - = å a a , h a a i l i k l i k l k r 11 3 6 4 3 6 1 1 6 ( ) , ( ) , ( ) / = - - = å , h i l i k l i k l k r 12 2 1 9 2 9 1 6 ( ) , ( ) , ( ) / = - = å a a , h i l i k l i k l k r 13 2 1 10 2 10 1 6 ( ) , ( ) , ( ) / = - = å a a , h a a i l i k l i k l k r 14 3 2 6 3 3 2 6 1 6 ( ) , ( ) , ( ) / = - - - = å , h i l i k l i k l k r 15 2 1 11 2 11 1 6 ( ) , ( ) , ( ) / = - = å a a , h i l i k l i k l k r 16 2 1 12 2 12 1 6 ( ) , ( ) , ( ) / = - = å a a , h i l i k l i k l k r 17 2 1 13 2 13 1 6 ( ) , ( ) , ( ) / = - = å a a , h i l i k l i k l k r 18 2 1 14 2 14 1 6 ( ) , ( ) , ( ) / = - = å a a , (9) h a a i l i k l i k l k r 19 3 2 3 1 3 2 6 1 1 6 ( ) , ( ) , ( ) / = - - - - = å , h a a i l i k l i k l k r 20 3 1 6 3 3 1 6 1 6 ( ) , ( ) , ( ) / = - - - = å , h a a i l i k l i k l k r 21 3 1 6 5 3 1 6 2 1 6 ( ) , ( ) , ( ) / = - - - - = å , h a a i l i k l i k l k r 22 3 6 5 3 6 2 1 6 ( ) , ( ) , ( ) / = - - = å , h a a i l i k l i k l k r 23 3 6 3 3 6 1 6 ( ) , ( ) , ( ) / = - = å , ãäå i j r, , , , / ;=1 2 3K k r=1 2 6, , , / ;K l =1 2, , ,K x . Êîýôôèöèåíòû a a ik l ik l1 14( ) ( ), ,K è b b kj l kj l1 14( ) ( ), ,K ñîîòâåòñòâåííî èìåþò ñëå- äóþùèé âèä: a ik l i k l i k l i k l a a a a 1 3 2 3 2 3 2 3 1 3 2 3 3 ( ) , ( ) , ( ) , ( )= + + - - - - - - i k l i k l i k l i k l a a a - - - - - - - - 1 3 2 3 1 3 1 3 3 2 3 3, ( ) , ( ) , ( ) , ( ) , a ik l i k l i k l a a 2 3 2 3 2 3 1 3 2 ( ) , ( ) , ( )= - - - - - , a ik l i k l i k l i k l a a a 3 3 2 3 2 3 1 3 2 3 1 3 1 ( ) , ( ) , ( ) , ( )= - + + - - - - - - , a ik l i k l i k l a a 4 3 1 3 2 3 1 3 1 ( ) , ( ) , ( )= + - - - - , a ik l i k l i k l i k l a a a 5 3 2 3 2 3 3 2 3 3 1 ( ) , ( ) , ( ) , ( )= - + + - - - - , a ik l i k l i k l a a 6 3 2 3 2 3 3 2 ( ) , ( ) , ( )= - + - - - , a ik l i k l i k l a a 7 3 3 2 3 3 1 ( ) , ( ) , ( )= + - - , (10) a ik l i k l i k l i k l a a a a 8 3 2 3 2 3 2 3 1 3 2 3 3 ( ) , ( ) , ( ) , ( )= + + - - - - - - i k l i k l i k l i k l a a a - - - - - - - - 1 3 1 3 1 3 3 3 2 3 3 1, ( ) , ( ) , ( ) , ( ) , a ik l i k l i k l i k l a a a 9 3 2 3 3 3 1 3 3 ( ) , ( ) , ( ) , ( )= - + + - - , a ik l i k l i k l a a 10 3 2 3 3 3 ( ) , ( ) , ( )= - - , 42 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 g b b j l k j l k j l k r 1 6 1 3 1 6 4 3 1 1 6 ( ) , ( ) , ( ) / = - - - - = å , g j l k j l k j l k r 2 2 1 2 1 1 1 6 ( ) , ( ) , ( ) / = - = å b b , g j l k j l k j l k r 3 2 2 2 1 2 1 6 ( ) , ( ) , ( ) / = - = å b b , g j l k j l k j l k r 4 2 3 2 1 3 1 6 ( ) , ( ) , ( ) / = - = å b b , g j l k j l k j l k r 5 2 4 2 1 4 1 6 ( ) , ( ) , ( ) / = - = å b b , g b b j l k j l k j l k r 6 6 2 3 2 6 5 3 2 1 6 ( ) , ( ) , ( ) / = - - - - = å , g j l k j l k j l k r 7 2 5 2 1 5 1 6 ( ) , ( ) , ( ) / = - = å b b , g j l k j l k j l k r 8 2 6 2 1 6 1 6 ( ) , ( ) , ( ) / = - = å b b , g j l k j l k j l k r 9 2 7 2 1 7 1 6 ( ) , ( ) , ( ) / = - = å b b , g b b j l k j l k j l k r 10 6 1 3 6 4 3 1 6 ( ) , ( ) , ( ) / = - - = å , g j l k j l k j l k r 11 2 8 2 1 8 1 6 ( ) , ( ) , ( ) / = - = å b b , g j l k j l k j l k r 12 2 9 2 1 9 1 6 ( ) , ( ) , ( ) / = - = å b b , g j l k j l k j l k r 13 2 10 2 1 10 1 6 ( ) , ( ) , ( ) / = - = å b b , g b b j l k j l k j l k r 14 6 3 2 6 3 3 2 1 6 ( ) , ( ) , ( ) / = - - - = å , g j l k j l k j l k r 15 2 11 2 1 11 1 6 ( ) , ( ) , ( ) / = - = å b b , g j l k j l k j l k r 16 2 12 2 1 12 1 6 ( ) , ( ) , ( ) / = - = å b b , g j l k j l k j l k r 17 2 13 2 1 13 1 6 ( ) , ( ) , ( ) / = - = å b b , g j l k j l k j l k r 18 2 14 2 1 14 1 6 ( ) , ( ) , ( ) / = - = å b b , g b b j l k j l k j l k r 19 6 1 3 2 6 4 3 2 1 6 ( ) , ( ) , ( ) / = - - - - = å , g b b j l k j l k j l k r 20 6 3 1 6 3 3 1 1 6 ( ) , ( ) , ( ) / = - - - = å , g b b j l k j l k j l k r 21 6 2 3 6 5 3 1 6 ( ) , ( ) , ( ) / = - - = å , g b b j l k j l k j l k r 22 6 2 3 1 6 5 3 1 1 6 ( ) , ( ) , ( ) / = - - - - = å , g b b j l k j l k j l k r 23 6 3 6 3 3 1 6 ( ) , ( ) , ( ) / = - = å , a ik l i k l i k l a a 11 3 3 1 3 3 ( ) , ( ) , ( )= + - , a ik l i k l i k l i k l a a a 12 3 2 3 3 1 3 1 3 1 3 ( ) , ( ) , ( ) , ( )= - + + - - - - , a ik l i k l i k l a a 13 3 2 3 3 1 3 ( ) , ( ) , ( )= - - - , a ik l i k l i k l a a 14 3 1 3 1 3 1 3 ( ) , ( ) , ( )= + - - - , ãäå i k r, , , , /= 1 2 3K ; k r= 1 2 6, , , /K ; l = 1 2, , ,K x ; b kj l k j l k j l b b 1 3 2 3 1 3 1 3 1 ( ) , ( ) , ( )= - + - - - - , b kj l k j l k j l k j l b b b 2 3 2 3 2 3 2 3 1 3 1 3 2 ( ) , ( ) , ( ) , ( )= - + + - - - - - - - - - + - - - - b b b b k j l k j l k j l k j l 3 1 3 1 3 1 3 3 3 2 3 3, ( ) , ( ) , ( ) , ( ) , b kj l k j l k j l k j l b b b 3 3 2 3 2 3 2 3 1 3 1 3 1 ( ) , ( ) , ( ) , ( )= - + - - - - - - , b kj l k j l k j l b b 4 3 2 3 2 3 2 3 1 ( ) , ( ) , ( )= - + - - - - , b kj l k j l k j l k j l b b b 5 3 2 3 2 3 2 3 3 1 3 ( ) , ( ) , ( ) , ( )= - + - - - - , b kj l k j l k j l b b 6 3 2 3 3 1 3 ( ) , ( ) , ( )= - - - , b kj l k j l k j l b b 7 3 2 3 2 3 2 3 ( ) , ( ) , ( )= - + - - - , b kj l k j l k j l k j l b b b b 8 3 2 3 2 3 2 3 3 1 3 2 ( ) , ( ) , ( ) , ( )= - + + - - - - - - 3 1 3 1k j l - - - , ( ) - - + - - - b b b k j l k j l k j l 3 1 3 3 3 2 3 3 1, ( ) , ( ) , ( ) , (11) b kj l k j l k j l k j l b b b 9 3 1 3 1 3 3 2 3 3 1 ( ) , ( ) , ( ) , ( )= + - - - - - , b kj l k j l k j l b b 10 3 1 3 1 3 3 1 ( ) , ( ) , ( )= - - - - , b kj l k j l k j l b b 11 3 3 2 3 3 1 ( ) , ( ) , ( )= - + - - , b kj l k j l k j l k j l b b b 12 3 1 3 3 3 2 3 3 ( ) , ( ) , ( ) , ( )= + - - - , b kj l k j l k j l b b 13 3 1 3 3 3 ( ) , ( ) , ( )= - - , b kj l k j l k j l b b 14 3 3 2 3 3 ( ) , ( ) , ( )= - + - , ãäå j k r, , , , / ;= 1 2 3K k r= 1 2 6, , , / ;K l = 1 2, , ,K x . Ýëåìåíòû ðåçóëüòèðóþùåé ìàòðèöû D dij= { } âû÷èñëÿþòñÿ åäèíîæäû ïî ñëåäóþùèì ôîðìóëàì: d c s s si j i j ij ij ij3 2 3 2 3 2 3 2 6 14 19 - - - -= + + +, , , d c s s s s s si j i j ij ij ij ij ij i3 2 3 1 3 2 3 1 1 4 5 6 12 - - - -= + + + + + +, , j ijs 14 15+ , d c s s s s s si j i j ij ij ij ij ij ij3 2 3 3 2 3 6 7 9 10 14 16 - -= + + + + + +, , + sij 18 , (12) d c s s s s s si j i j ij ij ij ij ij i3 1 3 2 3 1 3 2 2 3 4 6 14 - - - -= + + + + + +, , j ijs 16 17+ , d c s s s s si j i j ij ij ij ij ij3 1 3 1 3 1 3 1 2 4 5 6 20 - - - -= + + + + +, , , d c s s s s si j i j ij ij ij ij ij3 1 3 3 1 3 14 16 17 18 21 - -= + + + + +, , , d c s s s s s si j i j ij ij ij ij ij ij3 3 2 3 3 2 6 7 8 11 12 13 , ,- -= + + + + + + + sij 14 , d c s s s s si j i j ij ij ij ij ij3 3 1 3 3 1 12 13 14 15 22 , ,- -= + + + + + , d c s s s s si j i j ij ij ij ij ij3 3 3 3 6 7 8 9 23 , ,= + + + + + , ãäå i j r, , , , /= 1 2 3K . Îöåíèì âû÷èñëèòåëüíóþ ñëîæíîñòü ðàññìîòðåííîãî àëãîðèòìà (7)–(12). ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 5 43 Ìóëüòèïëèêàòèâíàÿ ñëîæíîñòü äàííîãî àëãîðèòìà îïðåäåëÿåòñÿ ñëåäóþ- ùèì îáðàçîì: W W Wì ì ì= +( ) ( )8 9 , W r r r ì ( ) ,8 2 3 23 6 3 23 54 0= × × æ è ç ö ø ÷ é ë ê ê ù û ú ú = æ è ç ç ö ø ÷ ÷ » ×x x 426 3 r îïåðàöèé óìíîæåíèÿ, W r r r rì ( ) ,9 2 22 23 6 3 46 18 2 55= × × × æ è ç ö ø ÷ = × » ×x x x îïåðàöèé óìíîæåíèÿ. Òàêèì îáðàçîì, W W W r rì ì ì= + » × + ×( ) ( ) , ,8 9 3 20 426 2 55x x îïåðàöèé óìíîæåíèÿ. Àääèòèâíàÿ ñëîæíîñòü ðàññìîòðåííîãî àëãîðèòìà ñîñòàâëÿåò W W W W W W Wa a a a a a a= + + + + +( ) ( ) ( ) ( ) ( ) ( )7 8 9 10 11 12 , ãäå W r r ra ( ) ( ) ,7 2 2 223 2 3 1 23 3 511= × × æ è ç ö ø ÷ + - × æ è ç ö ø ÷ » × +x x x x × -2 55 2 552 2, ,r r îïåðàöèé ñëîæåíèÿ, W r r r r a ( )8 2 2 23 3 6 1 23 2 3 6 = × æ è ç ö ø ÷ - æ è ç ö ø ÷ + × æ è ç ö ø ÷ × æ è ç ö x ø ÷ é ë ê ê ù û ú ú = × æ è ç ç ö ø ÷ ÷ - æ è ç ç ö ø ÷ ÷ é ë ê ê ù û ú ú »x 69 54 23 9 3 2 r r » × - ×x x1 278 2 553 2, ,r r îïåðàöèé ñëîæåíèÿ, W r r a ( )9 2 23 3 6 1= × × - æ è ç ö ø ÷ é ë ê ù û ú =x x x x× - æ è ç ç ö ø ÷ ÷ » × - ×23 9 46 3 2 55 15 3 2 2r r r r, , îïåðàöèé ñëîæåíèÿ, Wa ( ), ( ), ( )10 11 12 = + + = × æ è ç ö ø ÷ + × æ è ç ö ø ÷ +W W W r r a a a ( ) ( ) ( )10 11 12 2 2 28 3 28 3 x x 51 3 2 ræ è ç ö ø ÷ » » × +x 6 22 5 662 2, ,r r îïåðàöèé ñëîæåíèÿ. Ñëåäîâàòåëüíî, ïîëíàÿ àääèòèâíàÿ ñëîæíîñòü àëãîðèòìà (7)–(12) îïðåäåëÿ- åòñÿ òàê: W W W W W ra a a a a= + + + » × + ×( ) ( ) ( ) ( ),( ),( ) ,7 8 9 10 11 12 2511 2x x , ,55 2 552 2 r r- + + × - × + × - × + × +x x x x x1 28 2 55 2 55 15 3 6 22 5 663 2 2 2, , , , , ,r r r r r r 2 » » × + × - × +x x x1 28 13 9 15 3 313 2 2, , , ,r r r r îïåðàöèé ñëîæåíèÿ. Òîãäà îáùàÿ âû÷èñëèòåëüíàÿ ñëîæíîñòü àëãîðèòìà (7)–(12) ñîñòàâëÿåò W W W r r r rîáù ì a= + » × + × + × + × -x x x x0 426 2 55 1 28 13 93 2 3 2, , , , - × + » × + × + - ×x x x x15 3 31 1 7 16 4 31 15 32 3 2 2, , , , , ,r r r r r r îïåðàöèé óìíîæåíèÿ / ñëîæåíèÿ. Ïîñêîëüêó â ðàññìîòðåííîì àëãîðèòìå âû÷èñëåíèÿ (12) âûïîëíÿþòñÿ åäè- íîæäû, à íå x ðàç (â ñëó÷àå âû÷èñëåíèÿ äàííîé îïåðàöèè ñ ïîìîùüþ óêàçàííîãî âûøå àëãîðèòìà [9]), âûèãðûø ïî àääèòèâíîé è îáùåé ñëîæíîñòÿì ñîîòâåò- ñòâåííî ñîñòàâëÿåò d x x x x x xa a a= × + - + - » × + × - × + ×W r r W r r r r * ( ) , ,1 1 28 16 15 32 2 3 2 2 - - × - × + × - » × - »x x x x1 28 13 9 15 3 31 31 31 313 2 2 2 2, , , , , , ,r r r r r r ( )x -1 2 r îïåðàöèé ñëîæåíèÿ, d x x x x xîáù îáù îáù = × + - + - » × + × - ×W r r W r r * ( ) , ,1 1 7 18 5 152 2 3 2 , 3r + + × - × - × - + × » × -x x x x xr r r r r r r 2 3 2 2 2 21 7 16 4 31 15 3 31 31, , , , , , » -31 1 2, ( )x r îïåðàöèé óìíîæåíèÿ/ñëîæåíèÿ. 44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 Ýôôåêòèâíîñòü ðàññìîòðåííûõ àëãîðèòìîâ (3)–(6) è (7)–(12) ñîñòîèò â ìè- íèìèçàöèè èõ îïåðàöèîííîé ñëîæíîñòè ïî ñðàâíåíèþ ñî ñëîæíîñòüþ âû÷èñëå- íèÿ îïåðàöèè (2) ñ ïîìîùüþ ãèáðèäíûõ àëãîðèòìîâ èç ðàáîòû [9]. ÇÀÊËÞ×ÅÍÈÅ Ïðåäñòàâëåííûå â íàñòîÿùåé ñòàòüå áûñòðûå àëãîðèòìû äëÿ áàçîâîé îïåðà- öèè (2), îáëàäàÿ íàèìåíüøåé ïî ñðàâíåíèþ ñ èçâåñòíûìè àëãîðèòìàìè îïåðà- öèîííîé ñëîæíîñòüþ è âûñîêîé ðåãóëÿðíîñòüþ âû÷èñëåíèé, èìåþò ïðàêòè- ÷åñêóþ öåííîñòü è ìîãóò îáåñïå÷èòü ìàêñèìàëüíî ýôôåêòèâíóþ ðåàëèçàöèþ êëåòî÷íûõ ìåòîäîâ ëèíåéíîé àëãåáðû. CÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1.  î å â î ä è í À .  . Î êëàññå êëåòî÷íûõ àëãîðèòìîâ è åãî ñâîéñòâàõ // Âîïðîñû êèáåðíåòèêè. — 1988. — ¹ 135. — Ñ. 50–64. 2. Ë û ñ à í î â Ñ . Þ . Êëåòî÷íûå ìåòîäû ðåøåíèÿ çàäà÷ ëèíåéíîé àëãåáðû // Âîïðîñû êèáåðíå- òèêè. — 1988. — ¹ 135. — Ñ. 64–73. 3. S t r a s s e n V . Gaussian elimination is not optimal // Numerische Mathematik. — 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. L a d e r m a n J . D . A noncommutative algorithm for multiplying 3 ´ 3 matrices using 23 multiplications // Bulletin of the American Mathematical Society. — 1976. — 82, N 1. — P. 126–128. 6. W i n o g r a d S . A . A new algorithm for inner product // IEEE Transactions on Computers. — 1968. — C-18. — P. 693–694. 7. Å ë ô è ì î â à Ë . Ä . , Ê à ï è ò î í î â à Þ .  . Áûñòðûé àëãîðèòì äëÿ óìíîæåíèÿ ìàòðèö è åãî ýôôåêòèâíàÿ ðåàëèçàöèÿ íà ñèñòîëè÷åñêèõ ìàññèâàõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2001. — ¹ 1. — Ñ. 135–150. 8. Å ë ô è ì î â à Ë . Ä . Áûñòðûå ãèáðèäíûå àëãîðèòìû óìíîæåíèÿ ìàòðèö // Êèáåðíåòèêà è ñèñ- òåìíûé àíàëèç. — 2010. — ¹ 4. — Ñ. 49–59. 9. Å ë ô è ì î â à Ë . Ä . Íîâûå áûñòðûå ãèáðèäíûå àëãîðèòìû óìíîæåíèÿ ìàòðèö // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2011. — ¹ 6. — Ñ. 59–67. 10. Å ë ô è ì î â à Ë . Ä . Áûñòðûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö // Êèáåðíåòèêà è ñèñòåì- íûé àíàëèç. — 2008. — ¹ 3. — Ñ. 55–59. 11. Å ë ô è ì î â à Ë . Ä . Ñìåøàííûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö // Êèáåðíåòèêà è ñèñ- òåìíûé àíàëèç. — 2009. — ¹ 1. — Ñ. 22–27. 12. Å ë ô è ì î â à Ë . Ä . Íîâûå êëåòî÷íûå ìåòîäû óìíîæåíèÿ ìàòðèö // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2013. — ¹ 1. — Ñ. 19–29. 13. Å ë ô è ì î â à Ë . Ä . Îáúåäèíåííûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö // Êèáåðíåòèêà è ñèñ- òåìíûé àíàëèç. — 2013. — ¹ 5. — Ñ. 28–37. Ïîñòóïèëà 12.01. 2015 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2015, òîì 51, ¹ 6 45

Ähnliche Einträge