> lokM REbjbj'2'2-EXEX\/]DDDDD\DD~:222J%%%/111111$h\U)%%%%%U}2J}}}%2J/@@%/}}//24BDD;B/
Fabled Boundary Condition Forecast Algorithm
in Multigrid Domain Decomposition Parallel Computing
Guo Qingping1 Yakup Paker2 Zhang Shesheng1
Dennis Parkinson 2 Wei Jialin1
1Wuhan Transportation University, Wuhan 430063, P. R. China
2Queen Mary & West field College, University of London.E1 4NS U.K.
HYPERLINK "mailto:qpguo@public.wh.hb.cn"qpguo@public.wh.hb.cn HYPERLINK "mailto:guo@dcs.qmw.ac.uk"guo@dcs.qmw.ac.uk HYPERLINK "mailto:paker@dcs.qmw.ac.uk"paker@dcs.qmw.ac.uk
Abstract: We propose a fabled boundary condition forecast algorithm for multi grid parallel computing, and derive a forecast function formula in this paper. Numerical results of one and two-dimension boundary condition problems obtained with the algorithm in a PVM network computing environment show that the algorithm has high parallel efficiency.
Keywords: Multi-Grid, Domain Decomposition, Boundary Condition Forecast
1.Introduction
In recent years, several new multi grid parallel algorithms have been proposed in the literatures [1,2,3]. Guo Qingping et al (1998)[1] considered the domain decomposition method for cyclical temperature in ceramic/metal composites, and showed that MGP algorithm can obtain good numerical computing speedup in networking computing environment. Xu Zhengquan (1996) [ 2] discussed domain decomposition method of multi-grid distributed computing, and pointed out that a good initial value is very important when the equation is solved using iterative method. Iterative methods are used often in MGP, and amount of computing and communication increase as the number of iterative increases. Louis (1982)[3] detailed the polynomial iterative method which may speed up iterative speed, and showed that better initial value may be obtained by using his theory.
According to the theory given in reference [3], we decompose a numerical domain into several sub-domains. Boundaries between sub-domains are defined as a fabled boundary, and a mathematical model to forecast the boundary value at the fabled boundaries is proposed. Some numerical examples are given to show how to use our algorithm.
Full multi grid method is one of efficient multi grid method ([4] 1986 H. Hoppe). Combining the fabled boundary condition forecast method with the FMGM we can obtain a high efficient parallel fabled boundary condition forecast full-multigrid method.
2. Construction of boundary forecast function
Many boundary problems may be written as :
Lu (x) = f(x) x" (1)
Lu (x) = f(x) x"
The is a define domain of unknown function u (x), is a boundary of , L is a differential operator. Supposei is ist grid on and i a corresponding boundary by using difference method, Eq (1) may be written as
Liiui(x) = fi(x) x" (2)
Liiui (x) = fi(x) x"
We decompose domain into several sub-domain i, i =1,2,..,m, i is boundary of sub-domain i, so that the fabled boundaryin is
in=1+2+...+m
Suppose ui(xin) are the numerical value of function u while xin"i n, then {ui(xin) } is a sequence of fabled boundary points. By using of u1(xin),u2(xin),...,um(xin), we construct a subspace
Rn = span{u1(xin),u2(xin),...,um(xin)}
Assume that G is a mapping of Rn to space R, and
vn+1=G(Y) Y"Rn (3)
then it is possible to take vn+1 as forecast initial value on the fabled boundary for (n +1) th grid, and vn+1 should satisfy condition:
%vn+1-u(xin)%<%u n- u (xin)% xin" (4)
here u(xin) is function value at point xin. We propose some models to forecast vn as following. In those models, symbol vi,j is used to denote the fabled boundary value of jth model on the ith grid.
Model 1. One step forecast function
vn+1,1(xin) =un(xin)
Model 2.Two step forecast function
vn+1,2=un-2+3(un-un-1)
Theorem 1. If n!", un!u(xin), then if n!", vn+1,1!u(xin), vn+1,2!u(xin).
Proof. When n!", un!u(xin), so that if n!",un-un-1!u(xin)-u(xin)=0
Therefore if n!", we obtain
vn+1,1=un!u(xin) vn+1,2=un-2+3(un-un-1)!u(xin)
#.
Theorem 2. Let us denote u(s) as u s in which the s is an integer variable. If
u(s) = un-1 + C1(s n + 1)+ C2(s n + 1)2 (5)
then u(n+1) = un-2+3(un un-1)
where the C1 and C2 are some kinds of constant.
Proof. From the conditions of the theorem, we may derive formulas for C1 and C2:
C1 = 0.5 (un-un-2) , C2 =0.5 (un-2un-1+un-2)
so that
u (n+1) = un-1+2C1+4C2 = un-1+un-un-2+2(un-2un-1+un-2)
= un-2+3(un-un-1)
#.
Eq.(5) is a polynomial of degree 2. From Eq.(5), the model 2 can be derive when s=n+1, and the maximal value of Eq (5) is
umax = un-1- 0.25C12/C2
Model 3. Maximal value forecast function vn+1,3
vn+1,3 = un-1 - 0.25C12/C2 (6)
Theorem 3. If {un} is a non decreasing sequence and has a limit value, and
%un+1-u(xin)%<%un-u(xin)%.
then vn+1,3>vn+1,2
Proof. Because {un} is the non decreasing sequence and has a limit value, and
%un+1-u(xin)%<%un-u(xin)%.
then
C1 = 0.5 (un-un-2) > 0
C2 = 0.5 (un-2un-1+un-2) =0.5 [un-un-1 - (un-1-un-2)] < 0
so that the limit value of Eq.(5) is the maximal value of Eq.(5), and
vn+1,3 = umax > vn+1,2
#.
Obviously it is easy to proof theorem 4.
Theorem 4. If {un} is a decreasing sequence and has a limit value, and
%un+1-u(xin)%<%un-u(xin)%.
then vn+1,3 < vn+1,2
3. Fabled Boundary Condition Forecast Algorithm with Maximal Values
Using model 3, value of function u at fabled boundaryin in domain decomposition can be forecasted. Numerical procedure could be described as following.
(1).Calculate function value ui on corresponding grids by few sweeps, there i = 1,2,3. The ith grid is coarser then (i+1)th grid. So that initiative fabled boundary values on each sub-domain at the first three grids are obtained.
(2).According to model 3, calculate v4,3;
(3).Taking v4,3 as fabled boundary value at fourth grid, interpolating the current approximation of function u3 onto the next finer grid to get initiative value of u4. Calculate the function value u4 in each sub-domain by iterative method respectively;
(4). Interpolate the current approximation of function u4 onto the next finer grid to get initiative value of u5.
(5).Calculate value of u5 by few times of globe iteration among whole domain. This step needs sub-domain boundary value exchange, and the fabled boundary value at each sub-domain can be calculated out. This step is used to smooth forecast error of fabled boundary value.
(6). If (u5-u3)(u3-u1)>0, and %u5-u3%<%u3-u1|, then with data (1,u1), (3,u3), (5,u5) calculate v6,3 by Eq.(5) and (6), there u1, u3 and u5 replacing un-2, un-1 and un respectively. Otherwise let v4,3=0.5(v3,3+v4,3), and go to step 3. Value of u1, u3 and u5 are all obtained by global domain iteration.
(7). If "%u5-u3%<, is an required error bound, then function value u5 is a required result, and the calculation ends. Otherwise go to next step;
(8).u3!u1,u4!u2,u5!u3,v6,3!v4,3, go to step 3.
According to the step (3) of the numerical procedure, fabled boundary value need not change on same grid in each pair of sub-domains, so that we need not communicate between sub-domains during iteration. From step (2) and step (6), we can forecast next finer grid function value at fabled boundary by the value of three coarser grids.
4. Case study
Example 1. One dimension boundary problem.
u = -100x2 x"=[0,1]
u(0) =u(1) = 0
The exact solution of this equation is u = 25x(1-x3)/3
In order to explain our numerical method simply, we decompose domain into two sub-domain 1=[0, 0.5] and 2=[0.5, 1], and take two networked computers to calculate function u on each sub-domain respectively, the nth computer only calculates function value u on nth sub-domain, n =1,2. The parallel software environment used is the PVM. In this simple example, the fabled boundary is at point x = 0.5. Let the step length of the coarsest grid (1st grid) is h = 0.5, the 2nd grid h = 0.25, the 3rd grid h=0.125, etc. At fabled boundary x = 0.5 let initial function value u0=0. Using model 1, we calculate the function value u1 on first grid by few iteration, then interpolate u1 into second grid and calculate function value u2 on second grid, etc. We obtained u1 (x) =3.125, u2 (x) =3.515 etc at the point x=0.5. By using model 3, after few iterations on the first three grids we forecast the function value v 4, 3 = 3.63745 at fabled boundary x=0.5.Then calculate function value of u on 4th grid by solving two sub-domain relevant independent boundary condition problem. Then interpolate the fourth grid on to the fifth to get initiate values and forecast the fabled boundary by our formula, calculate u value at all points on the 5th grid by normal domain decomposition method with few iterations. On the fifth grid there is necessary for data exchange between two sub-domains to smooth boundary forecast error. We obtain u5(0.5) =3.641841.Similarly we forecast the function value v6, 3 = 3.644253 at fabled boundary x=0.5 on the sixth grid, solving two sub-domain relevant independent boundary condition problem etc until error bounds condition=0.0001 between two subsequent iterations has been satisfied. In this example, we obtain the satisfied numerical value of u on 8th grid.
General speaking we calculate unknown u by normal parallel computing on decomposed sub-domain with fabled boundary data exchange on all odd number grids, and solving relevant independent boundary condition problems with forecast fabled boundary values for all even number grids. By this way we reduce nearly half communication costs.
Denote number of computers as N. We decompose domain [ 0, 1] into sub-domain [xk-1,xk], k=1,2,...,N. Let one computer only calculate function value of u on one sub-domain. Table 1 shows the parallel calculate efficiency data of model 1 and model 3.When N>2,the efficiency of model 3 is 12 higher than that one of model 1.
Table 1. The parallel calculate efficiency
PRIVATE1234Model 110092.1984.3181.13Model 392.1996.3193.8291.42
Example 2. Two dimension no-line boundary problem
uxx+uyy-u2=-50x(x+y)-625(x+y-x2-y2)2/9 (x,y)"=[0,1][0,1]
u(0,y)=u(1,y)=u(x,0)=u(x,1)=0
We decompose domain into sub-domain
i={(x,y)%(i-1)/Nd"xd"i/N,0d"yd"1,i=1,2,...,N,}
The fabled boundary is
in ={(x,y)%x=i/N,0<y<1,i=1,2,...,N,}
Let one computer only calculate value of function u on one sub-domain. Step of 1st grid is h=1/N. The step of 2nd grid is h = 0.5/N.The step of 3rd grid is h=0.25/N etc. Table 2 shows the parallel calculate efficiency data of model1 and model 3. When N>2, the efficiency of model 3 is 12.2 higher than the one of model 1.
Table 2. The parallel calculate efficiency
PRIVATE1234Model 110093.0385.2682.72Model 310097.3194.4192.03
5. Further Improvement
In the proposed algorithm we transform a boundary problem into several relevant independent sub-domain boundary problems on all even number grid. Therefore it is nature and efficient to solve those boundary problems with the V-cycle multi grid method (MGM) without any extra communication between sub-domains. We name it as modified parallel full multi grid method with fabled boundary forecast.
6.Conclusion
Model 1 is a linear forecast method. Model 2 is a polynomial forecast method, but model 3 is a polynomial maximal forecast method. The model 3 may decrease the amount of communication between sub-domains. The examples of one and two-dimension problems show that our fabled boundary initial value forecast method is efficient in parallel multi grid computing.
Reference
[1] Guo Qingping. Parallel computing using Domain Decomposition for Cyclical Temperatures in Ceramic/Metal Composites,EuroPVM/MPI98, Liverpool UK, 1998.
[2] Xu Zhengquan. Domain decomposition method of multi grid distributed computing, Journal of Numerical and Compution.Vol.1.1996.p1-5.
[3] Louis. A. Hageman & David M. Young. Applied Iterative Methods. New York. 1982 p50-197.
[4] H. Hoppe and H. Mhlenbein, Parallel adaptive full-multigrid methods on message-based multiprocessors, Parallel Computing, No 3, North-Holland. 1986 p269-287
p}~:;cdez{|}R_K
y
$&(VXj˺˺˺ꑋCJOJo(CJOJo(
H*OJo(OJQJ5CJOJQJjNUjU0JCJOJQJjU jU6CJOJQJ6CJH*OJQJCJH*OJQJCJOJQJ5CJOJQJB*OJQJ6:pq:ROI
K
y
T.h@&$h$h$h$h@&:pq:ROI
K
y
T.n4t2-b7EH,0
BB p v V!!!!N"#$$%A&P'"*H++"-#-1-\-.0..78F:::::::
bjlz|~\^`~02468:HJLZ^<>@vx~fCJOJCJH*OJQJCJH*OJo(CJH*OJo(CJH*OJQJOJOJo(CJOJo(CJOJQJ
H*OJo(Lfjnt
,.26pt &468FHdj"$JKsw5CJOJQJCJOJCJOJQJCJOJo(CJH*OJQJWn4t2-b7EH8h@&@&h#%(,-/24=?
04:DFLPXbdjntBLPRTZ^dnrx()-5CJOJCJOJo(6CJOJQJ56CJOJQJCJH*OJQJCJOJQJR59<=ABLMQRYZ[^abqtxz{}
!(),/14VY[\]_`behjkmptux{}ŽŽŽͽͽŽͽͽͽͽŽŽͽͽͽͽͽͽCJH*OJQJ6CJOJQJCJOJQJ56CJOJQJCJOJCJH*OJo(CJOJQJCJOJo(CJH*OJo(JV^djvxz|~
$,BLNP $0<RTV߽56CJOJQJ5CJOJQJCJH*OJQJ6CJOJQJH*OJQJCJOJo(CJOJCJOJQJCJH*OJQJJH,0
BB p v V!!!!N"#$$%A&P'"*$8h@&@&h*,06BDHXZ`fjpD P V ^ d p t v V!\!^!`!f!n!r!t!v!x!z!|!~!!!!!!!!!N""""##$$$$?%@%OJo(OJQJ56CJOJQJCJOJCJH*OJQJ6CJOJQJH*OJQJCJOJQJCJOJo(M@%v%w%%%&&=&>&Y&[&Z'[']'^'a'b'd'e'((((
(((((((((H(J(X(Z(h(j(((((((((((()))L)R)^)d)h)n)))))))2*6*8*:*>*@*B*D*F*H*J***R+T+V+X+Z+^+`+b+d+f+j+OJQJOJo(CJOJo(H*OJQJCJH*OJQJCJOJQJW"*H++"-#-1-\-.0..78F::::::::|E$$TlrL~$$$@&h$j+l+n+p+r+v+|+~+++#-1-<-f-g-....(/*/T/V/X/t/v/x/11I2K2X2Z222445!566&9'9*9,9-9::F:::::::::::::::jCJOJQJUCJOJQJjCJOJQJUCJOJQJOJQJOJo(CJH*OJQJH*OJQJ5CJOJQJ5OJQJCJOJQJCJOJo(H*OJQJ>::::::;;;;*;6;B;D;H;;&<b<<=8==@O@Z@\@^@`@b@c@k@o@u@{@@@@@@@@@@@FBGBTBCCC`DDBEE
5::::::::::;;;;;(;*;4;6;@;D;H;^;;;;;;;;;;;;;<<<<<<<<<<<<<<<<<<<8=:=@=N=P=??@O@P@W@X@Y@Z@j CJOJQJUCJOJQJjCJOJQJUCJOJQJOJo(CJOJo(H*OJQJH*OJQJ5CJOJCJOJQJ5CJOJQJC:::::;;;;*;6;B;D;pE$$TlrL~E$$Tl8rL~$$D;H;;&<b<<=8==@O@Z@\@^@`@b@c@k@o@u@|E$$Tl\r4
$h@&$Z@[@\@]@^@_@`@a@c@h@i@j@k@n@o@t@u@z@{@@@@@@@@@@@@@@@@GBTBCCcDdDDDEOJQJCJOJQJCJOJQJOJQJCJOJo(5CJOJ5CJOJQJ5CJOJQJo(5CJOJo(*u@{@@@@@@@@@@@FBGBTBCCC`DDBE|8@&E$$Tl\r4
$BEE$8+0P. A!"#$n%DyKyK:mailto:qpguo@public.wh.hb.cnDyKyK2mailto:guo@dcs.qmw.ac.ukDyKyK6mailto:paker@dcs.qmw.ac.ukDlOm|mmLLffffffffmLLffffff ffm
LLffff
ffffDlmFmdmggggggmggggggmgggggg+
[8@8cke1$ddH$7$8$CJmH nHA@؞k=W[SO::Definition Term
>>Definition Listh(O(
Definition6**H1$@&5CJ0KH$&&H2$@&5CJ$&&H3$@&5CJ""H4$@&5&&H5$@&5CJ&&H6$@&5CJ..Address
600
Blockquote
hhOCITE6$O$CODECJOJQJX@:_6U@~c>*B*&V@&]v~c>*B*0O0Keyboard5CJOJQJffPreformatted0
#~=z9!v%CJOJQJbObz-Bottom of Form!$1$H$7$8$$d<CJOJQJmH nH\O\
z-Top of Form"$1$H$7$8$&d<CJOJQJmH nH$O1$SampleOJQJW@Ap50OQ0
TypewriterCJOJQJ$Oa$Variable6,Oq,HTML Markup<B*"O"Comment<"Y@"ech~gV)-D O lʑh*$\/!
)&-\/ jf5@%j+:Z@E.1245689;=@H"*:D;u@BEE/37:>?AB:E0<:dz|\/XXX~F08@0( {{
B
S ?
+
,
S
T
U
Y
\
d
e
j
k
l
23467CDE`ab\^I
K
u
v
KN\_
/1356JLTUsu_a^_`acjk[]DEHJ!#VW\]^_oqvwxyz{
STijyz##x&y&^'a'x'{'|'~'''''''''''''''''((((( (\)])----m.t.....^/:;=
&)afu
!)deJNjo%'34y}_a~Rlmq LV[]s #,6(-!!"#%%&&'&'N'''''''''(5(7(0)})++C-P-----c.i.j......^/Guo QingpingvC:\Guo\papers\A Fabled Boundary Condition Forecast Algorithm in Multi Grid Domain Decomposition Parallel Computing.docGuo QingpingvC:\Guo\papers\A Fabled Boundary Condition Forecast Algorithm in Multi Grid Domain Decomposition Parallel Computing.docGuo QingpingC:\Guo\papers\paper3.docGuo Qingping"C:\WINDOWS\TEMP\ ꁨRb`
Y OX[paper3.asdGuo Qingping"C:\WINDOWS\TEMP\ ꁨRb`
Y OX[paper3.asdGuo QingpingC:\Guo\papers\paper3.docGuo Qingping"C:\WINDOWS\TEMP\ ꁨRb`
Y OX[paper3.asdGuo QingpingC:\Guo\papers\paper3.docGuo QingpingC:\Guo\papers\paper3.docGuo QingpingC:\Guo\papers\paper3.doc@99w99$
VVV#$x&x'x(x)\/`@`````,@``4@``` `"`H@`(`*`X@`.``@`6`p@`:`<`>`@GTimes New Roman5Symbol3&Arial-[SO-ўSOWCenturyTimes New Roman?&
Arial Black?5 Courier New Ah$)\)& H'S~&R!xx>d0>-ff1C:\PROGRAM FILES\MICROSOFT OFFICE\OFFICE\html.dotdA Fabled Boundary Condition Forecast Algorithm in Multi Grid Domain Decomposition Parallel ComputingGuo QingpingGuo QingpingOh+'0$0D \h
eA Fabled Boundary Condition Forecast Algorithm in Multi Grid Domain Decomposition Parallel Computing Fa
Guo Qingpingdaruo html.doting
Guo Qingpingdar9o Microsoft Word 8.0o@
@\@PB'՜.+,D՜.+,\
px
=WTUS0eA Fabled Boundary Condition Forecast Algorithm in Multi Grid Domain Decomposition Parallel ComputingTitle@RZr
_PID_GUID_PID_HLINKSHTMLDocumentEncoding
GeneratorAN{A6D43BCF-4F15-11D2-B9DA-C05F0479ED4A}AH>mailto:paker@dcs.qmw.ac.ukg_mailto:guo@dcs.qmw.ac.uk-mailto:qpguo@public.wh.hb.cn
windows-1252ingMicrosoft Word 97it
!"#$%&'()*+,-./0123456789:;<=>?@ABCEFGHIJKMNOPQRSTUVWXYZ\]^_`abdefghijmnzqrstuvwxy{Root EntryII
F%&5BpDataINP_`0_`_`^`^`^`@^`
_`D1Table`j`pj`(j`i`HI~
` LWordDocument
`I``
`
`
`P
`IE-SummaryInformation([0
`DocumentSummaryInformationI8$I 0cMacrosyI<@/4B4B
@@VBA,@dI1hI@ 74B j4BThisDocument
_VBA_PROJECTdir@PROJECTwm
L)
!"#$%&'()*+,-./0123456789:;<=>?ABCDEFGHIJKNOPQRUE.wQ4gH?==B+.x,,9(S"SS"<$1HTML.ThisDocument0($`$$$0h@MExAttribute VB_Name = "ThisDocument"
Bas1HTML.CreatablA\FalsePredeclaDIdvTru
"E xposeTemplateDeriv$Cust0omizca^ *\G{000204EF-0000-0000-C000-000000000046}#3.0#9#C:\PROGRAM FILES\COMMON FILES\MICROSOFT SHARED\VBA\VBA332.DLL#Visual Basic For Applications*\G{00020905-0000-0000-C000-000000000046}#8.0#0#C:\Program Files\Microsoft Office\Office\MSWORD8.OLB#Microsoft Word 8.0 Object Library*\G{00020430-0000-0000-C000-000000000046}#2.0#0#C:\WINDOWS\SYSTEM\STDOLE2.TLB#OLE Automation*\G{49229F2E-4BE7-11D2-B9DA-851E82A73745}#2.0#0#C:\WINDOWS\SYSTEM\MSForms.TWD#Microsoft Forms 2.0 Object Library*\G{2EF2FC46-5177-11D2-B9DA-F01885346748}#2.0#0#C:\WINDOWS\TEMP\Word8.0\MSForms.EXD#Microsoft Forms 2.0 Object Library.E
.`Mh*\CC:\PROGRAM FILES\MICROSOFT OFFICE\OFFICE\html.dotn*\C..\..\PROGRAM FILES\MICROSOFT OFFICE\OFFICE\html.dot!3*\G{2DF8D04C-5BFA-101B-BDE5-00AA0044DE52}#2.0#0#C:\PROGRAM FILES\MICROSOFT OFFICE\OFFICE\MSO97.DLL#Microsoft Office 8.0 Object Library6,ThisDocument
736061c1c*D, C.wQ4gH`$&Wordk`VBA`Win16~`Win32`Mac`paper3W`stdole``MSFormsC`ThisDocument<` _Evaluate`HTML``Officeu`Project-`Documentj`mHTMLInsertTextArea`
HTMLTextArea1?``0* pHdProjectQ(@=
l 6J<
rstdole>stdoleP
f%\*\G{00020430-C
0046}#2.0#0#C:\WINDOWS\SYSTEM\STDOLE2.TLB# Automation^mMSFo@rms> MSFErm@s/z pF49229F2E-4BE7-11D2-B9DA-851E82A73745F3.TWD#Microsoft =" ` Ob Library9P0vP2EF2FC46-517 PF01885346748PJP\Wor d8.0\)EX).E
.`M
BHTML>'HTXMLY64B,ClPROGRAM FILES\MICROSOFT OFFICE\html.dot7
..\@!3OPfficOfPicG{2DF8D04C-5BFA-101B-BDE5AA42S#MSO97.DLL# _ERB,ThisDocumentN2@1Th@6sD@cuQenH15,","
,*""+ThisDocumentThisDocumentID="{2EF2FC49-5177-11D2-B9DA-F01885346748}"
Document=ThisDocument/&H00000000
Name="Project"
HelpContextID="0"
CMG="5A58937BE97FE97FE97FE97F"
DPB="B4B67D258D7E8E7E8E7E"
GC="0E0CC78F7BB3D4PROJECTMkPROJECTlkSCompObjTfB4D4B42B"
[Host Extender Info]
&H00000001={3832D640-CF90-11CF-8E43-00A0C911005A};VBE;&H00000000
&H00000002={000209F2-0000-0000-C000-000000000046};Word8.0;&H00000000
$U\g
FMicrosoft Word ĵ
MSWordDocWord.Document.89q