Some Parallel Algorithm For Solving Linear Equation Systems And Parablic Equations

In this paper, we mainly present several parallel iterative methods for linear equationsystems and several parallel algorithms for parabolic equations. In the meantime,motivated by the difference methods for two-dimensional problems, we also brieflydiscuss the difference methods and difference graph for the problems through using thedifference relationships of adjacent points.As is known to us, there are several direct methods for solving linear equation systems,such as LU Factorization method, Cholesky Factorization method, Block DiagonalPivotal Element method and so on, which have already been widely applied in numerousareas. However, parallel iterative methods show their advantage in several practicalapplications, because we do not need exact solutions to some large linear equationsystems or the coefficient matrix is special (e.g. sparse matrix). In parallel iterativemethods for the linear equation systems, we mainly describe and analyze paralleliterative and parallel multisplitting iterative methods, which are implemented by theRed-Black Ordering method and Multicolor Ordering method.Generally speaking, G-S iterative and SOR iterative methods, whose computation ofthe values on the( k + 1)step required the values on the( k )step are not suitable for parallelcomputation, but for some discrete equations for some specific elliptic boundaryproblems, they can be implemented independently by the Red-Black Ordering method.Considering the Poisson equation u_xx + u_yy= f, where ( x , y ) ∈Ω = [0,1] × [0,1] .Nowwe divide the domain of definite Ω into square meshes by h = 1/(n+1) in x andy direction. Let u_ij to represent the approximate solution of u ( x_i , y_j). The derivation inequation can be replaced by the two-order difference quotient. So we obtain thedifference equations for the Poisson equation mentioned above.u_(i+1),j+u_(i-1),j+u_i,(j+1)+u_i,(j-1)-4u_i,j=h²f_ij i,j=1,…n (1.1)After discretization of (1.1), we get the linear equation systems of n 2, and arrange all therequired nodes in row. Next we divide all nodes into red and black, which are rewrittenfrom left to right and from bottom to up. In the meantime, we arrange all the requiredvalues at the points correspondingly, thus we get the matrix forms of the linear equationsystems (1.1)TR R RB B BD C U bC D U b??? ?????? ??? =??? ??? (1.2)Where D R=4 I R, D B=4 I B, I Rand I B are unit matrixes, whose orders equal to thenumbers of the red points and the black points respectively. Matrix C contains mutualeffect between required red and black nodes. -h2 fijand the known values of function uon the boundary constitute components ofb . Now we apply G-E iterative method to (1.2),we get the expressions of u R( k+1 )and u B( k+1 ).u R( k +1 ) = DR ? 1 ( bR ? Cu B( k ) ), u B( k +1 ) = DB ? 1 ( bB ? C T uB( k)) (1.3)So, solving (1.3) has been changed to the matrix-vector multiplication.The SOR parallel iterative method is devised as follows. First, we can calculate thevalues u R( k+1 ) on the red points by the G-S iterative method. Then, we compute thevalues u R( k+1 ) by the SOR iterative method. So, using the values u R( k+1 ), we obtain thevalues u B( k+1 )by the G-S iterative method. At last, we get the values u B( k+1 )by the SORiterative method, two iterative formulas of which are as follows.( 1) 1 ( ) ( 1) 1 ( )( 1) ( ) ( 1) ( 1) ( 1) ( ) ( 1) ( 1)( ) ( )( ) ( )k k k T kR R R B B B B Rk k k k k k k kR R R R B B B Bu D b Cu u D b C uu u ω u u u u ωu u+ ? + ?+ + + + + +??? = = + ? ? ??? = = + ??For the red points, a step of G-S iteration is equivalent to a step of Jacobi iteration, so it isfor the black points.Although we can obtain the linear equation systems of the form that is similar to (1.2)for some more general equations, which contain mixed partial derivative (e.g.u xx + u yy + αuxy= 0) by the methods mentioned above, the forms of (1.3) cannot beobtained, because DR and DB are not diagonal matrixes. In order to solve theproblems, we make use of the Multicolor Ordering method, by arranging all the nodes inthe Multicolor Ordering rule, then, apply the G-S iterative method to (1.2), which hasbeen rearranged. So, we get the G-S iterative formula.1( 1) 1 ( 1) ( )1 1i rk k ki i i ij j ij jj j iu + D ? b ?B u +B u= = += ?? ? ???? ∑ ∑ ?Here the diagonal blocks are diagonal matrixes. This kind of equation can also becalculated through reducing it to the Jacobi iteration, which can be implemented by theRed-Black Ordering method mentioned above.In essence, Red-Black Ordering and Multicolor Ordering rearrange or block thecoefficient matrixes of linear equation systems, with which Multisplitting iterativemethod has the same principles. Multisplitting iterative method splits the coefficientmatrix A in the following rule: 1 11l l , l , l , l, 1,2, .lA M N M ? αE I M ?l== ? ∑ = = So weobtain the iterative forms from linear systems by the foregoing splitting method. In detail,the method is described as follows, (1) calculate yl , M l yl = N lx ( k)+ b , l= 1,2,. (2)Calculate ( 1)1k l l.lx +αE y== ∑ the first step can be implemented independently, in the secondstep, we get the weighted average, and then return to the first step, until it achieves theaccuracy we required. Sometimes, we could use the relaxation factor to accelerate theconvergence.In some practical problems, many phenomena are described and computed byparabolic systems. It has proved that numerically solving parabolic partial differentialequation by finite difference method is significant in theory and application. Classicexplicit scheme has the best parallelism, but the stability is conditional. Classic implicitscheme and Crank-Nicolson scheme have unconditional stability, but they have noobvious parallelism at all. Evans and Abdullahd first proposed the Group Explicit scheme(ab. GE) which is devised through smartly grouping different asymmetric differenceschemes. This scheme solves the problem explicitly. GE scheme constructs two kinds ofasymmetric difference schemes at the point ( i ,( k + 1) / 2) and combines them. It makesthat two values of the ( k + 1) time level can be computed by four values of the ( k )time level explicitly. So, six points described above constitute a group. We divide thedomain of definition into several groups, the parallelism is obvious. According to thedifference of the redundant points at right or left side of the boundary, GE scheme consistof GER scheme and GEL scheme. Through analyzing the stability, we get thatfor r = ? t / ? x2≤ 1, GE scheme is stable. Its truncation error is O ( ? t+?x), which is betterthan asymmetric difference schemes'. Since GER and GEL schemes are used alternatelyon two adjacent time levels, the stability of the AGE method has been changed, it isabsolutely stable and truncation error is O ( ? t+?x).Inserting an implicit scheme into the GE scheme, we get the 'GE-3' scheme. For theaddition of the implicit scheme, the truncation error has been changed greatly. In theGE-3 scheme, three values of the ( k + 1) time level can be computed explicitly by fivevalues of the ( k ) time level. In order to keep the truncation error small, we combine theclassic explicit scheme and the classic implicit scheme to compute the points at the rightor left side of the boundary, which they cannot constitute a group. The AGE-3 method isdevised as follows. On the odd time level, the computation schemes are arranged to be'Explicit–GE-3' from left to right successively, and the redundant points at the right sideof the boundary can be computed by the same method mentioned above. On the eventime level, we alternately use the schemes on the odd time level: change explicit schemes,implicit schemes and asymmetric difference schemes into implicit schemes, explicitschemes, and asymmetric difference schemes respectively. In the same way, we disposeof the redundant points at left side of the boundary. The AGE-3 method is absolutelystable. Its truncation error is better than AGE method's.Motivated by the construction of the GE-3 scheme, we obtain the ASE-I methodthrough adding more than one classic implicit schemes to the GE scheme, whichconstitute an implicit segment. In detail, ASE-I method is described as follows.Assuming that m ? 1 = NL , N ,Lare positive integers, L ≥ 3.We divide the nodes on theodd time level into N independent computational segments .The computation schemesare arranged to be 'Explicit–SE-I–Explicit' from left to right successively. On the nexttime level, i.e., the even time level, we also divide nodes into N segments. Wealternately use the schemes on each segment of the odd level: change explicit schemes,implicit schemes and asymmetric difference schemes into implicit schemes, explicitschemes, and asymmetric difference schemes respectively. Thus the computation rule onthe even time level changes to be 'SE-I–Explicit–SE-I'. Alternately using the twoalgorithms in time direction, we obtain the ASE-I method. ASE-I method is absolutelystable, its truncation error is O ( ?t 2 +?x2)at the inner points, and it is good at the pointsof the boundary.Traditional Crank-Nicolson scheme has two-order accuracy in solving onedimensional parabolic equations, but it must to compute a tridiagonal system, whichleads to some difficulties in the implementation of parallel computing. Throughreconstructing C-N scheme, we could divide the equation system into several small scaleequation systems, which can be computed independently.Among the basis finite difference schemes mentioned above in solvingone-dimensional problems, AGE method and ASE-I method have been promoted totwo-dimensional problems, and both of them have absolute stability and good truncationerror, so it is suitable for all kinds of parallel computer systems. Being similar to it insolving one-dimensional problems, AGE method in solving two-dimensional problemsalternately uses GE blocks from one time level to another. The ABE-I method, which isobtained from the promotion of the ASE-I method for one-dimension to two-dimension,is devised as follows: Assuming that we have obtained the approximate values at thepoints on the ( k ) time level, we divide the nodes on the ( k + 1) time level into severalindependent computational blocks. The approximate values at the points on the blockscan be computed by some explicit blocks or some implicit blocks. In detail, we block thenodes on the ( k + 1) time level by 4 × 4 points successively, of which the nodes can becalculated by explicit blocks or implicit blocks mentioned above independently. On the( k + 2) time level, we alternately use the schemes on the ( k + 1) time level. In the sameway, we obtain the values at all nodes.The Alternating Difference Block method is a new method for two-dimensionalproblems, which is motivated by AGE method and ABE-I method for two-dimensionalproblems. This method uses the difference relationships of adjacent points for theproblem. It contains Difference Block method and Complementary Difference Blockmethod. On the ( k + 1) time level, if we know the Difference Block method for theproblem, we could obtain the method for the problems on the ( k + 2) time level byComplementary Difference Block method on the ( k + 1) time level. Under someconditions, this method has parallelism and its stability is good.