Диссертация (1149591), страница 11
Текст из файла (страница 11)
 äàííîì ñëó÷àå, äëÿ ðåøåíèÿ òð¼õäèàãîíàëüíûõ ÑËÀÓ áûë ðàçðàáîòàí áîëåå ýôôåêòèâíûé àëãîðèòì, îñíîâàííûé íà èäåå ìåòîäà äåêîìïîçèöèè îáëàñòè [92, 93]. Ïðèìåíèòåëüíî ê ÑËÀÓ, îí çàêëþ÷àåòñÿ â ðàçäåëåíèèïîëíîé ìàòðèöû íà íåçàâèñèìûå áëîêè è îäèí ñâÿçóþùèé áëîê [94]. Ñõîäíûå èäåè äëÿ ëåíòî÷íîé ìàòðèöû ïðèâîäÿòñÿ òàêæå â òåõíè÷åñêîì îò÷åòåScaLAPACK [95].Ìåòîä öèêëè÷åñêîé ðåäóêöèè è ìåòîä Âîíãà áûëè îáîáùåíû äëÿ ðàáîòû ñ áëî÷íî-òð¼õäèàãîíàëüíûìè ÑËÀÓ [96].
 äàííîé äèññåðòàöèè ìåòîääåêîìïîçèöèè îáîáùàåòñÿ íà ñëó÷àé òàêèõ ÑËÀÓ. Ìåòîä ñâîäèòñÿ ê ïðåîáðàçîâàíèþ èñõîäíîé áëî÷íî-òð¼õäèàãîíàëüíîé ÑËÀÓ ê ýêâèâàëåíòíîìó âèäóñî ñòðåëîâèäíîé ôîðìîé íîâîé ìàòðèöû ïóòåì ïåðåñòàíîâêè áëî÷íûõ ñòðîêè ñòîëáöîâ èñõîäíîé ñèñòåìû.  ðåçóëüòàòå, ìàòðèöà ÑËÀÓ ëîãè÷åñêè ïðèâîäèòñÿ ê ôîðìå, âêëþ÷àþùåé êðóïíûå ñóïåð-áëîêè íà äèàãîíàëè, äîïóñêàþùèå ïàðàëëåëüíîå îáðàùåíèå, ðàçðåæåííûå ñóïåð-áëîêè âäîëü ïðàâîé èíèæíåé ñòîðîí ìàòðèöû è îäíîãî ñâÿçóþùåãî ñóïåð-áëîêà â ïðàâîì íèæíåìóãëó. Äëÿ îáðàùåíèÿ ñóïåð-áëîêîâ èñïîëüçóåòñÿ ìåòîä ìàòðè÷íîé ïðîãîíêè.Ïîêàçàíî, ÷òî äàííàÿ ñòðåëîâèäíàÿ ñèñòåìà äîïóñêàåò ïàðàëëåëüíîå ðåøåíèå [97, 98]. Äàííûé ìåòîä ÿâëÿåòñÿ áîëåå ýôôåêòèâíûì, ÷åì âñå ïðåäûäóùèå, ïðè êîëè÷åñòâå ïàðàëëåëüíûõ ïðîöåññîðîâ ìíîãî ìåíüøèì ÷èñëà áëîêîâíà äèàãîíàëè.
Âû÷èñëèòåëüíîå óñêîðåíèå ìåòîäà îòíîñèòåëüíî ìåòîäà ìàòðè÷íîé ïðîãîíêè ïîëó÷åíî àíàëèòè÷åñêè. Îíî âû÷èñëÿåòñÿ èç îöåíêè ÷èñëà ìóëüòèïëèêàòèâíûõ îïåðàöèé íà êàæäîì øàãå ìåòîäà è ñðàâíåíèè åãîñ àíàëîãè÷íûìè õàðàêòåðèñòèêàìè ìåòîäà ìàòðè÷íîé ïðîãîíêè.  íàñòîÿùåå âðåìÿ, ïðèëîæåíèÿ ìåòîäà äåêîìïîçèöèè äëÿ áëî÷íî-òð¼õäèàãîíàëüíûõÑËÀÓ ê çàäà÷àì àêóñòèêè è ãåîôèçè÷åñêîãî ìîäåëèðîâàíèÿ èññëåäóþòñÿ âðàáîòàõ [99101].Ðåàëèçîâàííûé ìåòîä ñòðåëîâèäíîé äåêîìïîçèöèè ïîçâîëèë ïðîâåñòèâû÷èñëèòåëüíûå ýêñïåðèìåíòû è ïîäòâåðäèòü àíàëèòè÷åñêèå îöåíêè íà ïðàêòèêå.
 êà÷åñòâå òåñòîâîé ÑËÀÓ èñïîëüçóåòñÿ äèñêðåòèçàöèÿ ãðàíè÷íîé çà73äà÷è äëÿ äâóìåðíîãî èíòåãðî-äèôôåðåíöèàëüíîãî óðàâíåíèÿ Ôàääååâà (4.6).Èñïîëüçîâàíèå ìåòîäà ñòðåëîâèäíîé äåêîìïîçèöèè äëÿ ðåøåíèÿ îðèãèíàëüíîé ÑËÀÓ ïîçâîëèëî óìåíüøèòü îáùåå âðåìÿ âû÷èñëåíèÿ àìïëèòóä ðàññåÿíèÿ â 10−18 ðàç ïî ñðàâíåíèþ ñ èñïîëüçîâàíèåì ìåòîäà ìàòðè÷íîé ïðîãîíêè.5.2.
