WWW.DISSERS.RU


...
    !


 >> 

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 class of iterative methods for nite element equations. Computer Meth. Appl. Mech.

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 , .

, (, , ), , . , , , " ".

. :

1. , , , , , .

2. .

3. , ( ) .

4. ( ).

5. ( , ) .

. ( ) ( ) , . , , .

, , . , .

, ; , , , , / .

, , "" ( ).

, , , , . .

. . , , , . :

1. , ( ), K- .

. ,8 .

2. - , , . , , , .

3. , 2- , O. Axelsson. Iterative solution methods. Cambridge University Press, Cambridge, 1994.

, -.

4. - , . - , . , .

5. - , , , , .

6. - , .

, . , .

. , .

, , .

, , , .

, , , .

. , , . , , , - .

, :

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.

(...):

r0 = b Mx0; p0 = r0; i = 0; 1; : : : :

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 :

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, :

r0 = b Ax0; p0 = Hr0; i = 0; 1; : : : :

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 :

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:

j (U)i;jj ; j > i;

+ 1 K(A) 1=n nz(U) n 1 + ;

; n; K(A).

, ,10 ,11 [12], , :

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 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) :

(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 + :

min max p p C(U 1AU T) (1 + ) + 1 + + :

, - , 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 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):

~ ~ ~ ~ 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 ~ 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; http://www.cise.u.edu/research/sparse/matrices - , : 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.

:

(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:

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. - , - , .

:

[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] .. // : . . .:

, 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] .., .. . // .:

\ . ." (.

.., ..) , , 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.

 >> 






2011 www.dissers.ru -

, .
, , , , 1-2 .