Авторефераты по всем тема >>
Авторефераты по разно
о /p>о н
01.01.07 | лна мамаа оа да наоан ной н дооазо-мама на оа| 2011 аоаолнна ждн ойой адм на лном н м. . . ооднна алн оонн: доо зо-мама на, оо н .
доо зо-мама на, о .
доо зо-мама на, но .
да оанза: азанй (олжй) далнй н ааоо \ " 2011 . мн
назадан аонноо оа 002.045.01 ждн ойой адм на н лной мама о ад: 119333, . оа, л. на, 8
дай можно ознаом ло на лной мама
оа азолан \ " 2011
нй а аонноо оа доо зо-мама на оао .
ой озо. мааонн модо нном н м нйн аннй азжннм маам алноо дал замн доаоно дано, о айнй м дн 20-о а. одаж л омн днннй ндоао: мдлнна одмо аонн жнй омом н, м а аз дл зада, оо наол аалн
м ннм аам аз аонн аломо н м нйн аннй ммной оложлно одлнной май ал (а) азаоаном м 1952 од мода ожнн адно, оой, о од, но зан аломом даоналза, олоаннм аном 19од;() азаоан дололан дл аонн модо (ооа алннадалном нйном оазоан ма м), омлоанной з онм модаожнн адно аоа анл 19ода,3 . . аа . A. зноа1968 ода,4 O. лона д
ононом, о дололнноо модаожнн адно азала о оно онон ан а (.наз. алноо лаололнно) дололнной ма, о оождало оо аа дололан
M. R. Hestenes and E. Stiefel. Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards, 49 (1952) 409{436
C. Lanczos. An iteration method for the solution of the eigenvalue problem of linear di erential integral operators. J. Research Nat. Bur. Standards, 45 (1950) 255{282
J. W. Daniel. The conjugate gradient method for linear and nonlinear operator equations. SIAM J. Numer. Analysis, 4 (1967) 10{26
. . а, . A. зно. омалн аонн оа. ол. ад. а , .181, 6 (1968) 1331{1334
O. Axelsson. A>
Engrg., 9 (1976) 123{137
о ознаало, о н оло о, но оон модо н м нйн аннй ой л ной м олала олма, оаздо ол ложна о анн одной, мнно, оонна задаанаонн знан. ом олдн зада н мой, оаной оано, о а аам дололай ма з ло мнммаонон айн онн знанй
нно, о о м ложнн алн ладн зада, аа а ла ноо мжд ално мнмм ломам, доазам о а но (однао заа н мм доаоно ооо ооноан), м онм, оо о доал олн нал н ан лаай дл ноо модлн олм (.. мл оо ооноан), однао, д алзоан д лома, оазал одн л дл доолно оаннноо аалн зада
ом оо, ажм налооазно адоолнлн ой адололнн ма, ааз наномно адлн онн знанй н ан а. а ойаа, одно, н зан ноднно о алнм лом ололнно (дл модаожнн адно, ажнм л н оло мало оо лаололнно, но азжнно аонн знанй лоо она о лонн аоо )
мм о азао нандан ододо дололан модаожнн адно, м., на., [1, 2], ааж нданй озо,7 оо оал най аа дололан, аннй д доааон k In Mk F Rn о дололнной ма M до днной In. днао, аом одод зн оанн, дла о нанм O. Axelsson and G. Lindskog. On the rate of convergence of the preconditioned conjugate gradient method, Numer. Math. 48, (1986) 499{523
T. Huckle. Factorized Sparse Approximate Inverses for Preconditioning. The Journal of Supercomputing v.25, no.2 (2003) 109{117
о мно ажн а, м. на., ождн ао [26]. олднй ао одж заоннна о одмо мода оонн мнмалн нзо мна н k In Mk F доолнлноо аама, аазо одлн аM о нл. днао, он азжнн ма олоо азма, н дал алной оаноазада о мнмза k In Mk ло, нам, оаннно k M 1 k
F ам оазом, аа о но онн мода оон н дололанй заономно од ноодмо азао нан ододо он аадололанй модаожнн адно
аом ж лооазн о азаоамодо дололан, оноанн нанн доаоно о ла азжнн ма нзамо о аной (оно, нам, знанй ннл мно азжнно), оо зан о ойам мама модлй з оо, о зам маам. ам оазом, а ажнйа аа задаа о азао н оло н, но доаоно налн аломо н ол азжнн м нйн аннй, жа ооно аоа жм "ноо а"
ао. а лй ао можно аза н д олм:p>
1. длн ододо наноо лаололнно, ооноо а н оло онон айн онн знанй, оло налн ойаа, н занноо, ам оазом, одлно зм оннм знанм дололнной ма
2. оон нлам оно лаай мода ожнн адно мна оо лаололнно
3. н зн оон но дололанй, оо л омалнм (л з аом) о зн нооо лаололнно
4. оа оано оонн дололанй о зн лаой о (оноанной намнн онон ан адололнной ма)
5. ломза но дололанй ( ом л, одн дл алза наооаалллн ома) аа оа лной но на далн о задаа
ално м. н нйн м азжннм ( ом л ммнм оложлно одлннм) маам олой азмно ао озна а ооа ( ом домна о домо) одзадаа лома, алз ам азнооазн ладн а. мом мо ж зада мамаой з, зада оон о, зада омза мно д
оолно анданой л а, ода нйн зада, оо н ноно наалнй дл аонноо н нлнйной зада. ом ойаозна ма о н даолн дазм, оан наджно ломо н нйн м ом ла озаа
дой оон, о аз лной н дл оо оан ломам н; а, од омзай лома, оммо ноо оан ла оай омаам, мож одазма н л оон нй, олай н ао омо аой мой ам /л аалллной оанзай нй
ам оазом, ло замоололнноо оа лн моной ложнн оаноо ладн зада, оа олмаоон "нало" модан ол азжнн м нйн аннй оа далой о ооналноо н (даж л оан задаам ммной оложлно одлнной май)
д зна, о нмо нал мноолнн доалй наожн до л, о оно аоо ажноо наалн, а оон н дололанй дл нн лао ма, оа ндоаонм дл аоо н даажн зада. о ололо ално м да
ана нозна. да азаоан ной й но одололанй дл модаожнн адно. й л оннм, о озолло ол а но аан зн ломо, а азаоа но лом, ол н одлнн ло. ононм ном злаам можно он д:p>
1. дложн доан ной й но дололан, омлоаннй мна мнмза маноо нонала(ажао з д ма одлл), назамоо дал K-лом ололнно
о мн л дн .лоном олзоан о зной моноа,8 д оно оан ноо зла наой да
2. мна -лаололнно олнаноа она лаай модаожнн адно, нлама ом ж мл, о зна оназ ално ло ололнно. ом оо, ноа онаодмо анала нйн оо одмо, ол о зной он, ооа аза оло налнйн одмо ай модаожнн адно
3. амон наол н з зн жнн олн азложнй, на надлжно ноом ла олн азложнй 2-о ода, олн налз O. Axelsson. Iterative solution methods. Cambridge University Press, Cambridge, 1994
а о зн омза а алноо ла ололнно, а -лаололнно
4. о зн омза -лаололнно оаналзоан наол н з зн н дололанй, а л жннм оанм олнм азложнм. айдналоно-нна омадалн а дололалй, озола за о змн лн заа одноо азложн з о аалллзмо. длн оо н он жнн олн азложнй лон мода, ооноанаоа но аоо одода
5. о зн омза -лаололнно оаналзоан олномалн дололан модаожнн адно, олн о онн оо зноо аа, о она омза а дололанй о мнммаалноо лаололнно, а ало, од ндоаоно нм лнм ломам
6. о зн омза -лаололнно оаналзоан зн ооаалллн дололан, занн малоаноой ой
оон но омл а дололанй, аж олнн доолнлнй налз о зн алноо лаололнно. оазанаоммо дололан одом малоаноой мода дм дололанм, о озол нно оа но зн модо
оа аа нно. оа нно да зала азао ноой о одмо модаожнн адно, аж ноднно занноо нй оо одода омза дололанй
ом оо, олн д ажн ан о злао, оа оннм ам долола ма
аа нно олнн злао зала оон онн ломо н м азжннм оложлно одлннм маам оо да, олада онной наджно, оой озодлно на олдоалн ома, аж оой аалллзмо
ано, азаоан н аалллн мод н м нйн аннй ммнм оложлно одлннм маам, оон аоа азжннм лоо ололннм маам, оо мо олзоан о мно омлнн ложн
од доан. да мн мод нйной л , о ма, аж о нй нн мнн. олзоанаа зна о аонн модо ммзмом ла, оноанна наона алноо лаололнно ма, а азаоаннй да нало, оноаннй наолзоан -ла ололнно
оложн, ном наза:p>
1. оа о одмо модаожнн адно, оноанна наолзоан K-лаололнно, заннй нй одод оон дололанй, оноаннй намнмза K-лаололнно
2. о дололан ммн оложлно одлнн ма одом жнн олн азложнй 2-о ода, ооноанм а з -ло ололнно, а мна алноо ла ололнно
3. о дололан ммн оложлно одлнн ма одом оан жнн олн азложнй, олзоанм лоно, аж нлоной ома, ооноанм мна -ла ололнно
4. оо онн ноо оной омза алноо лаололнно оламоо аа олномалноо дололан, олнно наоно аналза-лаололнно; оан аамза оо мноолна, оао зо омалном ао дололан
5. о дололан ммн оложлно одлнн ма одом -омалной малоаноой мода, ооноанм а з -ло ололнно, а мна алноо лаололнно
оноанно дооно злао
далнн да зла м оо мамао ооноан. дой оон, дооно но оонн дололанй оджда мм аннм злао ао злаам, олннм олзоан д андан дололанй: нам, оноо модао, жнноо лоноо модао
ом оо, дл дазада з олл налод, олзоа дм оам дл о азаоанн м аломо, л олн нно л зла
оа ао. зла ао доладал ождал намжднаодной онн \PaCT99" (ан, о, 1999 .), мном 16-ом он \IMACS 2000" о нанм нм, ладной мама модлоан (озанна, йа, 2000), олландо-ойом мозм NWO (, оа, н 2000), мозм NWO (мдам-ймн, олланд, но 2000), оом жднаодном нано-аом мна ойой молоджной ол \ ооозодлн аалллн н налан ма" (жнй ооод, о, 2002), мжднаодной онн \Parallel CFD 2003" (оа, 2003), жднаодной онн \VIII н нан н" (-, нжн, о, 2005), мжднаодной онн о лной ом, на о нанм нм \NUMGRID2008" ( , оа, 2008), мжднаодной онн о лной ом, на о ооозодлнм нм \NUMGRID2010" ( , оа, 2010), мжднаодной онн о манм модам мама ложн \MMMA-2011" ( , оа, 2011), нано-лдоал мнаа лноо на наллной мама , ао мнаа ExxonMobil Upstream Research Co. (он, )
а. о м да олоано 28 ао, з н 5 онн нзоанн здан, омндоанн , 8 мжднаодн нзм здан з омндоанноо а\Web of Science: Science Citation Index Expanded" (аза о ннм наам), 2 д мжднаодн нзм здан, 1 ойом нзмом здан, 4 да ой оннй, 5 да мжднаодн оннй, 3 ла д нан здан. (о ао од он оаа)
омн аоа [15, 19, 22, 24, 25, 27, 28] ..онн надлж оа млллной алза мода оан нн мно, о да - азаоа доан дололан
аодано. о ажа лаодано . . мн, м оа ао о м да, . . ололной занман ао нн ождн, оо . лон зан ао оонн оддж наожн мно л, . . онн задллно одно ола нноо оан аалллной алза азаоанн аоом модо, . . аанж заолзн ождн, заман оддж ао, . . ално заодно ола аой алза ндн азаоо о м да, аадм . . но н-оондн . . но занман ао оддж. онн нно мл ождн маалала 4 . . лоой . . алм, аа оно лной но дложнн оом модо
а ом ао. аонна аоаоо з дн, 6 ла, залн ала. м ао 2ан. о ла ла 192 намноан
дн одж ай ой озо оано зада, ооноан ално дмой олм, омло л зада даонной ао, н олнн да но злао, аой нно, оложнй, ном наза оан да
а лааодж зложн о нооо ла ололнно n
K = K(M) = trace(M) det(M) (1) n дал назамоо -лом ололнно. азаннй манй нонал одл дл нной ммзмой ма M (.., ножднна мааT аа, о M = TST 1, д S - ммна оложлно одлнна маа). оод дално ооалн -лаололнно о анданм алнм лом ололнно C = C(M) = (M)= (M): (2) max min аомна л од но ажн ойа л ололнно, жд о занн онам одмо модаожнн адно, мнмоо дл н м нйн л а аннй (.л.а..) Mx = b ммной оложлно одлнной (..о.) азжнной n n-май M
амаа анданй мод ожнн адно (м...):p>
r0 = b Mx0; p0 = r0; i = 0; 1; : : : :p>
T ri ri = ; xi+1 = xi + pi ; ri+1 = ri Mpi ; (3) i i i pTMpi i T ri+1 ri+ = ; pi+1 = ri+1 + pi :p>
i i T ri ri д xi ri = b Mxi жн н нзанаiй а, оонно. ооо зна онаан M 1p ном нз, д k rk = rTM 1r, м д 0 p, ! ! p i i k rik 1 C(M) + 1 C(M) M @ A 2 p + p ; (4) k r0k M C(M) 1 C(M) + д C(M) одлно (2). онно, о мнн C(M) оа ол о ан нй ан M 1-ном нз
д, однао, ом ндоаон олаоанно он (4) алной оо одмо м..., ооа нно за н оло о онон ан а, но о адлн онн знанй ма M н ан
оа о одмо м..., олза дложнно аоа [3, 4] -ло ололнно (1), оноа нанй p ан доой ном нз k ri k = rTr да i=k ri k K(M)1=i 1 : (5) k r0k оналнй д ой он л анолн аоа [8, 11], д лааж доазана нламо ом ж мл, ооом о адло дл анданой он (4)
оа лааодолжа зложн о модаожнн адно (м...), дл н .л.а.. Ax = b. аж а о мнн. оо нман дл дололнном аан м..., озолм знално о о лн но. л ..о. мааH A 1 ана а дололал дл ма A, о о мод оа дм омлам:p>
r0 = b Ax0; p0 = Hr0; i = 0; 1; : : : :p>
T ri Hri = ; xi+1 = xi + pi ; ri+1 = ri Api ; (6) i i i pTApi i T ri+1 Hri+ = ; pi+1 = Hri+1 + pi :p>
i i T ri Hri ажнм ном злаом, оджам ой ла, л (онна) оналаай модаожнн адно, доаоноо дл мнн H-ном наалной нз " 1 аз з K-ло ололнно iK(") = log2 K(HA) + log2 (" 1) : (7) оо можно оон о анданой оной лаай p iC(") = C(HA) log (2" 1) : (8) нонм ндоаам аадололан, оноанноо наон (8) занноо мнмзай алноо лаололнно C(HA), л а олмано о ноднноо аоо олзоан оло-нд ом ла (нам, оон дололанй дл озолной ..о. ма), а о ндоаона олаоанно алной оо одмо м..., оонно ло дй лной оно. оом залн ла омл ононой з да, номй наза, мнно, од о лооазно оон дололал H од з ло мнмза -лаололнно K(HA) (л о нй он) оанн, наладам ой дололал H
Y. Notay. On the convergence rate of the conjugate gradients in presence of rounding errors. Numer
Math. v.65 (1993) 301-317
лааодж оан зноо ой но лаадололанй, оа жннм ммнм олнм азложнм озолн ..о. ма A UTU. ноно нман дл ломам азложнй онм мал мно о знанм. оаза дй ажнй зла, аналай н ан заолнн жнноо множл U дл ооо лаа аломо аоза
ома1 [12]. A = AT > 0 Diag(A) = In, нооом 0 < 1 олнн ло ной ойо trace(UTU A) n ; det(UTU) det A:p>
одаз ло он j (U)i;jj ; j > i;
д оназаолнн + 1 K(A) 1=n nz(U) n 1 + ;
а мо нламой мал ; ол n; K(A)
налз олдн дожнй ола оон жнн олн азложнй, жд о ломамноо,10 о ол аной жнной ,11 л дй маной омло [12], ооа озоллан оло да оо ооноан оом дололан, но омлоа он жнноо олноо азложн ооо ода:p>
T A = UTU + UTE1 + E1 U E2 (9) M. Tismenetsky. A new preconditioning technique for solving large sparse linear systems. Linear Algebra Appls. v.154-156 (1991) 331-353
M. Suarjana and K. H. Law. A robust incomplete factorization based on value and space constraints
Int. J. Numer. Methods Engrg. v.38 (1995) 1703-1719
д U { ножднна н олна маа(олзма а жн аоо множл U0 оноо олноо T азложн A = U0 U0 дл ма A), E1 { оо н олна мааоно онолно малм о модл мнам, E2 { ммна ноално одлнна мааоно мнам, нно мнм о анн E1
налнм мом аоо азложн (9) ( о E1 = O( ), E2 = O( )) л о а, о ой ж нжнй ан намодл ннл мно U (аода ооамой нй ан заолнн nz(U), м. ом 1), оно жн оаза наодо л мл замо о лаололнно ма A:p>
p 2 C(U TAU 1) = 1 + O( C(A) + C(A)); log K(U TAU 1) c2(A) ;
одаа дл м ажннна-ала,12 м. аж (д E1 = 0; E2 = O( )) мм оаздо ол ла он C(U TAU 1) = 1 + O( C(A)); log K(U TAU 1) c1(A) :p>
нн оонон дл н жнноо олноо азложн мо олн ноднно з (9), нам, л о оа, о азжнно ма U E1 н ло оада озй ннл мно о знан ннл мно долол оононм j (U)ijj j (E1)ij j < оонно. д 0 < 1 дал оой малй аам, одлй ао азложн (дм аж наза аамом он мал мно жнном олном азложн)
н алноо лаололнно, олам олзоан дололан, ооо жнном олном азложн 2-о ода, анала A. Jennings and G. M. Malik. Partial elimination. J. Inst. Math. Appl., 20, 307-316, 1977
M. A. Ajiz and A. Jennings. A robust incomplete Choleski-conjugate gradient algorithm. Int. J. Numer
Methods Engrg., 20, 949-966, 1984
ома2 [12]. ожд (9) ма доло дм лом: U - н олна оложлной даонал, E1 - оо н олна, T T A = AT > 0; E2 = E2 0; E1 E1 E2;
T k E1A 1E1 k ; k A 1=2E2A 1=2k ;
одаадл он p p (U 1AU T) + 1 + + ; (U 1AU T) 1 + :p>
min max p p C(U 1AU T) (1 + ) + 1 + + :p>
зла, олнн ом ла он -ла ололнно, да ома3 [12]. ожд T A = UTU + UTE1 + E1 U E2;
ма доло дм лом: U - н олна оложлной даонал, E1 - оо н олна, T A = AT > 0; E2 = E2 0;
одаадл он T K(U 1AU T) det(A + E1 E1 + E2)= det A;
0 Z 1 dt T @ A K(U 1AU T) min trace(E1 E1 + E2) + (t) ;
A > t д (t) дал оой оно-оонн на A н, ан ол онн знанй ма A, н оод t
амм, однао, о а н (лжнна аоза), а мнн (н м маам UT U) жнноо ммноо олноо азложн а дололал дл й ма A, н да но алзоа нлллн а олм лом ооо адлнной ам
оом залн ла дла од о ноодмо амон алн ломо дололан, олада лй аалллзмо
а лааодж оан аалллзм модо дололан ммн оложлно одлнн ма оо да, оноанн наолзоан нолн оан олн (н.о..) азложнй
олзоан н -ололнно дл ааза одмо м... ло нодннм нмном оон -омалноо ддноо жн дл оаной ма, ооо мож олзоа а нй ооо аалллзмй дололал дл модаожнн адно
а оаной о оон олз нолно оано олно азложн ..о. ма A, днно аоа [3, 4]. о можно заа а GAGT = I + E;
д G - нжн олна азжнна маа ннлой даонал, E - мааоно. оз ннл мно ма G да заан. ойй о оноан на н азжнно ма G озй ннл мно нжно олнама Aq; q = 1; 2; 3; : : :
нан одл з ло мнммаK(GAGT). л оо доаоно олн n олн азложнй одма A, оонн нандн множа ннл мно аждой о G. ао дололан дм оознаа IIC(q) (анл. Incomplete Inverse Cholesky)
ол оннй лом дмаа оон нной азжнно f(i; j)g олано j (G)i;jj (G)i;i, д 0 < 1, олдм нм ма G дл ой . ом ло ай дололнноо м... нно н змн, заолннно ма G мож замно мн. ао дололан дм оознаа IIC(q, )
днао, нмо на"далн" аалллзмо ломо н.о..-азложн, оламй дололннй м... мож нодаоаза л ннамноо ол нм, м ла ойо даоналноо дололан H = (Diag(A)) 1
олма ом, о дл азанн "одн" алзай нолноо оаноо олноо азложн н оланнл мно ма G н ой ма GAGT оод оаздо мдлнн, м ооамой н заолнн оном жнном олном азложн ( м ол азложн 2-о ода), м. [9]. ом оо, лом о а заа налн мнн дололал G, м. дал .4
ол нй одод оан аоа [4, 11], д л дложн лонй аан моданолноо оаноо олноо азложн, озолй зналной м одол омн ндоа ойо н.о..-азложн
ом, о н д олзоа p ооо
одамааA одоа а, о а можно ол ннл мно оазал лоно-даоналной а, оой з p адан лоо мно однаооо азма
азжнно ма G м нжн олн лоо, аж ннл ол лон о, ла ннл мн нй одной ма Aq; q = 1; 2; 3; : : :. ода, л оадн лонондаоналн заолннно, оаза доаонм л н n аозай одма, оло p з н (оалн н зон)
ал, онно нозално л азанн p (о о, лон) оан олн множлй одма
оонн ло ма G можно ан нно, ажа з андан олн аоза анн p одма
, наон, омн аоза лоо о н озан онм, мо н можно олзоа жнн олн аоза 2-о ода ооом он, а о ло дложно алзоано аоа [15, 19, 22, 24, 25, 27, 28]. ао дололан дм оознаа BIIC(p,q)-IC2( ) (Block Incomplete Inverse Cholesky - Incomplete Cholesky of the 2nd order)
о, оонно дололан н оло маооо лла, но о а ооамо "наалллнм" жннм олнм азложнм й ма лом
о а л он мнално [15, 19] ооноан о ао [22]. алнй аз о мод олл аоа [27, 28], д наоно алн ой олноо азложн 2-о одал оон, ооноан ан мод н алано нй о лоам аоо дололал
дм ол дално оан лоной нолноо оаноо олноо азложн (BIIC) [4, 9, 11, 22]. маа A одона азанало м ж оазом, о дл зноо лоно-даоналноо дололан (Block Jacobi, BJ), .., t-й даоналнй ло ммно одонной ма м азм nt, д n1 + + np = n. д t = 1; 2; : : : ; p p { лона азмно ма A. л t-о даоналноо лоа одлм \ азно" множо ндо а fkt 1 + 1; : : : ; ktg, д kt 1 = n1 + + nt 1 (k0 = 0, kp = n), дм \ а" множандо fjt(1); : : : ; jt(mt nt)g; jt(p) kt 1. л аждоо t ао ндно множо, а ало, ла нд, н оод kt, оо оаза заннм t-м азнм множом ндо, нам, онолно азжнно ма Aq (л q-й н ма, олнной з A замной онолно мал мно нанл). д mt nt m1 = n1, .. о ао множо л м
оознан BIIC-дололал мож заан дм ддном д:p>
" # p X 0 H = VtUt 1 Ut TVtT; (10) 0 Int t=д Vt а д моолн ма, ол оо л дннм n-оам одлннм ндам, Vt = [ejt(1)j j ejt(mt nt)j ekt +1 j j ekt]; t = 1; 2; : : : ; p; (11) аажда нолна мааUt л ам множлм олоо t-й \ анной" даоналной (mt mt)-одма VtTAVt, .
VtTAVt = UtTUt; t = 1; 2; : : : ; p: (12) аоа [4, 9, 10] оазано, о BIIC-дололал H олада ойом K-омално дм мл. ознам з G множо азжнн нжнолн ма, оо м ннл мн оло оз (i; j), д j 2 fjt(1); : : : ; jt(mt nt); kt 1 + 1; : : : ; ig; kt 1 + 1 i kt; (13) t = 1; : : : ; p. одадл оонноо дололал адло далн H = GTG, д G = arg min K(GAGT) G2G (наомнм, о м мо ождо K(GAGT) = K(HA))
ал амаа жннй аан BIICдололан, оламй замной дл аждоо t = 1; 2; : : : ; p оноо UTU-азложн (12) наоо жнно IC2-азложн, налоно (9):p>
~ ~ ~ ~ VtTAVt = UtTUt + UtTRt + RTUt: (14) t д Rt { лоалн ма оо мнам j rijj <. ознам " # p X 0 ~ ~ ~ H = VtUt 1 Ut TVtT;
0 Int t= дм дл оо долаа, о а он мал мно анаам оазом, о mt nt даоналн ~ мно Ut оада оом мнам Ut. олзоанм оо доложн зложнн ой IC2 BIIC-азложнй, доаза да ома4 [22]. A л ..о. май; одаз ой азложнй IC2( ) BIIC(p) а да она ~ онон K-л ололнно ма HA HA:p>
p ~ Y K(HA) = det Imt + Rt(VtTAVt) 1RT exp(c0 ); (15) t K(HA) t=д 0 < c0 = c0(A)
ам оазом, з (7) д оналаай c0(A) ~ iK(") = log2 K(HA) + log2 (" 1) + : (16) log . ., дл ноооо доаоно малоо знан аамаон IC2-азложн лоо ооннй BIIC-IC2-дололал ~ H м о а ж он лаай м..., о Kомално BIIC-дололан (10). о ж м, BIIC-IC2азложн знално мн заа дл н, анн мнн дололал о анн \ онм" BIIC-дололанм (10), (м. [15])
нно оан оанн модо дололан IIC(q), IIC(q; ), BIIC(p;q)-IC2( ) оодло олзоанм нной ммной оложлно одлнной ма apache2, зой з олл азжнн ма налод. амаа, ознаа T. A. Davis, Y.F.Hu Y. University of Florida sparse matrix collection. To appear in: ACM Trans. on Math. Software, 2011. V. 38; нооой мной онно-азноной зада, м доаоно олой азм доолно лоо ололна: n = 715176, nz(A) = 4817870, (AS) = 2, (AS)= (AS) = 1:2 106, д max max min AS = (Diag(A)) 1=2A(Diag(A)) 1=2 дал оой ма оно, ммно мааоанн днной даонал
а дололнноо м... нанал нлоо наалноо жн x0 = 0 м оано жло ло k b Axk k 10 12k bk, д аа а b = Ax ла H H одом множн ма A нао ооо н x (i) = 1; i = 1; : : : ; n
аам дололанй задаал дм оазом:p>
(a) дл IIC(q) IIC(q; )) олзоала аноаодной ма оно, мнаа дн н н ма; аам он ал анм = 0:01;
() дл BIIC(p;q)-IC2( )) олзоала аноаодной ма оно, оаа доаоно заолннн лоно-даоналн а о оадам азмам лоо;
дл оо олзоала одода ломаPABLO15;
знан аамо мод жнноо олноо азложн I2 [12] ал анм = 0:01; = 0:0001; = 0; = 0:1;
а оодл нанаолном AMD Athlon 64x2 Dual Core Processor 4200+ (2.21 GHz, ам 2 Gbytes) од MS Windows XP v.2002 Service Pack 2 омлоом Intel Fortran Compiler 6.0 for Windows ом омл i /Ox /G6 /Qxi /Qip *.for. м аод нда
. 1 2 л зла, олнн дл лалоо p = 1; 2; 4; : : : ; 256; 512 олзоан дололанй BJ(p)-IC2(0.01) BIIC(p;4)-IC2(0.01). амм, о дл оо модо ла p = 1 оа одн о ж мод IC2(0.01)-CG, оаннй ддй ла
D. Fritzsche, A. Frommer, and D. B. Szyld, Extensions of certain graph-based algorithms for preconditioning. SIAM Journal on Scienti c Computing, v.29, no.5, (2007) 2144-2161
.1. ло ай м... замо о лалоо дл дололанй BJ( p)-IC2(0.01) BIIC( p;4)-IC2(0.01) зада apache2
.2. м ам... замо о лалоо p дл дололанй BJ( p)-IC2(0.01) BIIC( p;4)-IC2(0.01) зада apache2
.3. ло ай м... замо о н q дл модо IIC( q), IIC( q;0.01) BIIC(512;q)-IC2(0.01) зада apache2
.4. м ам... замо о н q дл модо IIC(q), IIC( q;0.01) BIIC(512;q)-IC2(0.01) зада apache2
. 1, оаза, о ло ай лоноо мода о доолно но озаа н лалоо (а о ознаа, о аалллной алза д нно нжа оазал но), о м а дл модаBIICIC2 ло ай а н змн. . 2 оаза, о азанно оонон о ой ж м оан дл мн а(.., лаоай)
аман. алдамй нзамо ла ай м... л лоо до p = 512 он м, о озмн, номо аздлнм нало, н оло анлно нло (а а л, мл -омално, мнмално озможнм), но оа нзамнм наон оно, номой жнной аозай лоо. ом оом p азм лоо мна, аоза ано он, доаоно олом p ж нана о лаай за н озмнй, ном аздлнм нало. л аоза лоо ол оно, о, номннно, о лаай м..., д налда ж нана мал знанй p
. 3 4 л зла, олнн дл азн знанй н q о 0 до 6 олзоан дололанй IIC(q), IIC(q;0.01) BIIC(512;q)-IC2(0.01) оонно. амм, о q = 0 мод IIC(0) IIC(0;0.01) од оном дололан о, мод BIIC(512;0)IC2(0.01) од BJ(512)-IC2(0.01). озаан q оод нно оан лаай, но аж доожан заа надололан
олано оазанной на.3. замо лаай о н , ан знан q лоно дололан нно мн ай, м он. дой оон, оноаннй лом IIC(q;0.01) о оло ж л даж мн ай о анн ойм модом IIC(q) (оой, а ало, олз зоно оло ннл мно дл омоан ма G)
амо мн ао н анно мно однаоадл модо, м. .4. д о ла налда ажннй омм о q (дл модо IIC о q = 2 дл BIIC о q = 4). днао олнно можно д замно мо модаIIC(q;0.01) над IIC(q) ( олоааза дл q = 3 за нноо мнн заолннно дололал). о од, мод BIIC(512;3)-IC2(0.01) мна м а о дааза(о анн IIC(3;0.01))
ам оазом, дл озолной азжнной ..о
ма ооно дололан, оа наджно ао л з жнн олн азложнй аалллзмо о (но мн н) лон модо
о ждн л одом, дланнм залн ла
а лаадал маналдн ла лооазно мнн K-омалн дололанй модаожнн адно. нй одн ой аналз модо олномалноо дололан H = pd 1(A) ммн оложлно одлнн ма A оо да
лоо ололнн ма азжннм ом ола намн онн знанй онажа айн нно омза оадололао мноолна, од з анданоо ло мнмза алноо лаололнно. ма. ао, о дололао мноолна д, !, + 2t + pd 1(t) = 1 Td Td t;
p p д Td(x) = ((x + x2 1)d + (x x2 1)d)=2 - мноолн а оо одаd-й н, ln d 0 < (A) < (A) ; = ;
min max 6d наалннй налн -ололнно, од оаздо ол ном дололан, озолм оа мод л н аалллзмо, ом а оан о ло оай
а лааодж оан модо дололан озолн ммн оложлно одлнн ма оо да, оноанн наолзоан малоаноой мода, д H = I + CSCT:p>
д C - оанна n m-мааолноо олооо ана, м m n, S - ммна m m-маа, одлма з ло мнммаK(HA). азанна он ладложна [4] зна [8], д ло анолно, о -омза аоо дололан од о S = (CTC) 1 + (CTAC) 1; (17) нооом знан = (A; C). л аоо олзоан можно олож = 1
налз олам н ан а дл K(HA), а дл C(HA), од одном ом ж залн: нйна оолоа оло ма C должнадоаоно ооо омоа онно одоано ма A, оа намнм оннм знанм
оа оданоаноднно од оон олнной омл д H = B 1 + V (VTBV ) 1 + (VTAV) 1 VT;
д а ма B олз ло оама маа, о жаа A (на., лоно-даонална а). оонно дололан м мо онон о мном знм д- мнооонм дололанм, озол доолнлно о но
алн одж д онон зла да
1. азаоананоа о одмо модаожнн адно, оноанна наолзоан K-лаололнно
2. азаоанао дололан ммн оложлно одлнн ма одом жнн олн азложнй 2-о ода, ооноанм а з -ло ололнно, а мна алноо ла ололнно
3. азаоанао дололан ммн оложлно одлнн ма одом оан жнн олн азложнй, ом л олзоанм лоно нлоной ома, ооноанм мна -ла ололнно
4. о зн о омза -лаололнно амон олномалн дололан, оона ооноанмза оо мноолна, одо о омалном а дололан дл ажноо лаа ..о. ма
5. азаоанао дололан ммн оложлно одлнн ма одом -омалной малоаноой мода, ооноанм а з -ло ололнно, а мна алноо лаололнно
нон ла оао м да:p>
[1] мн .., аон .. ална омза н аонн модо. I // н.: нн мод оо оанза нй, . 7, а. нан. мн. , 1984, .139, .51{60
(од: A. Yu. Eremin and I. E. Kaporin, Spectral optimization of explicit iterative methods. I. Journal of Mathematical Sciences, 1987, V.36, no.2, P.207{214) [2] мн .., аон .., ан .. н нйн м олой азмно наон онйн : ной одод омза н аонн модо // н.: оо н. онйза нй. (од д
..лоооо ..нноа), анй о о омлной олм "на", оа, 1986, .114{124
[3] аон .. нанй одод он лаай модаожнн адно // н.: нн мод оаммно он (од д. . . зноа) - .: , 1990, .55{72
[4] аон .. дололннй мод ожнн адно дл н дн налоо дналн зада // налн анн, 1990, .26, 7, .1225{1236
[5] аон .. дололан ллан мода ожнн адно // н: аж. дн аалллн он мод н нйн м. .:p>
, 1990. .343{355
[6] аон .. аонно н м нйн аннй олзоанм нолной оаной олной аоза // н: м оан зада мамаой з. .: зд-о , 1991. . 71{77
(од: I. E. Kaporin. Iterative solution of systems of linear equations using incomplete inverse triangular factorization. Computational Mathematics and Modeling vol.4, no.1 (1993) P.28{32) [7] аон .. он н дололан мода ожнн адно // н. -н. 1992. . 28. 2
. 329{339
[8] Kaporin, I.E. Explicitly preconditioned conjugate gradient method for the solution of nonsymmetric linear systems // Int. J. Computer Math., 1992, V.40, P.169{187
[9] аон .. н ан адоонн н дололанй // н. . .15. л. мам. на, 1993. .2, .28{42
[10] аон .. мза ломо модаожнн адно. // н: ама модл омза лн ломо. .: зд-о , 1994. . 50{62
(од: I. E. Kaporin, Optimization of conjugate gradient algorithms, Computational Mathematics and Modeling 1994, V.5, no.2, P.139{147) [11] Kaporin, I.E. New convergence results and preconditioning strategies for the conjugate gradient method // Numer. Linear Algebra with Appls., V.1, no.2, 1994, P.179{210
[12] Kaporin, I.E. High quality preconditioning of a general symmetric positive matrix based on its UTU + UTR + RTU-decomposition // Numerical Linear Algebra Appl., 1998, V.5, P.484{509
[13] Kaporin, I.E. Second order incomplete Cholesky preconditionings for the CG method // in: Proc. of IMMB'98, Iterative solution methods for the elasticity equations as arising in Mechanics and Biomechanics, Nijmengen, The Netherlands, Sept. 28-30, 1998, P.47{49
[14] eмн .., аон .. н наол онн знанй налнн одмо модаожнн адно, нн мод оо оанза нй
XIII, а. нан. м. , 248, , ., 1998, .5-16
(од: A. Yu. Yeremin and I. E. Kaporin. The in uence of isolated largest eigenvalues on the numerical convergence of the CG method
Journal of Mathematical Sciences 2000, V.101, no.4, P.3231{3236) [15] Kaporin,I.E. and Konshin,I.N. Parallel solution of large sparse SPD linear systems based on overlapping domain decomposition // in: Parallel Computing Technologies (Ed. V.Malyshkin), Proceedings of the 5th International Parallel Computing Technologies Conference (PaCT-99), St.-Petersburg, Russia, September 6-10, 1999. Lecture Notes in Computer Science, Vol. 1662, Springer-Verlag, Berlin - Heidelberg - NewYork, 1999, P.436{445
[16] Kaporin, I.E. Optimizing the UTU + UTR + RTU-decomposition based Conjugate Gradient preconditionings // Rep.0030, November 2000, Department of Mathematics, Catholic University of Nijmegen, Nijmegen, The Netherlands, 16p
[17] Axelsson O., Kaporin I., Konshin I., Kucherov A., Neytcheva M., Polman B., Yeremin A. Comparison of algebraic solution methods on a set of benchmark problems in linear elasticity // Tech. Report of Department of Mathematics, University of Nijmegen, The Netherlands, 2000, 89p
[18] Axelsson O., Kaporin I. On the sublinear and superlinear rate of convergence of conjugate gradient methods // Numerical Algorithms, 2000, V.25, P.1{22
[19] аон .., онн .. аалллно н ммн оложлно-одлнн м наоно ао азн нало // н. л. ам. ам. з. 2001, .41, .481{493
[20] Axellson O., Kaporin I. Optimizing two-level preconditionings for the conjugate gradient method // Rep.0116, August 2001, Department of Mathematics, Catholic University of Nijmegen, Nijmegen, The Netherlands, 21p
[21] Kaporin I.E. Using the Modi ed 2nd Order IC Decomposition as the Conjugate Gradient Preconditioning // In: Proc. of PRISM Conference, 20{23 May. 2001, Nijmegen, The Netherlands
[22] Kaporin I.E., Konshin I.N. A parallel block overlap preconditioning with inexact submatrix inversion for linear elasticity problems // Numerical Linear Algebra with Applications, 2002, V.9, no.2, P.141{162
[23] Kaporin I.E. Using the Modi ed 2nd Order Incomplete Cholesky Decomposition as the Conjugate Gradient Preconditioning // Numerical Linear Algebra with Applications, 2002, V.9, P.401{408
[24] Kaporin I., Konshin I.N. Parallel Conjugate Gradient Preconditioning via Incomplete Cholesky of overlapping Submatrices // In: Book of Abstracts, Parallel Computational Fluid Dynamics, May 13{15, 2003, Moscow, Russia, P.52{54
[25] аон .., онн .. аалллно н нйн м олзоан жнной аоза а лоо. // н.:p>
\ амао модлоан. олм зла." (д
..лоой, ..н) аа, оа, 2003, .308{319
[26] Kaporin I. Superlinear convergence in minimum residual iterations // Numerical Linear Algebra with Applications, 2005, V.12, P.453{470
[27] аон .., онн .. ола множлй IC2азложн дл алано аалллноо дололан
// . . а. а. з., 2009, .49, 6, .940{957
[28] Kaporin I.E., Konshin I.N. Load balancing of parallel block overlapped incomplete Cholesky preconditioning. // Lecture Notes in Computer Science, Vol. 5698, Springer-Verlag, Berlin-Heidelberg, 2009, P.304{315