| Under normal circumstances,as we get the numerical solution of partial di?erentialequations by computer,it is normally the first through the finite element method or finitedi?erence method to discretize partial di?erential equations to form algebraic equations Ax =v,and then solves the equations.Generally speaking,the coe?cient matrix of these equations have a large,sparse,pathological (condition number is very big) and other characteristics,although in the calcu-lation can be directly elimination operation,but in the process of elimination,you may fill inthe original sparse matrix,resulting in space burden. Therefore,for such equations shouldbe applied to solve some special techniques. Traditional algorithms for solving discrete equa-tions are Jacobi iteration method and Gauss-Seidel iteration method,etc. However,withcontinued refinement of the grid,not only unknown number of equations,condition num-ber also will be increased,more and more di?cult to obtain satisfactory results. In con-trast,successive overrelaxation iterative method (SOR) has a good e?ect,but its conver-gence rate is extremely sensitive to the relaxation factor w,w values when the best time alittle discomfort,SOR of the convergence speed will be significantly reduced,and the Withthe grid refinement,the best w is not readily available.The basic ideas of multi-grid method put forward in the 20th century,60's,and itdeveloped very quickly from the 70's. With the finite element method and finite di?erencemethod combined with,it has become to solve linear and nonlinear partial di?erential equa-tions of the most e?ective methods. Its approach is mainly split in a variety of steps tosmooth meshes,allowing polishing solution of the function of various frequency error,toachieve an overall polished e?ect,to improve accuracy and convergence speed. The biggest advantage of multi-grid method when used with the iterative method is with the subdivisionof the encryption,the number of iterative steps,and no significant increase.However,theprice paid for is the more complicated networks from fine to coarse network restrictions andcoarse network extension of the fine mesh such as correction processing. Simply considerthe adoption of partial di?erential equations are discretized algebraic equations Ax = v,ifin the fine mesh level,through some sort of transformation on the equation of eliminationcan become coarse net-level equations,while the calculation of the price is not consideredtoo large or support parallel,then no doubt it is our most want to see.Cyclic reduction method is a very suitable parallel method that can be used to solve ageneral block tridiagonal equations,the basic idea is the implementation of elementary rowoperations,in the even-numbered odd-numbered equations eliminate argument to get a half-scale three-diagonal equations. After some steps,we can generate a sequence of tridiagonalequations A(k)x(k) = v(k),each of equations is still three pairs of angle,and the order countfor half of the previous equations. Then by the last one of equations A(J)x(J) = v(J) solution ofa x(J),then by progressively back to generation,from x(k+1) to be x(k),ultimately be x(0) = x.Thus,using O(N) a Processor only O(log2N) steps to complete the calculation.We focus on two special cases.For the boundary value problemthe coe?cient matrix has a very good nature by cyclic reduction method .Through discus-sion, we can get the following conclusionsTheorem 1 For the di?erential equation (1.1) or di?erence equations (1.2), thesystems obtained from one step cyclic reduction has the same coe?cient matrix as thesystems built on the the coarse level grid,the right hand side is the amendment obtainedfrom numerical integration which use complex trapezoidal rule 2h instead of rectangular rulef2i·2h.Consider the following elliptic boundary value problemsλ1,λ2,λ3are constants ,andλ1 > 0,λ2 > 0,λ3 0.On ? for n×n uniform rectangular subdivision, h1 and h2 respectively, x and y directionof the step. five-point di?erence schemes of di?erential equation:For (1.3) and (1.4) we give a Deformation of Cyclic Reduction method,and we havethe following conclusions through discutionTheorem2 For di?erential equation(1.3) or di?erence equation (1.4), Deformationof the Cyclic Reduction method can save about O(n3) in every step than the standardmethod.Nested subdivision sorting was originally a sorting method for di?erential equationsused in large-scale grid nodes are given . From the equations it is equivalent to the unknownelement of the equation and re-sorting. It can greatly increase the algorithm parallelism.For the two-dimensional and even higher-dimensional case,the coe?cient matrix becomescomplex,nested subdivision method of sorting the corresponding also becoming more com-plex. This article highlights the two-dimensional case of nested subdivision sorting .By asorting example we show the details of this method and show that it can be used with O(N2)a processor in the O(N) steps to complete pairs of equations Ax = v of the solution.Hierarchical basis is a method which used to select the basis function of the finite ele-ment method for solving partial di?erential equations and it is very convenient in the calcu-lation.For the following question as the finite element method: Take n = 2J+1for example,in xi = a + ih we select the triangular hat function based on thesame level grid as its basis function. It brings a lot of convenience solving problem by usingthis hierarchical basis functions form a finite element equation.In fact,this hierarchical levelfunction layer selection method precisely nested subdivision sort.To the node xi number isi,then the number is 20 of the odd multiples of the nodes is the most fine layer of gridnodes,the base function is selected as:Number is 21 of the odd multiples of the node,basis function is selected as:After this are 22,23,···,this is an application of nested dissection sorting in FEM.Finally,in the article we gives a two-dimensional elliptic equations numerical exampleand we get the experimental results that match the theoretical predictions.
|
PDF Full Text Request