=Paper=
{{Paper
|id=Vol-1482/509
|storemode=property
|title=Универсальный метод Ланцоша-Паде решения линейных систем над большими конечными полями
(Universal block Lanczos-Pade method for linear systems over large finite fields)
|pdfUrl=https://ceur-ws.org/Vol-1482/509.pdf
|volume=Vol-1482
}}
==Универсальный метод Ланцоша-Паде решения линейных систем над большими конечными полями
(Universal block Lanczos-Pade method for linear systems over large finite fields)==
https://ceur-ws.org/Vol-1482/509.pdf
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Óíèâåðñàëüíûé ìåòîä Ëàíöîøà-Ïàäå ðåøåíèÿ
∗
ëèíåéíûõ ñèñòåì íàä áîëüøèìè êîíå÷íûìè ïîëÿìè
2 1
Í.Ë. Çàìàðàøêèí , Ì.À. ×åðåïíåâ
1 2
Ì Ó , ÈÂÌ ÀÍ
Ïðåäëîæåí óíèâåðñàëüíûé ìåòîä, ïðåäíàçíà÷åííûé äëÿ ðåøåíèÿ áîëüøèõ ðàç-
ðåæåííûõ ñèñòåì ëèíåéíûõ óðàâíåíèé íàä êîíå÷íûìè ïîëÿìè ñ áîëüøèì ÷èñëîì
ýëåìåíòîâ, êîòîðûå âîçíèêàþò ïðè ðåøåíèè çàäà÷è äèñêðåòíîãî ëîãàðè ìèðî-
âàíèÿ ïî ìîäóëþ ïðîñòîãî ÷èñëà. Ïðåäëîæåíû ý åêòèâíûå ñïîñîáû ïðåäñòàâ-
ëåíèÿ è ðàñïðåäåëåíèÿ äàííûõ, à òàêæå ïðîãðàììíûå ðåàëèçàöèè ïàðàëëåëüíûõ
àëãîðèòìîâ.
1. Ââåäåíèå
Îäíèì èç ìåòîäîâ, êîòîðûå èñïîëüçóþòñÿ äëÿ ðåøåíèÿ áîëüøèõ ðàçðåæåííûõ ñèñòåì
íàä êîíå÷íûìè ïîëÿìè, ÿâëÿåòñÿ ìåòîä Ëàíöîøà (ñì., íàïðèìåð [29,11,12℄). Ïðîñòîòà àëãî-
ðèòìà è âîçìîæíîñòü ïîñòîÿííîãî êîíòðîëÿ êîððåêòíîñòè åãî ðàáîòû îòíîñÿòñÿ ê ãëàâíûì
äîñòîèíñòâàì ìåòîäà. Îäíàêî ïî ñâîåé ïðèðîäå ìåòîä Ëàíöîøà ÿâëÿåòñÿ ïîñëåäîâàòåëü-
íûìè àëãîðèòìîì, íà êàæäîé èòåðàöèè êîòîðîãî íåèçáåæíî ïðîèñõîäèò áîëüøîé îáìåí
äàííûìè ìåæäó ðàçëè÷íûìè âû÷èñëèòåëüíûìè óçëàìè.
Èñïîëüçîâàíèå áëî÷íûõ âåðñèé íåñêîëüêî óëó÷øàåò ìàñøòàáèðóåìîñòü ïàðàëëåëüíûõ
ïðîãðàìì (ñì. íàïðèìåð, [12℄), íî òàê èëè èíà÷å íå ïîçâîëÿåò ý åêòèâíî èñïîëüçîâàòü
âû÷èñëèòåëüíûå ñèñòåìû ñ ïðîèçâîäèòåëüíîñòüþ áîëåå 100 TFlops. Íåñîâåðøåíñòâî ìåòîäà
ñòàíîâèòñÿ òåì çàìåòíåå, ÷åì íèæå ñêîðîñòü îáìåíà äàííûìè â êîììóíèêàöèîííîé ñåòè
âû÷èñëèòåëüíîé ñèñòåìû.
 ðàáîòå îïèñàí óíèâåðñàëüíûé áëî÷íûé ìåòîä Ëàíöîøà-Ïàäå, ïðåäíàçíà÷åííûé äëÿ
ðåøåíèÿ áîëüøèõ ðàçðåæåííûõ ñèñòåì ëèíåéíûõ óðàâíåíèé íàä êîíå÷íûìè ïîëÿìè ñ áîëü-
øèì ÷èñëîì ýëåìåíòîâ (¾óíèâåðñàëüíûé¿ îçíà÷àåò ¾ý åêòèâíûé íà ïàðàëëåëüíûõ âû-
÷èñëèòåëüíûõ ñèñòåìàõ ñ ðàçëè÷íîé àðõèòåêòóðîé è õàðàêòåðèñòèêàìè¿), à òàêæå ïðåäëà-
ãàþòñÿ ý åêòèâíûå ñïîñîáû ïðåäñòàâëåíèÿ äàííûõ, ðàñïðåäåëåíèÿ äàííûõ ïî âû÷èñëè-
òåëüíûì óçëàì è ïàðàëëåëüíûå àëãîðèòìû.
Óíèâåðñàëüíûé ìåòîä Ëàíöîøà-Ïàäå, ñîõðàíÿÿ îñíîâíûå äîñòîèíñòâà ìåòîäà Ëàíöî-
øà, îáëàäàåò ñóùåñòâåííî ëó÷øèìè ïàðàëëåëüíûìè ñâîéñòâàìè. Áîëåå òîãî â óíèâåðñàëü-
íîì ìåòîäå Ëàíöîøà-Ïàäå èìååòñÿ âîçìîæíîñòü ãèáêî óïðàâëÿòü ñëîæíîñòüþ âû÷èñëåíèé
è ðàçìåðîì îáìåíèâàåìûõ äàííûõ.
2. Îïèñàíèå óíèâåðñàëüíîãî ìåòîäà Ëàíöîøà-Ïàäå
2.1. A-îðòîãîíàëüíûé áàçèñ ïðîñòðàíñòâà Êðûëîâà è ìàòðè÷íûå ïðèáëè-
æåíèÿ Ïàäå
Íàì ïîòðåáóåòñÿ ðÿä êîíñòðóêöèé, ÷òîáû óñòàíîâèòü ñâÿçü ìåæäó ìàòðè÷íûìè ïðèáëè-
æåíèÿìè Ïàäå íåêîòîðîãî ñïåöèàëüíîãî ðÿäà è A-îðòîãîíàëüíûìè áàçèñàìè ïðîñòðàíñòâà
Êðûëîâà K(A, B).
Èòàê, ïóñòü α(x) îðìàëüíûé ìàòðè÷íûé ðÿä
∞
X
α(x) = αi x−i , (1)
i=0
àáîòà âûïîëíåíà ïðè èíàíñîâîé ïîääåðæêå Ìèíîáðíàóêè îññèè, ñîãëàøåíèå îò 17 èþíÿ 2014 ã.
∗
N 14.604 .21.0034 (èäåíòè èêàòîð ñîãëàøåíèÿ RFMEFI60414X0034).
509
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
êîý èöèåíòàìè êîòîðîãî ÿâëÿþòñÿ ìàòðèöû αi ∈ FK×K . Áóäåì ãîâîðèòü, ÷òî ïàðà ìàò-
ðè÷íûõ ïîëèíîìîâ Q(s) (x) è P (s) (x) ñòåïåíè s
(s) (s)
Q(s) (x) = Q0 + Q1 x + · · · + Q(s) s
s x ,
(s) (s)
P (s) (x) = P0 + P1 x + · · · + Ps(s) xs ,
(s) (s)
ñ êîý èöèåíòàìè Qi , Pj ∈ FK×K , çàäàåò ìàòðè÷íîå ïðèáëèæåíèå Ïàäå ñòåïåíè s äëÿ
ðÿäà (1), åñëè âûïîëíÿåòñÿ ñîîòíîøåíèå:
∞
(s)
X
α(x)Q(s) (x) − P (s) (x) = ρi x−i . (2)
i=s+1
ÿä â ïðàâîé ÷àñòè (2) áóäåì íàçûâàòü îñòàòî÷íûì ðÿäîì ïðèáëèæåíèÿ Ïàäå P (s) (x),
Q(s) (x) ñòåïåíè s è îáîçíà÷àòü åãî ÷åðåç R(s) (x).
Äàëåå, äëÿ ðÿäà (1) è ïàðû ïðîèçâîëüíûõ ìàòðè÷íûõ ïîëèíîìîâ îïðåäåëèì áèëèíåéíîå
îòîáðàæåíèå. À èìåííî, ïóñòü Q1 (x) è Q2 (x) äâà ìàòðè÷íûõ ïîëèíîìà. àññìîòðèì ðÿä,
ïîëó÷åííûé îðìàëüíûì ïðîèçâåäåíèåì QT
1 (x), α(x) è Q2 (x),
∞
X
QT1 (x)α(x)Q2 (x) = γi x−i . (3)
i=−t
Òîãäà çíà÷åíèå áèëèíåéíîãî îòîáðàæåíèÿ < Q1 , Q2 > äëÿ ïàðû ïîëèíîìîâ Q1 è Q2 îïðå-
äåëÿåòñÿ êàê çíà÷åíèå êîý èöèåíòà γ1 îðìàëüíîãî ðÿäà (3):
< Q1 , Q2 >= γ1 ∈ FK×K . (4)
Íàêîíåö, óñòàíîâèì ñïîñîá ïîñòðîåíèÿ áëîêà Q ðàçìåðà n×K ïî çàäàííîìó ìàòðè÷íîìó
Q ïîëèíîìó Q(x), êâàäðàòíîé n × n ìàòðèöå A è n × K áëîêó B . Äëÿ ýòîãî ðàññìîòðèì
ïîëèíîì Q(x) ñòåïåíè s ñ ìàòðè÷íûìè êîý èöèåíòàìè Q0 , Q1 , · · · , Qs :
Q(x) = Q0 + Q1 x + · · · + Qs xs .
Îïðåäåëèì áëîê Q = Q(A, B) ∈ Fn×K ïî ñëåäóþùåìó ïðàâèëó (ñì. íàïðèìåð, [9℄):
Q = Q(A, B) = BQ0 + ABQ1 + · · · + As BQs . (5)
 äàëüíåéøåì íàñ áóäóò èíòåðåñîâàòü òîëüêî òå ðÿäû α(x) âèäà (1), êîý èöèåíòû αi
êîòîðûõ çàäàþòñÿ íåêîòîðûì ñïåöèàëüíûì îáðàçîì, à èìåííî
αi = αiT = B T Ai B,
ñ ñèììåòðè÷íîé ìàòðèöåé A, è íåêîòîðûì áëîêîì B .
Ëåììà 1. [9℄Ñïðàâåäëèâî ñëåäóþùåå ðàâåíñòâî:
< Q1 , Q2 >= QT1 AQ2 (6)
Óòâåðæäåíèå 1. Ïóñòü A ∈ F
n×n ñèììåòðè÷íàÿ ìàòðèöà, B ∈ Fn×K áëîê èç K ëèíåé-
íî íåçàâèñèìûõ âåêòîðîâ, à αi ∈ FK×K êâàäðàòíûå ìàòðèöû âèäà αi = αiT = B T Ai B.
àññìîòðèì ïðèáëèæåíèÿ Ïàäå P (s) (x), Q(s) (x) ðÿäà (1) ñòåïåíåé 0, · · · , l,
∞
(0)
X
α(x)Q(0) (x) − P (0) (x) = ρi x−i ,
i=1
∞
(1)
X
α(x)Q(1) (x) − P (1) (x) = ρi x−i ,
i=2
··· ··· ··· ,
∞
(l)
X
(l) (l)
α(x)Q (x) − P (x) = ρi x−i ,
i=l+1
510
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
ïðåäïîëàãàÿ, ÷òî ìàòðèöû Q(s) (A, B)T AQ(s) (A, B) ÿâëÿþòñÿ íåâûðîæäåííûìè.
Òîãäà, äëÿ ëþáîãî s, 0 ≤ s ≤ l áëîêè Q0 = Q
(0) (A, B), · · · , Q = Q(l) (A, B), ïîñòðîåí-
l
íûå ïî Q-ïîëèíîìàì ïðèáëèæåíèé Ïàäå, çàäàþò A-îðòîãîíàëüíûé áàçèñ ïðîñòðàíñòâà
Êðûëîâà Kl (A, B)
Kl (A, B) = Span B, AB, · · · , Al B .
(s)T (s)
Êðîìå òîãî, Q(s) (A, B)T AQ(s) (A, B) = Qs ρs+1 , è ñòàðøèå êîý èöèåíòû ìàòðè÷íûõ
Q-ïîëèíîìîâ è ñòàðøèå êîý èöèåíòû ñîîòâåòñòâóþùèõ îñòàòî÷íûõ ðÿäîâ, ñòîÿùèå
â ïîñëåäíåì ðàâåíñòâå ñïðàâà, ÿâëÿþòñÿ íåâûðîæäåííûìè ìàòðèöàìè. ✷
Óòâåðæäåíèå 1 ïðåäîñòàâëÿåò ñïîñîá îïèñàíèÿ A-îðòîãîíàëüíîãî áàçèñà ïðîñòðàíñòâà
Êðûëîâà K(A, B) ñ ïîìîùüþ Q-ïîëèíîìîâ.
2.2. åêóððåíòíûå îðìóëû äëÿ ïðèáëèæåíèé Ïàäå
Ïðåäïîëîæèì, ÷òî óæå èçâåñòíû ïðèáëèæåíèÿ Ïàäå P (s−1) , Q(s−1) è P (s) , Q(s) ïîðÿäêîâ
s − 1 è s (çäåñü è âåçäå äàëåå âåðõíèé èíäåêñ â êðóãëûõ ñêîáêàõ ãîâîðèò î òîì, ê êàêîìó
ïîðÿäêó ïðèáëèæåíèÿ Ïàäå îòíîñèòñÿ äàííàÿ âåëè÷èíà), ñîîòâåòñòâåííî, ñ îñòàòî÷íûìè
ðÿäàìè R(s−1) (x) è R(s) (x)
∞
(s−1) −i
X
R(s−1) (x) = α(x)Q(s−1) (x) − P (s−1) (x) = ρi x ,
i=s
∞
(s)
X
R(s) (x) = α(x)Q(s) (x) − P (s) (x) = ρi x−i .
i=s+1
Íîâîå ïðèáëèæåíèå Ïàäå Q(s+1) (x), P (s+1) (x) ñòåïåíè s + 1 áóäåì èñêàòü â âèäå
Q(s+1) (x) = xQ(s) (x) + Q(s) (x)ν0 + Q(s−1) (x)ν1 , (7)
(s+1) (s) (s) (s−1)
P (x) = xP (x) + P (x)ν0 + P (x)ν1 , (8)
(s+1) (s) (s) (s−1)
R (x) = xR (x) + R (x)ν0 + R (x)ν1 , (9)
ãäå ν0 è ν1 K × K ìàòðèöû, òðåáóþùèå îïðåäåëåíèÿ. Èç óñëîâèÿ ðàâåíñòâà íóëþ êî-
(s+1) (s+1)
ý èöèåíòîâ ρs è ρs+1 îñòàòêà ðÿäà Ïàäå R(s+1) (x), ñëåäóåò, ÷òî ìàòðèöû ν0 è ν1
óäîâëåòâîðÿþò ñèñòåìå ëèíåéíûõ óðàâíåíèé
(s)
ρs+1 + ρs(s−1) ν1 = ρ(s+1)
s = 0, (10)
(s) (s) (s−1) (s+1)
ρs+2 + ρs+1 ν0 + ρs+1 ν1 = ρs+1 = 0. (11)
(s+1)
Îñòàâøèåñÿ êîý èöèåíòû ρs+k+1 îñòàòêà R(s+1) (x) k > 0 ïîëó÷àþòñÿ ïî ñëåäóþùåé
îðìóëå:
(s+1) (s) (s) (s−1)
ρs+k+1 = ρs+k+2 + ρs+k+1 ν0 + ρs+k+1 ν1 .
Ñëåäóÿ (7), çàïèøåì äëÿ ïîëèíîìà Q(s+1) (x)
Q(s+1) (x) = Q(s) (x) (Ix + ν0 ) + Q(s−1) (x)ν1 . (12)
Ïðèìåíÿÿ äàííîå ïðåîáðàçîâàíèå t ðàç, ïîëó÷èì ïðåäñòàâëåíèå äëÿ ïîëèíîìà Q(s+t) (x) â
âèäå:
(t) (t)
Q(s+t) (x) = Q(s) (x)H1s (x) + Q(s−1) (x)H0s (x), (13)
(t)
ãäå H1s (x) ìàòðè÷íûé ïîëèíîì ñòåïåíè t, ñòàðøèé êîý èöèåíò êîòîðîãî åäèíè÷íàÿ
(t)
K × K ìàòðèöà, à H0s (x) íåêîòîðûé ìàòðè÷íûé ïîëèíîì ñòåïåíè íå âûøå t − 1.
511
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Ïîäõîä ê âû÷èñëåíèþ A-îðòîãîíàëüíîãî áàçèñà, îñíîâàííûé íà ïðèáëèæåíèÿõ Ïàäå,
èìååò âèäèìûå ïðåèìóùåñòâà ñ òî÷êè çðåíèÿ ïàðàëëåëüíûõ âû÷èñëåíèé.  êëàññè÷åñêîì
ìåòîäå Ëàíöîøà èòåðàöèÿ àëãîðèòìà ñîñòîèò èç óìíîæåíèÿ ìàòðèöû A íà áëîê Qi è ïî-
ñëåäóþùåé ïðîöåäóðû A-îðòîãîíàëèçàöèè íîâîãî áëîêà ê ïðåäûäóùèì. Êàæäàÿ òàêàÿ èòå-
ðàöèÿ òðåáóåò çíà÷èòåëüíîãî îáìåíà äàííûìè, ÷òî ïðèâîäèò ê ïëîõîé ìàñøòàáèðóåìîñòè
àëãîðèòìà íà ìîùíûõ âû÷èñëèòåëÿõ. Äëÿ ìåòîäà Ëàíöîøà-Ïàäå òðåáóåòñÿ òîëüêî óìíî-
æàòü áëîê íà ìàòðèöó. Êàæäûé âåêòîð â áëîêå óìíîæàåòñÿ íåçàâèñèìî, à ÷èñëî îáìåíîâ
ìèíèìàëüíî. Ýòî è åñòü ãëàâíîå ïðåèìóùåñòâî ìåòîäà Ëàíöîøà-Ïàäå ïåðåä ìåòîäîì Ëàí-
öîøà.
2.3. Ìàòðè÷íûå îáîçíà÷åíèÿ
Íå ñëîæíî ïðîâåðèòü, ÷òî ïîëèíîìû Q(0) (x) è Q(1) (x), âçÿòûå â âèäå Q(0) (x) = I è
Q(1) (x) = Ix − α1−1 α2 , ñ α1 = B T AB è α2 = B T A2 B , ÿâëÿþòñÿ Q-ïîëèíîìàìè Ïàäå íóëåâîé
è ïåðâîé ñòåïåíè ñîîòâåòñòâåííî. Èñïîëüçóÿ ÷àñòíûé ñëó÷àé ñîîòíîøåíèÿ (13), ïðåäñòàâèì
Q-ïîëèíîì Ïàäå ñòåïåíè s + 1 â âèäå
(s+1) (s+1)
Q(s+1) (x) = Q(1) (x)H1 (x) + Q(0) (x)H0 (x), (14)
(s+1)
ñ ìàòðè÷íûì ïîëèíîìîì H1 (x) ñòåïåíè s è ñòàðøèì êîý èöèåíòîì, ðàâíûì åäèíè÷íîé
(s+1)
ìàòðèöå, è íåêîòîðûì ìàòðè÷íûì ïîëèíîì H0 (x) ñòåïåíè íå âûøå s − 1. Èç (12) è
(s+1) (s+1)
(14) ñëåäóåò, ÷òî H1 (x) è H0 (x) óäîâëåòâîðÿþò îäíîìó è òîìó æå ðåêóððåíòíîìó
ñîîòíîøåíèþ
(s+1) (s) (s−1)
H1 (x) = H1 (x) (Ix + ν0 ) + H1 (x)ν1 (15)
(s+1) (s) (s−1)
H0 (x) = H0 (x) (Ix + ν0 ) + H0 (x)ν1 , (16)
îòëè÷àÿñü òîëüêî âûáîðîì íà÷àëüíûõ óñëîâèé. À èìåííî, íà÷àëüíûå ïîëèíîìû âûáèðàþòñÿ
(0) (1) (0) (1)
â ñëåäóþùåì âèäå: H1 (x) = 0, H1 (x) = I , H0 (x) = I , H0 (x) = 0.
Äëÿ óäîáñòâà äàëüíåéøåé çàïèñè àëãîðèòìîâ îïðåäåëèì ñïåöèàëüíûå ìàòðè÷íûå îáî-
(s) (s) (s) (s)
çíà÷åíèÿ. Ñîñòàâèì èç êîý èöèåíòîâ ïîëèíîìîâ H1 (x) è H0 (x) áëîêè H1 è H0 ðàç-
ìåðà n×K , ðàñïîëîæèâ êîý èöèåíòû ìåíüøèõ ñòåïåíåé â ñòðîêàõ ñ áîëüøèìè íîìåðàìè:
0 0
··· ···
0
0
(s)
(s)
H
1(s−1)
(s)
0
H1 = , H0 = . (17)
(s) (s)
H1(s−2) H0(s−2)
··· ···
(s)
H11
(s)
H01
(s) (s)
H10 H00
 òàêîì ñëó÷àå ðåêóððåíòíûå ñîîòíîøåíèÿ (15) è (16) ýêâèâàëåíòíû ñëåäóþùèì ìàòðè÷-
512
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
íûì ðàâåíñòâàì:
I
(s+1)
Hi = (s) (s) (s−1)
ν0 , i = 0, 1, (18)
ZHi Hi Hi
ν1
ãäå Z ∈ Fn×n ìàòðèöà áëî÷íîãî ñäâèãà âèäà
0 Ik 0 ··· 0
0 0 Ik 0
···
Z= ··· ··· ··· ··· .
···
0 0 0 ··· Ik
0 0 0 ··· 0
(s) (s)
Íàðÿäó ñ áëîêàìè H0 è H1 îïðåäåëèì áëîê R(s) ðàçìåðà 2n × K , êîòîðûé ñîîòâåòñòâóåò
îñòàòî÷íîìó ðÿäó Ïàäå ñòåïåíè s (çàìåòèì, ÷òî ðàçìåð áëîêîâ R âäâîå ïðåâîñõîäèò ðàçìåð
áëîêîâ H ). ßâíûé âèä áëîêà R(s) çàäàäèì ñëåäóþùèì îáðàçîì:
⋆
⋆
ρ (s)
2 n −s
K
···
R(s) = , (19)
(s)
ρs+1
0
···
0
ãäå ñèìâîëîì ⋆ îáîçíà÷àþòñÿ òå ýëåìåíòû, êîòîðûå íå ÿâëÿþòñÿ ñóùåñòâåííûìè (äðóãèìè
ñëîâàìè çíà÷åíèÿ ýòèõ ýëåìåíòîâ íå áóäóò âëèÿòü íà âû÷èñëåíèÿ â àëãîðèòìå). ×èñëî
íóëåâûõ ìàòðèö â R(s) â òî÷íîñòè ðàâíî s + 1, è îòðàæàåò òîò àêò, ÷òî R(s) ñîîòâåòñòâóåò
îñòàòî÷íîìó ðÿäó Ïàäå ñòåïåíè s. Ïî àíàëîãèè ñ îðìóëàìè (18) çàïèøåì
I
R(s+1) = Z T R(s) R(s) R(s−1) (20)
ν 0
ν1
Çàìåòèì, ÷òî â ñîîòâåòñòâèè ñ îïðåäåëåíèåì ÷èñëî ¾íåñóùåñòâåííûõ¿ ýëåìåíòîâ â R(s+1)
óâåëè÷èâàåòñÿ íà 1 ïî ñðàâíåíèþ ñ ÷èñëîì ¾íåñóùåñòâåííûõ¿ ýëåìåíòîâ â R(s) . Òàêèì
îáðàçîì, îðìóëà (20) ìîæåò ðàññìàòðèâàòüñÿ êàê ðàâåíñòâî òîëüêî äëÿ ¾ñóùåñòâåííûõ¿
êîìïîíåíò R(s+1) .
513
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Äàëåå, îáîçíà÷èì ÷åðåç Q1 è Q0 áëîêè Q1 (A, B) è Q0 (A, B), ñîîòâåòñòâåííî. Ïî îïðå-
äåëåíèþ Q0 = B , à Q1 = AB − Bα1−1 α2 . Ñîñòàâèì ìàòðèöû K0 , K1 ∈ Fn×n èç áëîêîâ âèäà
Aj Q0 è Aj Q1 ñ j îò 0 äî K
n
− 1 çàïèñàííûõ â îáðàòíîì ïîðÿäêå,
(21)
n n
K0 = A K −1 Q0 A K −2 Q0 · · · AQ0 Q0
n n
K1 = −1 −2
A K Q1 A K Q1 · · · AQ1 Q1
Èç (13) ñëåäóåò, ÷òî äëÿ áëîêà Qs+1 = Q(s+1) (A, B) ñïðàâåäëèâî ñëåäóþùåå ïðåäñòàâëåíèå:
s s−1
(s+1) (s+1)
X X
i
Qs+1 = A Q1 H1i + Ai Q0 H0i , (22)
i=0 i=0
êîòîðîå óäîáíî çàïèñàòü â âèäå
(s+1) (s+1)
Qs+1 = K0 H0 + K1 H1 . (23)
Ïî ïîñòðîåíèþ (ñì. óòâåðæäåíèå 1) áëîêè Qs îáðàçóþò A-îðòîãîíàëüíûé áàçèñ âñåãî ïðî-
ñòðàíñòâà, à, ñëåäîâàòåëüíî, ðåøåíèå ñèñòåìû X Kn çàïèñûâàåòñÿ â âèäå ëèíåéíîé êîìáèíà-
öèè áëîêîâ Qi
n
K
−1
X −1 T
X Kn = Qi QTi AQi Qi B.
i=0
Ââîäÿ îáîçíà÷åíèå Zi äëÿ ìàòðèö
−1
Zi = QTi AQi QTi B,
ïðèäåì ê êðàòêîé çàïèñè äëÿ X Kn
n
K
−1
X
X Kn = Qi Zi . (24)
i=0
Íàêîíåö, ïîäñòàâëÿÿ â (24) âûðàæåíèå äëÿ Qi èç (23), íàéäåì, ÷òî
n n
K
−1 K
−1
X X (i) (i)
X Kn = Qi Zi = K0 H0 + K1 H1 Zi
i=0 i=0
n n
K
−1 K
−1
(i) (i)
X X
= K0 H0 Zi + K1 H 1 Zi .
i=0 i=0
×òîáû åùå íåìíîãî óïðîñòèòü çàïèñü è ïîëó÷èòü ìàòðè÷íîå ñîîòíîøåíèå äëÿ X Kn , îïðåäå-
(s) (s)
ëèì ñèñòåìó áëîêîâ G0 è G1 ðàçìåðà n × K ñëåäóþùåãî âèäà
s
(s) (i) (s−1) (s)
X
G0 = H 0 Zi = G0 + H 0 Zs ; (25)
i=0
s
(s) (i) (s−1) (s)
X
G1 = H 1 Zi = G1 + H 1 Zs , (26)
i=0
ãäå s ìåíÿåòñÿ â ïðåäåëàõ îò 1 äî K
n
− 1. Èñïîëüçóÿ (25) è (26), îêîí÷àòåëüíî çàïèøåì X Kn
êàê
( n −1) ( n −1)
X Kn = K0 G0K + K1 G1K . (27)
514
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Ïðåèìóùåñòâà ïîëó÷åííîé çàïèñè äëÿ X n ñîñòîèò â òîì, ÷òî â íåé íåò ÿâíîé çàâèñèìîñòè
K
îò áëîêîâ Qi , à èìååòñÿ çàâèñèìîñòü ëèøü îò ñèñòåì K0 è K1 áëî÷íî êðûëîâñêîãî òèïà.
Âû÷èñëåíèå K0 è K1 ëåãêî ïðîèçâîäèòü íà ïàðàëëåëüíûõ âû÷èñëèòåëüíûõ ñèñòåìàõ. Äëÿ
ýòîãî êàæäûé èç 2K âåêòîðîâ, âõîäÿùèõ â áëîê Q0 èëè Q1 ìîæíî óìíîæàòü íà ìàòðèöó
A íåçàâèñèìî, òåì ñàìûì äîñòèãàÿ ìàêñèìàëüíî âîçìîæíîãî ý åêòà. ×òîáû çàâåðøèòü
(n) (n)
îïèñàíèå ìåòîäà, íåîáõîäèìî ïðåäúÿâèòü ñïîñîáû âû÷èñëåíèÿ áëîêîâ G0 K è G1K , êîòîðûå
íå èñïîëüçîâàëè áû ÿâíûé âèä áëîêîâ Qi .
2.4. Âû÷èñëåíèå QT
i B
Èñïîëüçóÿ ðåêóððåíòíûå ñîîòíîøåíèÿ (12)
Q(i) (x) = Q(i−1) (x) (Ix + ν0 ) + Q(i−2) (x)ν1 ,
çàïèøåì äëÿ áëîêîâ Qi , Qi−1 è Qi−2
Qi = AQi−1 + Qi−1 ν0 + Q̃i−2 ν1 .
Òîãäà
QTi B = QTi−1 AB + ν0T QTi−1 B + ν1T QTi−2 B. (28)
 ñèëó ñâîéñòâà A-îðòîãîíàëüíîñòè äëÿ i > 2 ïåðâîå ñëàãàåìîå â (28) âñåãäà ðàâíî íóëþ.
Îêîí÷àòåëüíî
1
X
QTi B = νjT QTi−j−1 B = ν0 QTi−1 B + ν1 QTi−2 B.
(29)
j=0
2.5. Âû÷èñëåíèå QT
i AQi
×òîáû âû÷èñëèòü QT
i AQi âîñïîëüçóåìñÿ óòâåðæäåíèåì 1:
(i) T (i)
QTi AQi = Qi ρi+1
2.6. Àëãîðèòì Ëàíöîøà-Ïàäå
Âûïèøåì àëãîðèòì Ëàíöîøà-Ïàäå.
Øàã 0 (èíèöèàëèçàöèÿ àëãîðèòìà):
(a) âû÷èñëèòü α0 = B T B , α1 = B T AB , α2 = B T A2 B ;
(b) îïðåäåëèòü n × K áëîê Q0 è Q1 ïî îðìóëàì
Q0 = B; (30)
Q1 = AB − Bα1−1 α2 ; (31)
(0) (1) (0) (1)
( ) îïðåäåëèòü n × K áëîêè H0 , H0 H1 è H1 ;
(d) âû÷èñëèòü êâàäðàòíûå K × K ìàòðèöû ψ0 è ψ1 ïî îðìóëàì
ψ0 = QT0 B = B T B, ψ1 = QT1 B;
(e) âû÷èñëèòü êâàäðàòíûå ìàòðèöû Z0 è Z1 êàê
Z0 = α0−1 ψ0 = (QT0 AQ0 )−1 ψ0 , Z1 = (QT1 AQ1 )−1 ψ1 ;
515
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
(1) (1)
(f) âû÷èñëèòü áëîêè G0 è G1 ïî îðìóëàì:
(1) (0)
G0 = H 0 Z0 ; (32)
(1) (1)
G1 = H 1 Z1 ; (33)
Øàã 1 (âû÷èñëåíèå áëî÷íî-ñòåïåííîãî áàçèñà ïðîñòðàíñòâà Êðûëîâà è ïî-
ñòðîåíèå ðÿäà Ïàäå ëèíåéíîé ñèñòåìû):
2n
(a) âû÷èñëèòü ðàñøèðåííóþ ìàòðèöó K0 âèäà K0 = Q0 AQ0 · · · A K Q0 ;
(b) âû÷èñëèòü êâàäðàòíûå K × K ìàòðèöû αi ïî îðìóëàì αi = QT i
0 A Q0 , äëÿ âñåõ
n
i îò 2 äî 2 K ;
( ) ïðèñâîèòü çíà÷åíèÿ ýëåìåíòàì áëîêîâ R(0) è R(1) ;
n
Øàã 2 (ïîñòðîåíèå A-îðòîãîíàëüíîãî áàçèñà): äëÿ âñåõ s îò 2 äî K −1 ïîâòîðÿòü
(a), (b), ( ), (d) è (e)
(a) íàéòè K × K ìàòðèöû ν0 , ν1 , ðåøàÿ ñèñòåìó óðàâíåíèé,
(s−1) (s)
0 ρs ν0 ρs+1
= − . (34)
(s) (s−1) (s)
ρs+1 ρs+1 ν1 ρs+2
(s) (s)
(b) âû÷èñëèòü H0 è H1 ïî ðåêóððåíòíîé îðìóëå
(s) (s−1) (s−1) (s−2)
Hi = ZHi + Hi ν 0 + Hi ν1 , (i = 0, 1); (35)
( ) âû÷èñëèòü îñòàòîê ðÿäà Ïàäå R(s) äëÿ ïðèáëèæåíèÿ Ïàäå ñòåïåíè s ïî îðìóëå
R(s) = Z T R(s) + R(s) ν0 + R(s−1) ν1 ; (36)
(d) âû÷èñëèòü êâàäðàòíóþ K×K ìàòðèöó Zs , îïðåäåëÿåìóþ êàê Zs = (QT −1 T
s AQs ) Qs B ,
èñïîëüçóÿ ñëåäóþùèé àëãîðèòì:
(a) âû÷èñëèòü êâàäðàòíóþ K × K ìàòðèöó ψs = QT
s B , èñïîëüçóÿ ðåêóððåíòíîå
ñîîòíîøåíèå,
ψs = ν0T ψs−1 + ν1T ψs−2 (37)
(s)
(b) ïîëîæèòü ìàòðèöó QT
s AQs ðàâíîé ρs+1
(s) (s)
(e) âû÷èñëèòü G0 è G1 ïî ðåêóððåíòíûì îðìóëàì:
(s) (s−1) (s) (s) (s−1) (s)
G0 = G0 + H 0 Zs , G1 = G1 + H 1 Zs . (38)
Øàã 3 (ïîñòðîåíèå ðåøåíèÿ): Âû÷èñëèòü ðåøåíèå X n ïî îðìóëå:
K
n n
(K −1) (K −1) ( n −1)
X Kn = K0 G0 + AK0 G1 − K0 Ĝ1K , (39)
ãäå K × K êîìïîíåíòû áëîêà Ĝ1 åñòü íè ÷òî èíîå êàê K × K êîìïîíåíòû áëîêà G1 ,
−1
óìíîæåííûå ñëåâà íà ìàòðèöó α1 α2 .
516
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
2.7. Àëãîðèòì ïîñòðîåíèÿ áëî÷íî-ñòåïåííîãî áàçèñà ïðîñòðàíñòâà Êðûëî-
âà è ðÿäà Ïàäå ëèíåéíîé ñèñòåìû
Ïîñêîëüêó Øàã 0 (èíèöèàëèçàöèÿ àëãîðèòìà) èìååò ìàëóþ àëãîðèòìè÷åñêóþ ñëîæ-
íîñòü, òî ïðè ïîñòðîåíèè ïàðàëëåëüíîãî àëãîðèòìà ìû ñðàçó ïåðåõîäèì ê àíàëèçó Øàãà
1 (âû÷èñëåíèå áëî÷íî-ñòåïåííîãî áàçèñà ïðîñòðàíñòâ Êðûëîâà è ðÿäà Ïàäå ëè-
íåéíîé ñèñòåìû). Áóäåì âåçäå äàëåå ñ÷èòàòü, ÷òî ÷èñëî äîñòóïíûõ â àëãîðèòìå ñóïåð-
óçëîâ ðàâíî K . Íà Øàãå 1 âñå K ñóïåð-óçëîâ áóäóò ðàáîòàòü íåçàâèñèìî è âûïîëíÿòü
îäèíàêîâóþ ðàáîòó.
Ñ ñóïåð-óçëîì íîìåðîì i íà Øàãå 1 ñâÿæåì ñëåäóþùèå âû÷èñëåíèÿ: ðàññìîòðèì áëîê
Q0 ∈ Fn×K ; ïóñòü Q0i ∈ Fn i-ûé âåêòîð â áëîêå Q0 . Íà Øàãå 1 ñóïåð-óçåë ñ íîìåðîì i
(a) ñòðîèò ïîñëåäîâàòåëüíîñòü âåêòîðîâ Aj Q0i ñ ïàðàìåòðîì j , èçìåíÿþùèìñÿ îò 0 äî 2 K n
,
è (á) âû÷èñëÿåò i-ûå ñòîëáöû αj = Q0 A Q0i êâàäðàòíûõ ìàòðèö αj = Q0 A Q0 .
i T j T j
Î÷åâèäíî, äëÿ òîãî, ÷òîáû èìåòü âîçìîæíîñòü âûïîëíèòü óêàçàííûå âû÷èñëåíèÿ â
îòñóòñòâèå îáìåíà äàííûìè ñ äðóãèìè ñóïåð-óçëàìè, ïåðåä íà÷àëîì âû÷èñëåíèé íà ñóïåð-
óçëå ñ íîìåðîì i íåîáõîäèìî ðàçìåñòèòü ìàòðèöó A, à òàêæå áëîê Q0 = B .
Îïèøåì ðàñïðåäåëåííèå äàííûõ ïî âû÷èñëèòåëüíûì óçëàì, îòíîñÿùèìñÿ ê i-îìó ñóïåð-
óçëó. Äëÿ ïðîñòîòû áóäåì ïðåäïîëàãàòü, ÷òî êàæäûé ñóïåð-óçåë ñîñòîèò èç îäèíàêîâîãî
÷èñëà s âû÷èñëèòåëüíûõ óçëîâ. Èçáåãàÿ íåñóùåñòâåííûõ äåòàëåé, áóäåì ñ÷èòàòü, ÷òî ìàò-
ðèöà A ïðåäñòàâëÿåòñÿ â âèäå îáúåäèíåííèÿ s áëîêîâ-ñòîëáöîâ A1 , A2 , · · · , As ñ ðàâíûì
÷èñëîì ñòîëáöîâ ns è ðàâíûì ÷èñëîì íåíóëåâûõ ýëåìåíòîâ â êàæäîì áëîêå, à áëîê Q0 èìååò
ñîîòâåòñòâóþùåå áëî÷íîå ñòðî÷íîå ðàçáèåíèå
Q 1
0
2
Q0
Q0 =
,
, (40)
···
Qs0
ãäå äëÿ ëþáîãî j áëîêè Qj0 è èìåþò ðàçìåðû ns × K , è ÷òî ïåðåä íà÷àëîì âû÷èñëåíèé â
îïåðàòèâíîé ïàìÿòè óçëà ñ íîìåðîì j , çàïèñàíû áëîê-ñòîëáåö Aj ìàòðèöû A è ÷àñòü Qj0
áëîêà Q0 .
Ïðåäëîæåííàÿ ñõåìà õðàíåíèÿ åñòåñòâåííûì îáðàçîì îïðåäåëÿåò àëãîðèòìû ïîñòðî-
åíèÿ ñòåïåííîãî áàçèñà ïðîñòðàíñòâà Êðûëîâà è àëãîðèòìà âû÷èñëåíèÿ êîý èöèåíòîâ
ðÿäà Ïàäå.
2.8. Àëãîðèòì ïîñòðîåíèÿ A îðòîãîíàëüíîãî áàçèñà ïðîñòðàíñòâà Êðûëîâà
Íà÷íåì ñ ýëåìåíòàðíîãî àíàëèçà ñëîæíîñòè âû÷èñëåíèé íà Øàãå 2 (ïîñòðîåíèå A-
îðòîãîíàëüíîãî áàçèñà). åøåíèå îäíîé ñèñòåìû ëèíåéíûõ óðàâíåíèé âèäà (34) èìååò
ñëîæíîñòü O(K 3 ), ñëåäîâàòåëüíî, ó÷èòûâàÿ, ÷òî ðåøàòü ñèñòåìó íåîáõîäèìî 2n/K ðàç,
ïîëíàÿ ðåøåíèÿ 2K × 2K ëèíåéíûõ ñèñòåì O(nK 2 ).
(t)
àññìîòðèì âû÷èñëåíèÿ êîý èöèåòîâ Hi ïîëèíîìèàëüíîãî ïðåäñòàâëåíèÿ, çàäàâàå-
ìîãî îðìóëîé (35). Ñëîæíîñòü ýòîãî âû÷èñëåíèÿ îöåíèâàåòñÿ êàê O n K . Àíàëîãè÷íàÿ
2
îöåíêà ñïðàâåäëèâà è äëÿ ðåêóððåíòíûõ ñîîòíîøåíèé (36) è (38). Íàêîíåö, ýëåìåíòàð-
íàÿ ïðîâåðêà ïîêàçûâàåò, ÷òî âñå îñòàëüíûå âû÷èñëåíèÿ íà Øàãå 2 (ïîñòðîåíèå A-
îðòîãîíàëüíîãî áàçèñà) èìåþò ñëîæíîñòü íå âûøå O(nK 2 ).
Ó÷èòûâàÿ, ÷òî n ≫ K è, ñëåäîâàòåëüíî, n2 K ≫ nK 2 , îñíîâíîå âíèìàíèå áóäåì óäåëÿòü
ïàðàëëåëüíîé ðåàëèçàöèè ðåêóððåíòíûõ ñîîòíîøåíèé (35), (36), (38). Êëþ÷åâîå íàáëþäå-
íèå, êîòîðîå ïîçâîëÿåò ðåàëèçîâàòü ý åêòèâíóþ ïàðàëëåëüíóþ ïðîöåäóðó ïåðåñ÷åòà ðå-
517
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
êóððåíòíûõ ñîîòíîøåíèé, çàêëþ÷àåòñÿ â âîçìîæíîñòè õðàíèòü ñòðîêè, áëîêîâ H , R è G, â
âèäå, äîïóñêàþùåì ñáàëàëàíñèðîâàííûå âû÷èñëåíèÿ íà âñåõ s óçëàõ ëþáîãî ñóïåð-óçëà.
Èòàê, áóäåì ñ÷èòàòü, ÷òî íà óçëå ñ íîìåðîì 1 ñóïåð-óçëà ñ íîìåðîì i ðàñïîëàãàþòñÿ
(0) (0) (0) (0)
âåêòîðû-ñòðîêè Ri = α0i , Rsi = αsi , R(2s)i = α(2s)i , · · · , R(2n/K)i = α(2n/K)i (íàïîìíèì,
÷òî s ýòî ïàðàìåòð, îïðåäåëÿþùèé ÷èñëî óçëîâ, îòíîñÿùèõñÿ ê äàííîìó ñóïåð-óçëó).
Àíàëîãè÷íî, íà óçëå ñ íîìåðîì 2 òîãî æå ñóïåð-óçëà ñ íîìåðîì i áóäóò ñîõðàíÿòüñÿ âåêòîðû
(0) (0) (0)
R1i = α1i , R(s+1)i = α(s+1)i , R(2s+1)i = α(2s+1)i è ò.ä. Òàêèì îáðàçîì, íà êàæäîì èç s óçëîâ
êàæäîãî ñóïåð-óçëà áóäåò õðàíèòüñÿ ïðèìåðíî ïîðîâíó, à èìåííî ïî Ks
2n
âåêòîðîâ äëèíû
K , ïðåäñòàâëÿþùèõ áëîê R . Àíàëîãè÷íûì îáðàçîì ðåàëèçóåòñÿ ñõåìà õðàíåíèÿ áëîêîâ
(0)
(s) (s) (s) (s)
R(s) , H0 , H1 , à òàêæå G0 è G1 .
àññìîòðèì ïðåèìóùåñòâà, êîòîðûå äàåò îïèñàííàÿ íàìè ñõåìà õðàíåíèÿ. Âûïèøåì
àëãîðèòì, ñîîòâåòñòâóþùèé âû÷èñëåíèþ s + 1 îñòàòêà ðÿäà Ïàäå ïî îðìóëå
R(s+1) = Z T R(s) + R(s) ν0 + R(s−1) ν1 , (41)
ñ÷èòàÿ ÷òî ìàòðèöû ν0 è ν1 ÿâëÿþòñÿ èçâåñòíûìè.
(s)
Îáîçíà÷èì ÷åðåç R̃il áëîê ðàçìåðà Ks
2n
, ïðåäñòàâëÿþùèé íàáîð âåêòîðîâ R(s) íà l-îì
óçëå i-îãî ñóïåðóçëà. Íå ñëîæíî ïðîâåðèòü, ÷òî (41) ïåðåõîäèò â ñëåäóþùåå ñîîòíîøåíèå:
(s+1) (s) (s) (s−1)
R̃il = Z̃ T R̃i(l+1) + R̃il ν0 + R̃il ν1 , (42)
ãäå Z̃ æîðäàíîâà êëåòêà ðàçìåðà Ks
2n
ñ íóëåâûì çíà÷åíèåì íà äèàãîíàëè. Ïåðâîå ñëàãàåìîå
â ïðàâîé ÷àñòè (42) èìååò íèæíèé èíäåêñ l+1, à çíà÷èò ýòà ÷àñòü áëîêà R(s) ðàñïîëàãàåòñÿ â
ïàìÿòè óçëà ñ íîìåðîì l+1. Â òîæå âðåìÿ îñòàëüíûå ñëàãàåìûå è ïðåäïîëàãàåìûé ðåçóëüòàò
íàõîäÿòñÿ íà óçëå ñ íîìåðîì l. Òàêèì îáðàçîì, âû÷èñëåíèÿ ïî îðìóëå (42) ïîäðàçóìåâàþò
îáìåí äàííûìè ìåæäó óçëàìè ñóïåð-óçëà ñ íîìåðîì i. Çàïèøåì àëãîðèòì.
Àëãîðèòì äëÿ (41):
1. íà êàæäîì èç s óçëîâ âû÷èñëèòü ïðîèçâåäåíèå âñåõ Ks
2n
ñòðîê îò áëîêà R(s) íà ìàòðèöó
ν0 ;
2. íà êàæäîì èç s óçëîâ âû÷èñëèòü ïðîèçâåäåíèå âñåõ Ks
2n
ñòðîê îò áëîêà R(s−1) íà
ìàòðèöó ν1 ;
3. ñëîæèòü ñîîòâåòñòâóþùèå ñòðîêè;
4. ïåðåñëàòü ñòðîêè ñ óçëà ñ íîìåðîì i íà óçåë ñ íîìåðîì (i mods) + 1) è ñëîæèòü ñ
ïðåäûäóùèì ðåçóëüòàòîì.
Äëÿ òîãî, ÷òîáû çàêîí÷èòü îïèñàíèå ïàðàëëåëüíîé ðåàëèçàöèè Øàãà 2 (ïîñòðîå-
íèå A-îðòîãîíàëüíîãî áàçèñà), íàì íåîáõîäèìî îïèñàòü ïðîöåññ ãëîáàëüíûõ ïåðåñûëîê
ìåæäó ðàçëè÷íûìè ñóïåð-óçëàìè è ñâÿçàííûå ñ íèìè âû÷èñëåíèÿìè. Äåéñòâèòåëüíî, åùå
íè÷åãî íå áûëî ñêàçàíî î òîì, êàê ïîëó÷àòü ìàòðèöû ν0 è ν1 . Ïîñêîëüêó äàííûå ìàòðè-
öû ÿâëÿþòñÿ ðåçóëüòàòîì ðåøåíèÿ ñèñòåì (34), òî íåîáõîäèìî ó÷åñòü âðåìÿ, íåîáõîäèìîå
íà ñáîðêó è ðåøåíèå òàêèõ ñèñòåì. Íà÷íåì ñî ñáîðêè. Ó÷èòûâàÿ âûáðàííóþ íàìè ñõåìó
õðàíåíèÿ äàííûõ, ñáîðêà (34) ÿâëÿåòñÿ ðåçóëüòàòîì ýëåìåíòàðíîãî îáìåíà äàííûìè ìåæäó
ñóïåð-óçëàìè.
2.9. Îðãàíèçàöèÿ ïàðàëëåëüíûõ âû÷èñëåíèé íà Øàãå 3 (ïîñòðîåíèå ðåøå-
íèÿ)
Ïîäõîä ê ïîñòðîåíèþ äàííîãî àëãîðèòìà îïèñàí â ðàçäåëå 4.3 êíèãè [12℄. Èäåÿ ïîäõîäà
âåñüìà ïðîñòà. àññìîòðèì ñíà÷àëà íåñêîëüêî óïðîùåííóþ ñèòóàöèþ. Ñ÷èòàÿ çàäàííûìè
518
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
áëîê B ∈ Fn×K , ìàòðèöó A ∈ Fn×n è âåêòîð G, áóäåì èñêàòü âåêòîð X â âèäå
n
K
−1
X
X = K0 G = Ai BGi , (43)
i=0
ãäå Gi ïîäâåêòîðû âåêòîðà G ðàçìåðà K .
Ïóñòü èìåþòñÿ K óçëîâ, è íà êàæäîì èç K óçëîâ íàõîäèòñÿ ïîñëåäîâàòåëüíîñòü Êðû-
ëîâà âèäà Bi , ABi , A2 Bi , · · · , An/K−1 Bi è âåñü âåêòîð G. Íàøà áëèæàéøàÿ öåëü ïðåäëîæèòü
àëãîðèòì ïîëó÷åíèÿ X , ìèíèìèçèðóþùèé ÷èñëî îáìåíîâ.
Çàïèøåì (43) áîëåå ïîäðîáíî, ðàññêðûâàÿ íåÿâíîå ñóììèðîâàíèå â ñîîòíîøåíèè ABGi ,
n
K
−1
X
X= Ai BGi (44)
i=0
n
K
−1 K
X X
Ai B j Gij (45)
=
i=0 j=1
n
K K
−1
X X
Ai B Gij (46)
=
j
j=1 i=0
n
K K
−1
X X
= Ai Bj Gij . (47)
j=1 i=0
Íå òðóäíî çàìåòèòü, ÷òî â (47) âûðàæåíèå â ñêîáêàõ ìîæåò âû÷èñëÿòüñÿ íà âñåõ óçëàõ
íåçàâèñèìî. Òàêèì îáðàçîì, åñëè áû òðåáîâàëîñü ïîëó÷èòü X íà óçëå ñ íîìåðîì 1, òî
êîëè÷åñòâî íåîáõîäèìûõ îáìåíîâ äëÿ ïîëó÷åíèÿ X íå ïðåâîñõîäèëî áû O (n).
Ïðèìåíèì äàííûé ïîäõîä ê ïîñòðîåíèþ îïòèìàëüíîãî ïî ñëîæíîñòè àëãîðèòìà ïîëó-
÷åíèÿ ðåøåíèÿ ëèíåéíîé ñèñòåìû â âèäå ëèíåéíîé êîìáèíàöèè áëîêîâ áëî÷íî-ñòåïåííîãî
áàçèñà ïðîñòðàíñòâà Êðûëîâà. Íà÷íåì ñ îáñóæäåíèÿ òîãî, ÷åì ðåàëüíûé àëãîðèòì îòëè÷à-
åòñÿ îò òîëüêî ÷òî ðàññìîòðåííîé óïðîùåííîé ñèòóàöèè. Âî-ïåðâûõ, â ðåàëüíîé ñèòóàöèè
èìååòñÿ K ñóïåð-óçëîâ, êàæäûé èç êîòîðûõ ñîñòîèò èç s óçëîâ. Âî-âòîðûõ, âåêòîðû âèäà
Aj Bi õðàíÿòñÿ íà îòäåëüíûõ óçëàõ ñóïåð-óçëîâ â âèäå ïîäâåêòîðîâ ðàçìåðà ns , ÷òî îïðåäå-
ëÿåòñÿ âûáðàííîé íàìè ñõåìîé õðàíåíèÿ (ñì. ïóíêò 2.7). Êàê áóäåò âèäíî èç äàëüíåéøåãî,
ýòè îòëè÷èÿ íå ïîâëèÿþò ñóùåñòâåííî íà ïîñòðîåíèå ïàðàëëåëüíîé ïðîöåäóðû.
Îòìåòèì åùå, ÷òî â ðàññìàòðèâàåìîì íàìè àëãîðèòìå G ýòî íå âåêòîð, à n × K áëîê
âåêòîðîâ. Ñõåìà õðàíåíèÿ áëîêà G áûëà îïèñàíà íàìè ðàíåå. Íå òðóäíî ïðîâåðèòü, ÷òî
ïîñëå âñåõ âû÷èñëåíèé íà Øàãå 2 (ïîñòðîåíèå A-îðòîãîíàëüíîãî áàçèñà) ñòðîêè áëî-
n n
−1 −1
êîâ G0K , G1K è ñîîòâåòñòâóþùèå ñòîëáöàì Aj Bi êðûëîâñêèõ ñèñòåì, ðàñïîëàãàþòñÿ â
ïàìÿòè óçëîâ îäíîãî è òîãî æå ñóïåð-óçëà ñ íîìåðîì i (ñì. ïóíêò 2.8). Ýòîò àêò ïîçâî-
ëÿåò íàì ðàññìîòðåòü àëãîðèòì âû÷èñëåíèÿ ðåøåíèÿ X , êîòîðûé â ìèíèìàëüíîé ñòåïåíè
èñïîëüçóåò îáìåí ìåæäó îòäåëüíûìè ñóïåð-óçëàìè, à, ñëåäîâàòåëüíî, íå çàâèñèò îò òèïà
ïàðàëëåëüíîé àðõèòåêòóðû.
Àëãîðèòì âû÷èñëåíèÿ X :
( n −1)
1. ñîáðàòü íà êàæäîì óçëå êàæäîãî ñóïåð-óçëà K
n
× K ïîäáëîêè G̃0 è G̃1 áëîêîâ G0K
( n −1)
è G1 K (íàïîìíèì, ÷òî äî íà÷àëà ðàáîòû àëãîðèòìà íà óçëàõ ðàñïîëàãàþòñÿ ëèøü
n
Ks × K ïîäáëîêè áëîêîâ G̃0 è G̃1 );
2. ïðîâåñòè íåçàâèñèìî íà êàæäîì óçëå âû÷èñëåíèÿ âèäà
n
K
−1
X
X̃ti = Aj Bit G̃j , (48)
j=0
519
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
çäåñü t îáîçíà÷àåò íîìåð óçëà â ñóïåð-óçëå ñ íîìåðîì i, à X̃ti áëîê ðàçìåðà ns × K ,
ðàñïîëîæåííûé â ïàìÿòè t-îãî óçëà ñóïåð-óçëà ñ íîìåðîì i;
3. ïåðåñëàòü áëîêè X̃ti íà t-ûé óçåë ñóïåð-óçëà ñ íîìåðîì 1 (âûäåëåííîãî ñóïåð-óçëà);
4. íà óçëå ñ íîìåðîì t ñóïåð-óçëà 1 âû÷èñëèòü
K
X
X̃t = X̃ti . (49)
i=1
5. ñîáðàòü ðåøåíèå íà óçëå 1 ñóïåð-óçëà 1.
Ëèòåðàòóðà
1. Lan zos C. An iteration method for the solution of the eigenvalue problem of linear
dierential and integral operators // J. Res. Nat. Bur. Standards. 1950. Vol. 45, P. 255282.
2. Coppersmith D. Solving linear equations over GF (2): Blo k Lan zos algorithm. // Linear
Algebra Appl. 1993. Vol. 193. P. 3360.
3. Gutkne ht M.H. A ompleted theory of the unsymmetri Lan zos pro ess and related
algorithms. Part I. // SIAM J. Matrix Anal. Appl. 1992. Vol. 13. N. 2. P. 594639.
4. Gutkne ht M.H. A ompleted theory of the unsymmetri Lan zos pro ess and related
algorithms. Part II. // SIAM J. Matrix Anal. Appl. 1992. Vol. 15. P. 1558.
5. Montgomery P. A blo k Lan zos algorithm for nding dependen ies over GF(2) //
Springer-Verlag, 1995. Vol. 921.
6. Peterson M., Moni o C. F2 Lan zos revisited. // Linear Algebra Appl. 2008. Vol. 428.
P. 11351150.
7. Äîðî ååâ À.ß. Âû÷èñëåíèå ëîãàðè ìîâ â êîíå÷íîì ïðîñòîì ïîëå ìåòîäîì ëèíåéíîãî
ðåøåòà. // Òðóäû ïî äèñêðåòíîé ìàòåìàòèêå. 2002. Ò. 5. P. 2950.
8. Äîðî ååâ À.ß. åøåíèå ñèñòåì ëèíåéíûõ óðàâíåíèé ïðè âû÷èñëåíèè ëîãàðè ìîâ â
êîíå÷íîì ïðîñòîì ïîëå. // Ìàòåìàòè÷åñêèå âîïðîñû êðèïòîãðà èè. 2012. Vol. 3. N. 1.
P. 551.
9. ×åðåïíåâ Ì.À. Áëî÷íûé àëãîðèòì òèïà Ëàíöîøà ðåøåíèé ðàçðåæåííûõ ñèñòåì
ëèíåéíûõ óðàâíåíèé. // Äèñêðåòíàÿ ìàòåìàòèêà. 2008. Vol. 20. N. 1.
10. Ì.À. ×åðåïíåâ. Version of blo k Lan zos-type algorithm for solving sparse linear systems.
Bull.Math.So .S i.Math.Roumanie, V.53(101), N.3, 2010, p.225-230,
http://rms.unibu .ro/bulletin.
11. È.À. Ïîïîâÿí Þ.Â. Íåñòåðåíêî, Å.À. ðå÷íèêîâ. Âû÷èñëèòåëüíî ñëîæíûå çàäà÷è
òåîðèè ÷èñåë. Ó÷åáíîå ïîñîáèå. Èçäàòåëüñòâî Ìîñêîâñêîãî Óíèâåðñèòåòà, 2012.
12. Í.Ë. Çàìàðàøêèí. Àëãîðèòìû äëÿ ðàçðåæåííûõ ñèñòåì ëèíåéíûõ óðàâíåíèé â GF(2).
Ó÷åáíîå ïîñîáèå. Èçäàòåëüñòâî Ìîñêîâñêîãî Óíèâåðñèòåòà, 2013.
520
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Universal block Lanczos-Pade method for linear systems over
large finite fields
Nikolay Zamarashkin and Mihail Cherepnev
In this paper we propose a universal algorithm designed for solving large sparse linear
systems over finite fields with large prime number of elements. Such systems arise in the
solution of the discrete logarithm problem modulo a prime number. Parallel algorithms and
effective data distributions are proposed.