Ìåòîä ñòðåëîâèäíîé äåêîìïîçèöèè äàííîé ãëàâå äèññåðòàöèè èññëåäóåòñÿ áëî÷íî-òð¼õäèàãîíàëüíàÿ ÑËÀÓ,îïèñûâàåìàÿ óðàâíåíèåìAi Xi−1 + Ci Xi + Bi Xi+1 = Fi ,A1 = BN = 0,(5.1)ãäå Ai , Ci , Bi , i = 1, . . . , N áëîêè ðàçìåðà n × n ìàòðèöû ñèñòåìû. Ýëåìåíòû Fi , ðàçìåðà n × l, ãäå l ≥ 1, â ïðàâîé ÷àñòè ýòî áëîêè ñóïåðâåêòîðàF. Èñêîìûé ñóïåðâåêòîð X ñîñòîèò èç áëîêîâ Xi . Ïîëíûé ðàçìåð ìàòðèöû(nN ) × (nN ).Èäåÿ ìåòîäà ñòðåëîâèäíîé äåêîìïîçèöèè äëÿ N = 15 ïîêàçàíà íà ðèñóíêå 5.1. Èñõîäíàÿ áëî÷íî-òð¼õäèàãîíàëüíàÿ ñèñòåìà (5.1) ëîãè÷åñêè ïðåîáðàçóåòñÿ ê ýêâèâàëåíòíîìó âèäó ñî ñòðåëîâèäíîé ôîðìîé íîâîé ìàòðèöû.Äàííîå ïðåîáðàçîâàíèå îñóùåñòâëÿåòñÿ ñëåäóþùèì îáðàçîì:• Âûáèðàåòñÿ íåêîòîðîå êîëè÷åñòâî íåçàâèñèìûõ ñóïåð-áëîêîâ èëè ïîäñèñòåì, M , íà êîòîðûå èñõîäíàÿ ìàòðèöà áóäåò ðàçäåëåíà.• Ìåæäó äàííûìè ïîäñèñòåìàìè âûáèðàåòñÿ M − 1 áëî÷íûõ ñòðîê-ðàçäåëèòåëåé è ñòîëáöîâ-ðàçäåëèòåëåé. Äàííûå áëî÷íûå ñòðîêè è ñòîëáöûïåðåñåêàþòñÿ íà äèàãîíàëè.• Áëî÷íûå ñòðîêè-ðàçäåëèòåëè âìåñòå ñ ñîîòâåòñòâóþùèìè áëîêàìè âïðàâîé ÷àñòè ÑËÀÓ ñäâèãàþòñÿ â íèæíþþ ÷àñòü ñèñòåìû, ïóòåì ïåðåñòàíîâêè áëî÷íûõ ñòðîê è ñòîëáöîâ.74• Áëî÷íûå ñòîëáöû-ðàçäåëèòåëè ñäâèãàþòñÿ â ïðàâóþ ÷àñòü ìàòðèöû.Äàííîå ïðåîáðàçîâàíèå ïðèâîäèò ê òîìó, ÷òî ñîîòâåòñòâóþùèå áëîêèèñêîìîãî ðåøåíèÿ ïîñëåäîâàòåëüíî ñäâèãàþòñÿ â íèæíþþ ÷àñòü âåêòîðà X. ðåçóëüòàòå, èñõîäíàÿ ÑËÀÓ ïðèâîäèòñÿ â ýêâèâàëåíòíîìó âèäó ñî ñòðåëîâèäíîé ôîðìîé íîâîé ìàòðèöû: íà äèàãîíàëè ðàñïîëîæåíû íåçàâèñèìûåêðóïíûå ñóïåð-áëîêè, âäîëü ïðàâîé è íèæíåé ñòîðîí ìàòðèöû ðàçðåæåííûå ñóïåð-áëîêè, à â ïðàâîì íèæíåì óãëó ìàòðèöà, ñâÿçóþùàÿ ïåðå÷èñëåííûå ýëåìåíòû.Ïîëó÷åííàÿ ýêâèâàëåíòíàÿ ÑËÀÓ ìîæåò áûòü êðàòêî çàïèñàíà â âèäåáëî÷íîé ìàòðèöû 2 × 2SWL WRsF = s .HhFh(5.2)Çäåñü S ñîñòîèò èç íåçàâèñèìûõ ñóïåð-áëîêîâ íà äèàãîíàëè S k , k = 1, .
. . , M .Îñòàëüíûå ýëåìåíòû îáîçíà÷åíû íà ðèñóíêå 5.1. Ðåøåíèå ñèñòåìû (5.2) äàåòñÿ ôîðìóëàìè s = S−1 F − S−1 W hsR. h = H − WL S−1 WR −1 Fh − WL S−1 Fs (5.3)Óðàâíåíèå (5.3) â ïðàâîé ÷àñòè ñîäåðæèò ìàòðè÷íûå óìíîæåíèÿ è îáðàùåíèÿ, êîòîðûå, ïðè äåòàëüíîì ðàññìîòðåíèè, îáëàäàþò áîëüøîé ñòåïåíüþ ïàðàëëåëèçìà. Íåçàâèñèìîñòü ñóïåð-áëîêîâ S k ïîçâîëÿåò âû÷èñëÿòü ïðîèçâåäåíèÿ S−1 Fs , S−1 WR ïàðàëëåëüíî. Áîëåå òîãî, âìåñòî âû÷èñëåíèé îáðàòíûõìàòðèö, äîñòàòî÷íî ïðîñòî ðåøèòü íàáîð ÑËÀÓ çíà÷èòåëüíî ìåíüøåãî ðàçìåðà: SkZk = W kR Skzk = F kk = 1, . . .
, M.(5.4)sÂâèäó ðàçðåæåííîé ñòðóêòóðû ñóïåð-áëîêîâ WL , WR êîëè÷åñòâî óìíîæåíèéïðè ïîñòðîåíèè ìàòðèö H − WL S−1 WR è Fh − WL S−1 Fs òàêæå ìíîãîêðàòíî75ñîêðàùàåòñÿ. Âòîðîå óðàâíåíèå â ñèñòåìå (5.3) ïðåäñòàâëÿåò ñîáîé îïÿòü æåÑËÀÓ ñ áëî÷íî-òð¼õäèàãîíàëüíîé ìàòðèöåé äëÿ ÷àñòè èñêîìîãî ðåøåíèÿ h.Cíà÷àëà âû÷èñëÿåòñÿ ðåøåíèå h = (h1 , . . . , hM −1 )T , à ïîòîì îñòàëüíàÿ ÷àñòü,s, ïîëíîãî ðåøåíèÿ X = (s, h)T îïðåäåëÿåòñÿ ïî ôîðìóëåsk = z k − Z k hk−1 − Z k hk , k = 1, . . .
, M,(5.5)ãäå h0 = hM = 0. äàííîì èññëåäîâàíèè, äëÿ ðåøåíèÿ ñèñòåìû ñ ñóïåð-áëîêîì S k è äëÿâû÷èñëåíèÿ ÷àñòè ðåøåíèÿ h ìû èñïîëüçóåì ìåòîä ìàòðè÷íîé ïðîãîíêè, õîòÿäëÿ ýòèõ îïåðàöèé ìîæíî èñïîëüçîâàòü ìåòîä ñòðåëîâèäíîé äåêîìïîçèöèèâëîæåííî [102].5.3. Ìåòîä ìàòðè÷íîé ïðîãîíêèÄëÿ ïîëíîòû èçëîæåíèÿ, äàäèì êðàòêîå îïèñàíèå ìåòîäà ìàòðè÷íîéïðîãîíêè [87], êîòîðûé òàêæå èçâåñòåí â àíãëîÿçû÷íîé ëèòåðàòóðå êàê ìàòðè÷íûé àëãîðèòì Òîìàñà (Thomas matrix algorithm) [106]. Äàííûé àëãîðèòìïðåäñòàâëÿåò ñîáîé àëãîðèòì Ãàóññà (LU -ðàçëîæåíèå), ïðèìåíÿåìûé ê áëî÷íîòð¼õäèàãîíàëüíîé ìàòðèöå.
Ïðè ýòîì, ìèíèìàëüíûì ýëåìåíòîì äëÿ àëãîðèòìà, â äàííîì ñëó÷àå, ÿâëÿåòñÿ áëîê ìàòðèöû.Ìåòîä ìàòðè÷íîé ïðîãîíêè âêëþ÷àåò â ñåáÿ äâà ýòàïà: ïðÿìîé õîä èîáðàòíûé õîä. Äëÿ ìàòðè÷íîé ñèñòåìû (5.1), ïðÿìîé õîä çàêëþ÷àåòñÿ â ïðèâåäåíèè èñõîäíîé áëî÷íî-òð¼õäèãîíàëüíîé ÑËÀÓ ê ÑËÀÓ ñ âåðõíåé áëî÷íîòð¼õäèàãîíàëüíîé ôîðìîé, ïóòåì ïîñëåäîâàòåëüíîãî âû÷èñëåíèÿ âñïîìîãàòåëüíûõ áëîêîâèA = GB11 1 Ai = Gi Bi ,i = 2, ..., N − 1B = GF11 1 Bi = Gi (Fi − Ai Bi−1 ),76i = 2, ..., N,(5.6)(5.7)Ðèñ. 5.1.
Ïðèìåð ïðåîáðàçîâàíèÿ ÑËÀÓ â ìåòîäå ñòðåëîâèäíîé äåêîìïîçèöèè. Âåðõíèéðèñóíîê: èñõîäíàÿ ÑËÀÓ ñ âûäåëåíèåì áëîêîâ, êîòîðûå áóäóò ïåðåñòàâëåíû. Ñðåäíèéðèñóíîê: ïðåîáðàçîâàííàÿ ÑËÀÓ ñ ìàòðèöåé ñòðåëîâèäíîé ôîðìû. Íèæíèé ðèñóíîê: îáîçíà÷åíèÿ ýëåìåíòîâ ïðåîáðàçîâàííîé ÑËÀÓ ñ ìàòðèöåé ñòðåëîâèäíîé ôîðìû, ïðèíÿòûåâ äàííîé ñòàòüå.77−1ãäå G1 = C1−1 è Gi = (Ci − Ai Ai−1 ) . Îáðàòíûé õîä çàêëþ÷àåòñÿ â ïîñëåäîâàòåëüíîì âû÷èñëåíèè ÷àñòåé ðåøåíèÿ ÑËÀÓ, íà÷èíàÿ ñ ïîñëåäíåé áëî÷íîéñòðîêè, ïî ôîðìóëàì, èñïîëüçóþùèì âñïîìîãàòåëüíûå áëîêè, ïîëó÷åííûå íàïðÿìîì õîäå ïðîãîíêè:X = BNN Xi = Bi − Ai Xi+1 ,i = N − 1, .
. . , 1. ðåçóëüòàòå, ìû ïîëó÷àåì ðåøåíèå X ñèñòåìû (5.1).Íåîáõîäèìî îòìåòèòü, ÷òî ìåòîä ìàòðè÷íîé ïðîãîíêè ÿâëÿåòñÿ ïîñëåäîâàòåëüíûì: ñëåäóþùèé âñïîìîãàòåëüíûé áëîê èëè æå ñëåäóþùàÿ ÷àñòü âåêòîðà ðåøåíèÿ ïîëó÷àåòñÿ òîëüêî èç ïðåäûäóùåãî ýëåìåíòà. Ïîýòîìó ðàñïàðàëëåëèòü äàííûé ìåòîä è, òåì ñàìûì, óìåíüøèòü âðåìÿ âû÷èñëåíèé ìîæíîòîëüêî ïóòåì ïàðàëëåëèçàöèè ìàòðè÷íûõ îïåðàöèé îáðàùåíèÿ è óìíîæåíèÿáëîêîâ â ôîðìóëàõ (5.7-5.3).5.4. Âû÷èñëèòåëüíîå óñêîðåíèåÂû÷èñëèòåëüíîå óñêîðåíèå ìåòîäà ñòðåëîâèäíîé äåêîìïîçèöèè ïî îòíîøåíèþ ê ïîñëåäîâàòåëüíîìó ìåòîäó ìàòðè÷íîé ïðîãîíêè ìîæíî îöåíèòü êàêîòíîøåíèå âðåìåíè âû÷èñëåíèÿ ðåøåíèÿ ÑËÀÓ ìåòîäîì ïðîãîíêè ê ñîîòâåòñòâóþùåìó âðåìåíè ìåòîäà äåêîìïîçèöèè.
Âðåìÿ âû÷èñëåíèÿ íåïîñðåäñòâåííî ñâÿçàíî ñ ÷èñëîì ïîñëåäîâàòåëüíûõ îïåðàöèé êàæäîãî ìåòîäà. Êîëè÷åñòâîïîñëåäîâàòåëüíûõ ìóëüòèïëèêàòèâíûõ îïåðàöèé ìåòîäà ñòðåëîâèäíîé äåêîìïîçèöèè áûëî ñîñ÷èòàíî è, êàê ñëåäñòâèå, îöåíåíî âû÷èñëèòåëüíîå óñêîðåíèå.Àääèòèâíûå îïåðàöèè íå ó÷èòûâàëèñü, ñ÷èòàÿ, ÷òî îíè òðåáóþò çíà÷èòåëüíîìåíüøåãî êîìïüþòåðíîãî âðåìåíè. ñîîòâåòñòâèè ñ ðàáîòîé [103], ìû ñ÷èòàåì, ÷òî, êàê äëÿ óìíîæåíèÿ,òàê è äëÿ îáðàùåíèÿ áëîêà ðàçìåðà n × n òðåáóåòñÿ ðîâíî n3 ìóëüòèïëèêàòèâíûõ îïåðàöèé. Äàííàÿ îöåíêà ñîãëàñóåòñÿ ñ îöåíêîé êîëè÷åñòâà îïåðàöèéâ îáùåïðèíÿòîé ðåàëèçàöèè äàííûõ àëãîðèòìîâ [104], à èìåííî LAPACK.78Êîëè÷åñòâî ìóëüòèïëèêàòèâíûõ îïåðàöèé äëÿ âû÷èñëåíèÿ âñïîìîãàòåëüíûõ áëîêîâ è ÷àñòåé âåêòîðà ðåøåíèÿ â ìåòîäå ìàòðè÷íîé ïðîãîíêè ëåãêîîöåíèâàåòñÿ è ïðèâîäèòñÿ â òàáëèöå (5.1). Ïîëíîå ÷èñëî ìóëüòèïëèêàòèâíûõîïåðàöèé ïîñëåäîâàòåëüíîãî ìåòîäà ìàòðè÷íîé ïðîãîíêè äàåòñÿ ôîðìóëîéOM S = (3N − 2)(n3 + n2 l).Äëÿ ìåòîäà äåêîìïîçèöèè ïîëíîå êîëè÷åñòâî îïåðàöèé óìíîæåíèÿ òàêæå áûëî íàéäåíî:− 1)n l +(4N1 − 1)n + (4N1 − 1)n l + (6NM − 3)n + (4NMM−1 X32+7Nk n + 5Nk n l + (3M − 5)(n3 + n2 l).3232(5.8)k=2Çäåñü Nk , k = 1, .
. . , M îáîçíà÷àåò êîëè÷åñòâî áëîêîâ íà äèàãîíàëè ñóïåðáëîêà S k . Ïîñëåäíåå ñëàãàåìîå ñîîòâåòñòâóåò ÷èñëó îïåðàöèé óìíîæåíèÿ äëÿðåøåíèÿ âòîðîãî óðàâíåíèÿ â ñèñòåìå (5.3).  îáùåì ñëó÷àå Nk ìîãóò áûòüðàçëè÷íûìè, íî óäîâëåòâîðÿþò ñîîòíîøåíèþMXNk = N − (M − 1).k=1Ìàêñèìàëüíîå óñêîðåíèå äîñòèãàåòñÿ, êîãäà âðåìÿ ðàáîòû êàæäîãî ïðîöåññîðà ïî ðåøåíèþ ñèñòåìû ñ ñóïåð-áëîêîì S k îäèíàêîâî.  ýòîì ñëó÷àå Nkðàâíû äðóã äðóãó ïðè k = 2, . .
. , M − 1, à N1 è NM íåñêîëüêî áîëüøå îñòàëüíûõ. Âûèãðûø â ïðîèçâîäèòåëüíîñòè ïî ñðàâíåíèþ ñî ñëó÷àåì, êîãäà âñå Nk ,k = 1, . . . , M ðàâíû äðóã äðóãó äîñòàòî÷íî ìàë. Ïîýòîìó, äëÿ ïðîñòîòû, ìûðàññìîòðèì ñëó÷àé ðàâåíñòâà âñåõ Nk äðóã äðóãó:Nk =N −M +1.M ýòîì ñëó÷àå, åñëè êîëè÷åñòâî ïàðàëëåëüíûõ ïðîöåññîðîâ ðàâíî ÷èñëó áëîêîâ M íà äèàãîíàëè, òî ÷èñëî ïîñëåäîâàòåëüíûõ îïåðàöèé óìíîæåíèÿ ìåòîäàñòðåëîâèäíîé äåêîìïîçèöèè áóäåò ðàâíîOAD = ((N − M + 1) /M ) (7n3 + 5n2 l) + (3M − 5)(n3 + n2 l)79Computational speedupn=400, N=30712220181614121086421 RHS vector100 RHS vectors200 RHS vectors400 RHS vectors020406080100Number of processors120140Ðèñ.
5.2. Àíàëèòè÷åñêàÿ îöåíêà âû÷èñëèòåëüíîãî óñêîðåíèÿ ìåòîäà ñòðåëîâèäíîé äåêîìïîçèöèè ïî îòíîøåíèþ ê ìåòîäó ìàòðè÷íîé ïðîãîíêè â çàâèñèìîñòè îò ÷èñëà ïàðàëëåëüíûõïðîöåññîðîâ (M ) äëÿ ðàçíîãî ÷èñëà âåêòîðîâ â ïðàâîé ÷àñòè ÑËÀÓ (RHS ). Íà÷àëüíûåïàðàìåòðû ìàòðèöû: ðàçìåð êàæäîãî áëîêà n = 400, ÷èñëî áëîêîâ íà äèàãîíàëè N = 3071.×èñëî âåêòîðîâ â ïðàâîé ÷àñòè ìåíÿåòñÿ îò 1 äî 400.Âû÷èñëèòåëüíîå óñêîðåíèå ðàñ÷èòûâàåòñÿ êàê îòíîøåíèå ïîñëåäîâàòåëüíûõîïåðàöèé óìíîæåíèÿ êàæäîãî ìåòîäà:S = OM S /OAD .Òàêèì îáðàçîì, âû÷èñëèòåëüíîå óñêîðåíèå ëåãêî ïîëó÷àåòñÿ â âèäåS=3N − 23M − 5 + 5 +21+l/n∼N −M +1M73M1+MN.(5.9)Ãðàôèê âû÷èñëèòåëüíîãî óñêîðåíèÿ îò ÷èñëà ïàðàëëåëüíûõ ïðîöåññîðîâ äëÿn = 400 è N = 3071 ïîêàçàí íà ðèñóíêå 5.2.
Ëåãêî âèäåòü, ÷òî çàâèñèìîñòüâû÷èñëèòåëüíîãî óñêîðåíèÿ îò îòíîøåíèÿ l/n äîñòàòî÷íî ñëàáàÿ. Êàê ôóíêöèÿ M , óñêîðåíèå âåäåò ñåáÿ ëèíåéíî S = 3M/7 ïðè M N . Ïðè äàëüíåéøåì óâåëè÷åíèè M , óñêîðåíèå äîñòèãàåò ñâîåãî ìàêñèìóìà è ïîòîì óáûâàåò.Äëÿ äàííûõ ïàðàìåòðîâ N è l, ÷èñëî ïàðàëëåëüíûõ ïðîöåññîðîâ, ïðè êîòîðîì80âû÷èñëèòåëüíîå óñêîðåíèå äîñòèãàåò ñâîåãî ìàêñèìóìà, äàåòñÿ ôîðìóëîésM∗ =(N + 1)25+.31 + l/n(5.10) äàííîì ñëó÷àå, ìåòîä ñòðåëîâèäíîé äåêîìïîçèöèè ìàêñèìàëüíî â 18 − 20ðàç áûñòðåå ìåòîäà ìàòðè÷íîé ïðîãîíêè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
