Sobre la paralelización de problemas elípticos

Bol. Soc. Esp. Ma . Apl. no31(2005), 31–52 Sob e la pa alelizaci´on de p oblemas el´ıp icos M. C. Calzada1, I. I. Alba eal2, J. L. C uz1, E. Fe n´ andez-Ca a2, J. R. Galo1, M. Ma ´ ın1 1Dp o. de In o m´a ica y An´alisis Num´e ico, Uni e sidad de C´o doba, Campus de Rabanales, Ed. C2-3, E-14071 C´o doba 2Dp o. de Ecuaciones Di e enciales y An´alisis Num´e ico, Uni e sidad de Se illa, Ap do. 1106, 41080 Se illa [email p o ec ed], [email p o ec ed], [email p o ec ed], [email p o ec ed], [email p o ec ed], [email p o ec ed] Resumen En es e abajo se ecogen dos de los p oblemas que apa ecen a la ho a de esol e num´e icamen e las ecuaciones deNa ie -S okes. La disc e izaci´on en la a iable empo al en dichas ecuaciones nos conduce, en cada e apa de iempo, a un p oblema de Bu ge s y un p oblema de S okes gene alizado, en las a iables espaciales. La aplicaci´on de un m´e odo de pun o ijo y un m´e odo de ipo g adien e conjugado, espec i amen e, nos lle a a la esoluci´on de un ele ado n´ume o de p oblemas de ipo Helmhol z. As´ı, en una p ime a pa e, eco damos un algo i mo pa alelo que esuel e num´e icamen e la ecuaci´on de Helmhol z. Po o o lado, la u ilizaci´on de di e encias ini as cen adas sob e un mismo mallado egula pa a la elocidad y la p esi´on en la esoluci´on del p oblema de S okes puede gene a soluciones oscilan es, en pa icula p esiones esp´u eas. En una segunda pa e, po an o, se p esen a un esquema de disc e izaci´on pa a el p oblema de S okes, demos ´andose median e un an´alisis asin ´o ico del e o que ´es e egula iza la soluci´on1. Fecha de ecepci´on: 31/01/05 1Una e si´on p e ia de es e abajo apa ece ´a en las Ac as del I Wo kshop sob e “Recien es A anaces en el An´alisis y Con ol de Ecuaciones Di e enciales No Lineales”, celeb ado en C´o doba en eb e o de 2004. 31 32 M. C. Calzada y o os 1 In oducci´on En la esoluci´on de muchos p oblemas de g an complejidad, apa ecen de o ma ecuen e ecuaciones de ipo Helmhol z: αu −β∆u= en Ω ⊂IRN,(1) siendo α≥0, β > 0, una unci´on conocida y Ω un dominio aco ado bi o idimensional. La ecuaci´on se comple a con condiciones de con o no, que pueden se de ipo Di ichle , u=gsob e Γ = ∂Ω,(2) de ipo Neumann, Fou ie o una mezcla de ambas. Aunque ´es e es uno de los p oblemas m´as conocidos y es udiados, es cla o que una peque˜na ganancia en el iempo de esoluci´on de (1) puede en la p ´ac ica supone una g an mejo a en el a amien o de p oblemas m´as complejos. Pensemos en las ecuaciones de Na ie -S okes, pa a las cuales hemos desa ollado a ios algo i mos donde es e hecho se pone de mani ies o ( ´ease po ejempo [3, 4]). El m´e odo que se p esen a sigue la idea de los denominados m´e odos ADI (Al e na ing Di ec ions Implici me hods). Es os m´e odos ue on o mulados inicialmen e po Peaceman y Rach o d [15] en el caso bidimensional y po Douglas y Rach o d [7] en el caso idimensional y, pos e io men e, ue on gene alizados al caso N-dimensional po Douglas y Gunn [6]. Pa a desc ibi la idea de es os m´e odos, conside emos po ejemplo el p oblema de Helmhol z (1)–(2). Conside emos ijados una descomposici´on del ope ado L = αI−β∆ en la o ma L = L1+ L2con Ln=α 2I−β∂2 ∂x2 n (n= 1,2) (3) y un esquema en di e encias ini as cen adas con paso de disc e izaci´on h en las dos di ecciones espaciales. Un m´e odo de paso accionado (de ipo de Peaceman-Rach o d) pa a es a descomposici´on es un m´e odo i e a i o que comienza con U0a bi a io y, pa a m≥0, calcula Um+1 en dos pasos. As´ı, pa a Umdado, p ime o se ob iene Um+1 2como soluci´on de (I+τA1)Um+1 2=τ + (I−τA2)Um(4) y en segundo luga se esuel e (I+τA2)Um+1 =τ + (I−τA1)Um+1 2.(5) Aqu´ı, τ > 0,yAnes la ma iz co espondien e a la disc e izaci´on del ope a- do Ln2. As´ı, en el p ime paso se esuel e un p oblema disc e o co espondien e al ope ado α 2I−β∂2 ∂x2 1 , 2Po simplicidad, hemos deno ado de nue o la unci´on disc e izada. Pa alelizaci´on y p oblemas ell´ıp icos 33 es deci , un p oblema en la di ecci´on x1. An´alogamen e, en el segundo paso se esuel e un p oblema en la di ecci´on x2. Es o es lo que mo i a el nomb e de m´e odo de di ecciones al e nadas. Con una adecuada o denaci´on de los nodos del mallado, se consigue que las ma ices I+τAn(n= 1,2) sean diagonales po bloques, siendo cada bloque una ma iz idiagonal. Es a idea se puede aplica , en gene al, a la ho a de esol e un sis ema algeb aico Au = (6) esul an e (po ejemplo) de la disc e izaci´on de un p oblema el´ıp ico, siemp e que la ma iz Ase pueda descompone en la o ma3 A= p X n=1 An,(7) siendo las ma ices An(1 ≤n≤p) m´as ´aciles de in e i que la p opia A. Es a gene alizaci´on da luga a los llamados m´e odos de descomposici´on o m´e odos secuenciales de paso accionado ( ´ease [13]). En es e caso, pa a m≥0, conocido Um,el c´alculo de Um+1 se ealiza esol iendo los siguien es sis emas: Um+1 p−Um τm +A1³Um+1 p−Um´=−αÃp X n=1 AnUm− !, (8) Um+n p−Um+n−1 p τm +An³Um+n p−Um´= 0, n = 2,...,p siendo α > 0 y {τm}una sucesi´on de pa ´ame os eales. Como acabamos de e , los m´e odos de paso accionado (8) son algo i mos i e a i os secuenciales, en los que cada i e aci´on se subdi ide en ppasos que se ealizan sucesi amen e seg´un el esquema: Um→Um+1 p→Um+2 p→ · · · → Um+p−1 p→Um+1.(9) Es deci , has a que no se calcula Um+i pno se puede calcula Um+i+1 p. Po ello, la pa alelizaci´on de es os algo i mos s´olo puede lle a se a cabo al m´as bajo ni el, a la ho a de esol e los sis emas ( e po ejemplo [18] y [11]). Noso os abo damos la esoluci´on de los p oblemas de Helmhol z gene alizando y ampliando a dominios a bi a ios un m´e odo in oducido po Lu y o os [12] o mulado pa a p oblemas con condiciones de ipo Di ichle y pa a dominios que esul an de la uni´on de ec ´angulos. Nues o obje i o global es desa olla un esquema num´e ico que pe mi a la pa alelizaci´on al ni el de las a iables espaciales. Es e m´e odo, que denominamos m´e odo impl´ıci o de di ecciones simul ´aneas oSDI (Simul aneous Di ec ions Implici me hod), descompone 3En gene al, pno iene po qu´e coincidi con la dimensi´on Nen la que se abaje. 34 M. C. Calzada y o os el p oblema o iginal, independien emen e de la dimensi´on espacial del dominio en el que es ´e o mulado, en un conjun o de p oblemas unidimensionales. Se sus i uye as´ı un p oblema en de i adas pa ciales po una amilia de p oblemas di e enciales o dina ios odos ellos con la misma es uc u a y po an o con las mismas di icul ades num´e icas, independien emen e de la dimensi´on espacial en la que se abaje. Adem´as, los p oblemas esul an es son independien es en e s´ı y pueden esol e se en pa alelo. El m´e odo SDI que hemos desa ollado es aplicable a dominios Ω a bi a ios. En [17] se aplica en el caso bidimensional, e ec u´andose p e iamen e una “ ec i icaci´on”del abie o Ω, de al mane a que se ap oxima el dominio o iginal po una uni´on de ec ´angulos. En nues o caso no se e ec ´ua es a ec i icaci´on y el mallado se cons uye a pa i de una e ´ıcula o ogonal de pa ici´on a bi a ia, admi iendo odo ipo de condiciones de con o no. Pa a ello se ha desa ollado un mallado ( e [9]), an o en el caso 2D como en el 3D, que pe mi e dispone de una es uc u a de da os que con ibuye a una mayo e iciencia del m´e odo. El m´e odo es econ´omico en sus necesidades de almacenamien o, po lo que es compa ible con p oblemas de g an alla. Adem´as, en [9] se demues a su ca ´ac e “smoo he ”, que explica que se adap e muy bien al uso de ´ecnicas mul ig id pa a acele a la con e gencia sea cual sea la geome ´ıa del dominio conside ado. Aqu´ı solo expond emos el algo i mo pa alelo p opues o cuando la ecuaci´on de Helmhol z se comple a con condiciones de con o no de ipo Di ichle . La conside aci´on de o o ipo de condiciones de con o no ompe en gene al, con on e as no necesa iamen e pa alelas a los ejes coo denados, la independencia po di ecciones al se condiciones ne amen e in e espaciales. En [9] se encuen a desa ollada una ´ecnica ´alida pa a condiciones de o o ipo. ´ Es a consis e en un m´e odo i e a i o que inicialmen e necesi a la esoluci´on de una sucesi´on de p oblemas con condiciones de Di ichle y pos e io men e se educe a la aplicaci´on del m´e odo SDI a un ´unico p oblema con condiciones de Di ichle dependien es de la i e aci´on. Recien emen e se ha demos ado la con e gencia de es e m´e odo. Hay que des aca que la esoluci´on de los p oblemas de Helmhol z con condiciones de Neumann iene in e ´es no s´olo po s´ı misma, sino ambi´en cuando se buscan p econdicionado es que pe mi en acele a la con e gencia del g adien e conjugado al aplica ´es e, po ejemplo, a la esoluci´on de un p oblema de S okes. Como es de p e ee , dispone de un m´e odo pa alelo e icien e pa a la esoluci´on de los p oblemas de Helmhol z conduce a una no able mejo a en la esoluci´on de p oblemas m´as complejos, como puede se el caso de los p oblemas de S okes o Na ie -S okes. En nues o caso, pa a esol e el p oblema de S okes, e o mulamos ´es e como un p oblema de m´ınimos al que aplicamos un m´e oddo i e a i o de ipo g adien e conjugado p opues o en [10] y [5]. Es e m´e odo conduce a la esoluci´on de un g an n´ume o de p oblemas de Helmhol z y/o Poisson. Po lo an o, disponemos de una mane a de esol e un p oblema de S okes N-dimensional exclusi amen e a pa i de p oblemas uni- dimensionales independien es (p oblemas di e enciales o dina ios), con igual esquema de esoluci´on y di icul ad num´e ica independien emen e de la dimensi´on del p oblema o iginal. Se obse a en onces que la pa alelizaci´on del m´e odo es posible a es ni eles, espec i amen e co espondien es a la Pa alelizaci´on y p oblemas ell´ıp icos 35 descomposici´on de los p oblemas ec o iales po componen es y a los dos ni eles de pa alelizaci´on impl´ıci os al m´e odo SDI. En [5], se esuel en los p oblemas de Helmhol z y Poisson disc e izando po elemen os ini os, us´andose un mallado el doble de ino pa a las elocidades que pa a la p esi´on, al obje o de e i ica la condici´on in -sup. En nues o caso, disc e izamos los p oblemas unidimensionales esul an es u ilizando di e encias ini as y el mismo mallado pa a odas las inc´ogni as. Es o hace que no se e i ique la condici´on in - sup, lo que p o oca la apa ici´on de p esiones esp´u eas, que disminuyen la p ecisi´on de la ap oximaci´on de la p esi´on calculada sin que la ap oximaci´on de la elocidad enga que e se a ec ada. Las p esiones esp´u eas se mani ies an en la ep esen aci´on g ´a ica de las isoba as como l´ıneas de con o no con oscilaciones. En la p ´ac ica, seg´un la disc e izaci´on que se e ec ´ue, el ipo de “ es ” conside ado y el ca ´ac e de su soluci´on, puede que expl´ıci amen e no se obse e la p esencia de las mismas. En la secci´on 3.2 e ec ua emos un an´alisis de es a di icul ad in oduciendo el desa ollo asin ´o ico del e o come ido y siguiendo la me odolog´ıa p opues a po We on [19] en su es udio del m´e odo de p oyecci´on. We on explica la causa de la apa ici´on de p esiones esp´u eas en base a la exis encia de “e o es al e nan es” unidi eccionales. Aqu´ı ealiza emos un an´alisis simila , con emplando la exis encia de es os e o es pe o con un ca ´ac e mul idi eccional. Iden i ica emos los modos esp´u eos y, de es a mane a, pod emos busca el il ado adecuado pa a las p esiones que haga que las oscilaciones se eduzcan. Es e il ado ( e [9]) se ealiza siguiendo cada una de las di ecciones espaciales, man eniendo el esquema concep ual es ablecido de educi odo el a amien o a p oblemas unidimensionales. 2 Un esquema pa alelo pa a la ecuaci´on de Helmhol z Como acabamos de e , los m´e odos de paso accionado (8) son algo i mos i e a i os secuenciales, en los que cada i e aci´on se subdi ide en psube apas que se ealizan sucesi amen e. En [12], Lu e al. p oponen un esquema de descomposici´on pa a la esoluci´on de (6) en el que los pasos accionados son independien es en e s´ı. A pa i de una descomposici´on de la ma iz Adada po (7) y de un pa ´ame o τ > 0, el paso de UmaUm+1 se ealiza calculando Um+1,n (1 ≤n≤p) a pa i de (I+τAn)Um+1,n = I−τ p X k=1,k6=n Ak Um+τ , n = 1,...,p, (10) y haciendo, pos e io men e, Um+1 =ω p p X n=1 Um+1,n + (1 −ω)Um,(11) donde ωes un pa ´ame o dado. Se a a de un m´e odo de descomposici´on en el cual los ppasos accionados pueden esol e se simul ´aneamen e y la 36 M. C. Calzada y o os pa alelizaci´on se ealiza a un ni el m´as al o, siendo es o mucho m´as in e esan e y e ec i o. A es e m´e odo lo denomina emos m´e odo pa alelo de paso accionado oPFS (Pa allel F ac ional S ep me hod). Esquem´a icamen e puede ep esen a se como sigue: Um Um+1,1 % · · · & & · · · % Um+1,p Um+1 (12) Cuando se aplica es e m´e odo al p oblema de Helmhol z-Di ichle N dimensional ½Lu=αu −β∆u= en Ω ⊂IRN, u=gsob e ∂Ω(13) conside ando la siguien e descomposici´on del ope ado L = N X n=1 Ln= N X n=1 µα NI−∂2 ∂x2 n¶, se iene que, en cada paso (10) se esuel en Np oblemas independien es co es- pondien e cada uno de ellos al ope ado α NI−β∂2 ∂x2 n , al igual que suced´ıa con el m´e odo ADI pe o, en es e caso, los c´alculos se hacen en odas las di ecciones simul ´aneamen e. De aqu´ı que a es e m´e odo lo denominemos m´e odo impl´ıci o de di ecciones simul ´aneas oSDI (Simul aneous Di ec ions Implici me hod)4. Como ya indicamos en el m´e odo ADI, la descomposici´on elegida es con enien e, ya que las ma ices esul an es I+τAnson m´as ´aciles de in e i que la ma iz Adel p oblema o iginal. En es e caso, la ob enci´on de cada Um+1,n puede e ec ua se esol iendo en pa alelo ssis emas independien es con sdel o den de h−1, lo que se co esponde con la esoluci´on simul ´anea en cada una de las l´ıneas del mallado en la di ecci´on xn. Se ienen po an o dos ni eles de pa alelismo que conducen a N·sposibles p ocesos simul ´aneos y, dado que ses un n´ume o ele ado al se en la p ´ac ica h peque˜no, ob enemos un algo i mo con un al o ´ındice de pa alelizaci´on. Adem´as, los p oblemas a esol e pa a la ob enci´on de las Um+1,n ienen odos la misma es uc u a y p esen an id´en icas di icul ades num´e icas. Los m´e odos pa alelos de paso accionado en gene al y los SDI en pa icula , seg´un la desc ipci´on (10)–(11) e ec uada, dependen de dos pa ´ame os (que pueden a ia en cada i e aci´on en el caso no es aciona io); el pa ´ame o τdenominado pa ´ame o de e oluci´on y el pa ´ame o ω, conocido como pa ´ame o de coo dinaci´on. En [9] se encuen a un es udio exhaus i o de los alo es de es os pa ´ame os, 4En gene al, llama emos m´e odos SDI a los m´e odos pa alelos de paso accionado aplicados a p oblemas en los que en cada Lnin e engan de i adas en una ´unica di ecci´on. Pa alelizaci´on y p oblemas ell´ıp icos 37 que hacen que el m´e odo sea con e gen e y adem´as su elocidad de con e gencia sea lo mayo posible. En [1] apa ece un es udio del e o pa a un caso pa icula del algo i mo o almen e disc e izado. 2.1 Resoluci´on e ec i a En es a secci´on e ec uamos un an´alisis de los elemen os necesa ios pa a la esoluci´on e ec i a de los p oblemas de ipo Helmho z-Di ichle . Mallado Como es na u al, pa a la esoluci´on del p oblema (13) e ec ua emos una disc e izaci´on espacial. A pa i de una e ´ıcula ca esiana R(∆), ob enemos un mallado de Di ichle M(∆) = M1(∆) ∪... ∪MN(∆), de nodos N(∆) = NI(∆) ∪NF(∆),donde NI(∆) con iene los nodos in e io es, NF(∆) con iene los nodos on e a y Mn(∆) = Mn [ j=1   en(n,j) [ l=1 Ij,l n ,1≤n≤N, siendo Ij,l n= ((al),(bl)) un segmen o de IRNen la di ecci´on espacial enisomo o al in e alo de IR (al, bl).En las Figu as 1 y 2, apa ece un ejemplo de M(∆) pa a un dominio bidimensional y en la Figu a 3 un dominio idimensional an´alogo. Figu a 1: Un mallado M(∆) = M1(∆)∪M2(∆),pa a un dominio bidimensional. 38 M. C. Calzada y o os Figu a 2: Dos segmen os in eg ables en la di ecci´on e1. Figu a 3: Algunos segmen os in eg ables en un dominio 3D. De alle del algo i mo ∗E apa de esoluci´on La e apa de esoluci´on del algo i mo (10), aplicada al p oblema (13), se co esponde con Nsubp oblemas del ipo ((I + τLn)um+1,n =³I−τPN k=1,k6=nLk´um+τ en Ω ⊂IRN, um+1,n =gsob e Γ = ∂Ω,(14) donde Ln=α NI−∂2 ∂x2 n ,1≤n≤Nyumes conocida. Pa a el mallado M(∆), como Lnes unidimensional, pa a cada uno de los p oblemas (14) se iene el co espondien e p oblema disc e o ((I + τδn)Um+1,n =³I−τPN k=1,k6=nδk´Um+τ en Mn(∆), Um+1,n =gen NF(∆),(15) donde δnes el ope ado disc e o co espondien e a Ln.Dado que las condiciones de con o no son de ipo Di ichle , (15) es un conjun o de p oblemas Pa alelizaci´on y p oblemas ell´ıp icos 39 independien es5 ((I+τδn)Um+1,n =³I−τPN k=1,k6=nδk´Um+τ en Ij,l n= ((al),(bl)) , Um+1,n ((al)) = g((al)) , Um+1,n((bl)) = g((bl)), (16) de inidos en cada uno de los segmen os in eg ables Ij,l nque cons i uyen Mn(∆). A su ez, cada p oblema (16) es un p oblema disc e o co espondien e a un p oblema de con o no o dina io (unidimensional) en la a iable xndel ipo (³1 + τα N´ −τβ 00 =˜ en (al, bl), (al) = a, (bl) = b,(17) donde 00 es la segunda de i ada en la a iable xny˜ es un segundo miemb o gen´e ico. As´ı pues, Um+1,n en (16) queda de e minada median e la esoluci´on de, al menos, Mnp oblemas de con o no o dina ios del ipo (17), cada uno de ellos en el co espondien e in e alo de IR,isomo o al segmen o in eg able Ij,l n∈Mn(∆). Haciendo n= 1, ..., N, emos que (16) es una amilia de, al menos, M= N X n=1 Mnp oblemas del ipo (17). Todos ellos poseen la misma es uc u a y, po an o, p esen an igual di icul ad num´e ica. Adem´as, son independien es en e s´ı po lo que pueden e´o icamen e esol e se de o ma simul ´anea. Hagamos no a que Mes un n´ume o ela i amen e g ande, ya que depende del n´ume o de pun os de las pa iciones conside adas en cada di ecci´on espacial. As´ı pues, se iene un al o ni el de pa alelismo posible. ∗E apa de coo dinaci´on De e minadas las Um+1,n, con n= 1, ..., N, en los nodos N(∆) del mallado, la e apa de coo dinaci´on del algo i mo (11) es ambi´en un p oceso pa alelizable ya que el c´alculo Um+1(P) = ω N N X n=1 Um+1,n(P) + (1 −ω)Um(P) (18) se puede ealiza de o ma simul ´anea pa a cada P∈N(∆).Es a e apa de coo dinaci´on es ealmen e la que nos obliga a u iliza una e ´ıcula ca esiana como base pa a la cons ucci´on del mallado. ∗“Tes ” de pa ada El “ es ” de pa ada conside ado en el p oceso i e a i o es: kUm−Um+1k∞= m´ax x∈N(∆) |Um(x)−Um+1(x)|< ε, donde εes una ole ancia dada. 5La ma iz del p oblema disc e o es una ma iz diagonal po bloques. 46 M. C. Calzada y o os donde las bu(s)=u(sp)−u(si) 2, u(s)=u(sp)+u(si) 2 son egula es e independien es de h. Decimos que es e ipo de desa ollo es al e nan e. Es o da una explicaci´on p ecisa de qu´e es lo que ocu e cuando se pie de la egula idad disc e a. As´ı pues, apa ece una soluci´on global que oscila al cambia de submallado ya que el desa ollo asin ´o ico del e o con iene ´e minos al e nan es que, en caso de que p edominen en e a los ´e minos egula es, causan la p´e dida de p ecisi´on, ´ease [19]. No emos que el desacoplamien o es debido a la disc e izaci´on elegida del ope ado y el o den en el que apa ece el ´e mino al e nan e es el o den en el que di ie en las ap oximaciones on e a conside adas en cada submallado. Los ipos de desa ollo asin ´o ico del e o indicados pueden ex ende se a cualquie p oblema de con o no bi o idimensional. Como conclusi´on, se iene que median e es e an´alisis podemos a e igua si un esquema de disc e izaci´on es egula izan e y, en el caso de ene un desa ollo al e nan e, se puede de e mina , median e una adecuada ponde aci´on de los alo es de nues a inc´ogni a en un nodo y sus adyacen es, un pa ´on de il ado que pe mi a amino a la p´e dida de p ecisi´on indicada. En [19] se e ec ´ua un an´alisis del esquema de disc e izaci´on de Cho in [2] aplicado, en es e caso, al p oblema de S okes. Se demues a que el e o es de segundo o den pa a la elocidad (con e o es de ipo al e nan e de e ce o den) y s´olo de p ime o den en la p esi´on debido a la p esencia de e o es al e nan es, que p edominan sob e el ´e mino egula de segundo o den. Sin emba go, es e esquema es aplicable s´olo a dominios ec angula es o compues os po uni´on de ec ´angulos, dado que es p eciso calcula una di e gencia disc e a en los nodos on e a. 3.2 El esquema egula izan e p opues o Pa a no ex ende la exposici´on, ha emos el desa ollo en el caso bidimensional. De o ma an´aloga puede hace se pa a el caso N-dimensional. Pa a la esoluci´on de (19), de inido en un dominio a bi a io, con obje o de ob ene un esquema egula izan e, conside a emos el p oblema disc e o (20), donde:  Ωhes el dominio disc e o de e minado a pa i de una e ´ıcula ca esiana egula , que se ´a el mismo pa a la elocidad y la p esi´on.  ∆hes el ope ado de Laplace disc e o bidimensional, de inido po la ap oximaci´on de cinco pun os de o den h2, es deci : ∆hzi,j =zi−1,j +zi+1,j −4zi,j +zi,j−1+zi,j+1 h2.(25)  Gh= (Gx h, Gy h) y Dhson los ope ado es g adien e y di e gencia disc e a, ob enidos median e ap oximaciones de segundo o den basadas Pa alelizaci´on y p oblemas ell´ıp icos 47 en di e encias cen adas: Gx hPi,j =Pi+1,j −Pi−1,j 2h, (26) Gy hPi,j =Pi,j+1 −Pi,j−1 2h, (27) Dh·U=Dh·(U, V )i,j =Ui+1,j −Ui−1,j 2h+Vi,j+1 −Vi,j−1 2h.(28) Calcula emos la p esi´on exclusi amen e en los nodos in e io es, po lo que s´olo es necesa io e alua la di e gencia y el g adien e disc e o en dichos nodos. De aqu´ı que es e esquema puede aplica se en p oblemas con dominios no necesa iamen e ec angula es. Adem´as, se iene lo siguien e:  El ope ado di e gencia disc e a Dhdesacopla el mallado 2D en cua o submallados (ocho en 3D), pe o ´es e s´olo se aplica en los nodos in e io es. Dado que los alo es de la elocidad son conocidos sob e Γh, odos los submallados “ en” igual ap oximaci´on en la on e a.  El ope ado g adien e disc e o Gh(26)–(27) espe a los submallados an e io es, pe o su aplicaci´on en los nodos adyacen es a la on e a equie e la elecci´on de una adecuada ap oximaci´on. Po ejemplo, en los nodos de e e encia (1, j), seg´un la no aci´on habi ual, la aplicaci´on de (26) conduci ´ıa a Gx hP1,j =P2,j −P0,j 2h,(29) es deci , se ´ıa necesa io conoce la p esi´on P0,j en los nodos on e a de e- e encia (0, j). Pe o en es os nodos hemos exclu´ıdo el c´alculo de la p esi´on y, po consiguien e, debemos ealiza una ap oximaci´on que e ec ua emos median e una ex apolaci´on unidi eccional, dada po P0,j = 3P1,j −3P2,j +P3,j .(30) El e o de uncamien o asociado es e0,j =p(0, jh)−P0,j =h3pxxx +O(h4).(31) As´ı pues, de (29) y (30) se iene que Gx hP1,j =−3P1,j + 4P2,j −P3,j 2h,(32) que no es m´as que la ´o mula de di e encias p og esi as de segundo o den. F´o mulas an´alogas a ´es a (di e encias p og esi as o eg esi as) se ob ienen en los nodos adyacen es al es o de la on e a. Seg´un (31), (32) y exp esiones an´alogas, cada uno de los submallados an es ci ados “ e” di e en es condiciones de con o no pa a la p esi´on, que se 48 M. C. Calzada y o os di e encian en ´e minos de o den h3. Po consiguien e, el desa ollo asin ´o ico de la p esi´on, ap oximada po es e esquema, iene un ´e mino al e nan e de o den h3, es deci , un ´e mino de la o ma bp(3) i,j =p(3)(ih, jh) + (−1)ip(3i)(ih, jh) + (−1)jp(3j)(ih, jh) + (−1)i+jp(3ij)(ih, jh) donde las p(3),p(3i),p(3j)yp(3ij)son unciones egula es e independien es de h. Se iene en onces el siguien e esul ado, cuya demos aci´on puede encon a se en [9]: Teo ema 1 Si la soluci´on (u, p)del p oblema de S okes (19) es su icien emen e egula , en onces la soluci´on (U, P )del p oblema disc e o (20), co espondien e a los ope ado es (25)–(28) ac uando en los nodos in e io es y omando sob e la on e a los alo es ex apolados pa a la p esi´on, iene un desa ollo asin ´o ico del e o dado po U=u+h2u(2) +h5b u(5) +··· ,(33) P=p+h2p(2) +h3bp(3) +··· ,(34) donde u(2) yp(2) son ´e minos egula es y b u(5) ybp(3) son ´e minos al e nan es. Po an o, las ap oximaciones de Uy de Pson ambas de segundo o den en h. 3.3 Expe iencias num´e icas “Tes ” en dominio ec angula Con obje o de comp oba el compo amien o num´e ico del esquema p opues o y compa a lo con el esquema de disc e izaci´on de Cho in (aplicable s´olo en dominios ec angula es), conside a emos inicialmen e el “ es ” con soluci´on anal´ı ica p opues o po J.T. Oden en [14]. Consis e en la esoluci´on de (19) en el cuad ado Ω = (0,1) ×(0,1), con α= 0, ν = 1 y elegida pa a que la soluci´on exac a enga dada po : u1(x, y) = 8x2(1 −x)2y(y−1)(2y−1), u2(x, y) = 8y2(1 −y)2x(x−1)(1 −2x), p(x, y) = 4(x−x2). (35) La p esi´on oma alo es en el in e alo [0,1], siendo las isoba as segmen os e icales. La implemen aci´on p ´ac ica se e ec ´ua aplicando un algo i mo ipo g adien e conjugado en el que se in eg a el m´e odo SDI ( e [9]), de aqu´ı que el m´e odo sea i e a i o. En la Figu a 9 esumimos los esul ados ob enidos al aplica los esquemas an e io men e ci ados: el m´e odo de Cho in sin il a las p esiones, el m´e odo de Cho in il ando las p esiones seg´un el pa ´on ob enido en [9] y el esquema egula izan e p opues o. En conc e o, en cada columna de la g ´a ica, ep esen amos:  El compo amien o, espec o al n´ume o de i e aciones, de la no ma in ini o del e o exac o an o del campo de elocidades como de la p esi´on, pa a di e en es alo es del paso de disc e izaci´on h. Pa alelizaci´on y p oblemas ell´ıp icos 49  Las isoba as pa a el caso h= 0,05.  El e o exac o de la p esi´on median e un g ´a ico de supe icie cuando h= 0,05. Pa a el p ime esquema (p ime a ila de g ´a icos en la Figu a 9), podemos obse a que la exis encia de un ´e mino al e nan e de p ime o den en la p esi´on conduce a la p´e dida de p ecisi´on, que se e leja en la si uaci´on inal alcanzada en el e o exac o y que es del o den e´o ico demos ado en [19]. La elocidad no se e a ec ada. Son muy signi ica i as las oscilaciones de las isoba as, as´ı como el p edominio del e o de ipo al e nan e en e al egula , que se ap ecia en el g ´a ico de supe icie. Tambi´en se puede obse a que el e o es ´a asociado a los di e en es submallados. En el segundo esquema, el il o aplicado a la p esi´on log a que el ´e mino al e nan e de p ime o den se aslade al e ce o den, po lo que pasa a p edomina el ´e mino egula de segundo o den y, po an o, se egula iza la p esi´on (es e hecho es ´a demos ado en [9]). Figu a 9: Resul ados del “ es ” de Oden pa a di e en es esquemas. Podemos obse a en la segunda ila de esa misma igu a que el compo amien o de la elocidad es el mismo, pe o la p esi´on mejo a su p ecisi´on, alcanz´andose el o den indicado y mani es ´andose peque˜nos cambios en la con e gencia debido al ´e mino al e nan e, ya de e ce o den. Las isoba as e lejan le es oscilaciones, debido m´as al e o p opio de un m´e odo ap oximado que a la p esencia de p esiones esp´u eas. En el g ´a ico de supe icie, se obse a el p edominio del ´e mino egula de segundo o den y la p esencia del e o al e nan e en un o den supe io . No se ap ecia ya dis inci´on en e los di e en es submallados. En el e ce caso, de acue do con lo demos ado an e io men e, se log a alcanza el e o egula de segundo o den, an o pa a la elocidad como pa a la p esi´on, no apa eciendo oscilaciones en las isoba as. El g ´a ico de supe icie ambi´en e leja el compo amien o egula del e o y no se obse a 50 M. C.˜Calzada y o os dependencia de los submallados. Hemos ealizado un n´ume o de i e aciones muy supe io al necesa io, pa a pode in ui el compo amien o asin ´o ico del algo i mo. Omi imos la ep esen aci´on g ´a ica del campo de elocidades dado que, seg´un lo desc i o an e io men e, ´es e no se e a ec ado en la p ´ac ica. “Tes s” 2D y 3D en dominios no ec angula es Como ejemplo de “ es s” bidimensional y idimensional de inidos en dominios no ec angula es, conside a emos la de e minaci´on de un luido es ´a ico (“No Flow”) sob e el que ac ´ua una ue za g a i acional. En la Figu a 10, e lejamos las p esiones ob enidas median e l´ıneas y supe icies isob´a icas, espec i amen e. Se puede comp oba , de nue o, el ca ´ac e egula izan e del esquema p opues o, no apa eciendo p esiones esp´u eas. En [9], pueden encon a se esul ados con o os “ es s” e ec uados. Figu a 10: Isoba as y supe icies isob´a icas en los “ es s” “No Flow” 2D y 3D. Ag adecimien os T abajo pa cialmen e inanciado po la D.G.E.S., P oyec o BFM2003–06446– C02–02 y po la Jun a de Andaluc´ıa, ACC–1204–FQM124. Re e encias [1] I.I. Alba eal -Pa alelizaci´on en iempo y espacio de la esoluci´on num´e ica de algunas ecuaciones en de i adas pa ciales, Tesis, Uni e sidad de Se illa (2004). [2] A.J. Cho in -On he con e gence o disc e e app oxima ions o he Na ie -S okes equa ions, Ma h. Comp, 22 (1968), 745–762. Pa alelizaci´on y p oblemas ell´ıp icos 51 [3] J.L. C uz, M.C. Calzada, E. Fe n´ andez-Ca a, M. Ma ´ ın -A pa allel algo i hm o sol ing he incomp essible Na ie -S okes p oblem, Comp. Ma h. wi h Appl., 25 (9) (1993), 51–28. [4] J.L. C uz, M.C. Calzada, E. Fe n´ andez-Ca a, M. Ma ´ ın -A con e gence esul o a pa allel algo i hm o sol ing he Na ie -S okes equa ions, Comp. Ma h. wi h Appl., 35 (4) (1998), 71–88. 1995. [5] E.J. Dean, R. Glowinski -On Some Fini e Elemen Me hods o he Nume ical Simula ion o Incomp essible Viscous Flow, Incomp essible compu a ional luid dynamics (M.D. Gunzbu ge and R.A. Nicolaides, Eds.), Camb idge U.P., USA 1993, 17–65. [6] J. Douglas J ., J.E. Gunn -Al e na ing di ec ion me hods o pa abolic sys ems in mspace a iables, J. Assoc. Compu . Mach., 9(1962), 450–456. [7] J. Douglas J ., H.H. Rach o d J . -On he nume ical solu ion o hea conduc ion p oblems in wo and h ee space a iables, T ans. Ame . Ma h. Soc., 82 (1956), 421–439. [8] C. Fle che -Compu a ional echniques o Fluids Dinamics. Vol 2. Speci ic echniques o di e en low ca ego ies, Sp inge -Ve lag, Be lin (1991). [9] J.R. Galo -Resoluci´on en pa alelo de las ecuaciones de Na ie -S okes 2D y 3D median e el m´e odo de di ecciones simul ´aneas, Tesis, Uni e sidad de Se illa (2002). [10] R. Glowinski -Supe compu ing and he ini e elemen app oxima ion o he Na ie -S okes equa ions o incomp essible iscous luids, Recen ad ances in compu a ional luid dynamics (P ince on, NJ, 1988), Sp inge , Be lin 1989, 277–315. [11] S.L. Johnsson, Y. Saad, M.H. Schul z -Al e na ing di ec ion me hods on mul ip ocesso s, SIAM J. Sci. S a is . Compu ., 8 (5) (1987), 686–700. [12] T. Lu, P. Nei aanmaki, X.C. Tai -A pa allel spli ing-up me hod o pa ial di e en ial equa ions and i s applica ions o Na ie -S okes equa ions, RAIRO Mod´el. Ma h. Anal. Num´e ., Vol. 26 (6) (1992), 673– 708. [13] G.I. Ma chuk -Spli ing and al e na ing di ec ion me hods, Handbook o nume ical analysis, Vol. I, No h-Holland, Ams e dam 1990, 197–462. [14] J.T. Oden, O. Jacquo e -S abili y o some mixed ini e elemen me hods o S okesian lows, Compu . Me hods Appl. Mech. Eng., 43(2) (1984), 231–247. [15] D.W. Peaceman, H.H. Rach o d J . -The nume ical solu ion o pa abolic and ellip ic di e en ial equa ions, J. Soc. Indus . Appl. Ma h., 3(1955), 28–41. 52 M. C. Calzada y o os [16] G. S ang -Accu a e pa ial di e ence me hods. I. Non-linea p oblems, Nume . Ma h., 6(1964), 37–46. [17] X.C. Tai, P. ˜ Nei aanmaki -Pa allel ini e elemen spli ing-up me hod o pa abolic p oblems,7 (3) (1991), 209–225. [18] R.S. Va ga -Ma ix i e a i e analysis, Sp inge -Ve lag, Be lin 2000. [19] B.R. We on -Analysis o he spa ial e o o a class o ini e di e ence me hods o iscous incomp essible low, SIAM J. Nume . Anal., 2(1997), 723–755.