Implementación paralela de un método numérico híbrido global en ecuaciones de convección difusión

Re is a In e nacional de Mé odos Numé icos pa a Cálculo y Diseño en Ingenie ía. Vol. 11,4, 695-705(1995) * Depa amen o de Ma emá ica Aplicada Uni e sidad Poli écnica de Valencia Camino de Ve a s/n 4 6071 Valencia, Spain ** Depa amen o de Sis emas In o má icos y Compu ación Uni e sidad Poli écnica de Valencia Camino de Ve a s/n 46071 Valencia, Spain RESUMEN P esen amos un mé odo numé ico híb ido global, y su implemen ación en pa alelo sob e el mul ip ocesado de memo ia compa ida Allian FX/80, pa a el a amien o de ecuaciones de con ección-di usión en egimen ansi o io en dos dimensiones. El mé odo se basa en la disc e ización ealizada en el caso es aciona io con bases de Legend e adap adas al ope ado , conjun amen e con la u ilización de la ans o mada de Laplace y un algo i mo po bloques de educción cíclica o pa -impa que implemen amos en pa alelo pa a la esolución de los sis emas idiagonales po bloques asociados al p oblema. Es o nos pe mi e ob ene soluciones ap oximadas de o ma ápida y sin es icciones sob e el paso de iempo, al con a io de lo que sucede en o os mé odos como di e encias ini as o elemen os ini os. Se compa an las p es aciones ob enidas en el algo i mo po bloques de educción cíclica con las de o os algo i mos po bloques basados en eliminación Gaussiana y écnicas del ipo di ide y ence ás. SUMMARY We p esen a global hyb id me hod and i s pa allel implemen a ion on he sha ed memo y mul ip oceso Allian FX/80 o he ea men o wo dimensional ansien con ec ion-di usion equa ions. The me hod is based on he disc e iza ion o he s eady s a e using Legend e basis adap ed o he ope a ion, oge he wi h he use o he Laplace ans o ma ion and a cyclic block educ ion o odd-e en algo i hm implemen ed in pa allel o he solu ion o he idiagonal block sys em associa ed o he p oblem. This allows us o ob ain app oxima e solu ions e y Recibido: Ene o 1995 OUni e si a Poli ecnica de Ca alunya (España) ISSN 0213-1315 696 E CHECA MARTÍNEZ Y V. HERNÁNDEZ GARCÍA as and wi hou es ic ions on he ime s ep compa ing a ou ably wi h o he me hods such as ini e di e ences and ini e elemen s. The ob ained esul s using he cyclic block educ ion a e compa ed o algo i hms based on Gaussian elimina ion and di ide and win echniques. INTRODUCCI~N La elección de bases pa a la disc e ización de una ecuación di e encial, como po ejemplo la de di usión o con ección-di usión, es uno de los aspec os cla es en la ap oximación numé ica de la solución. En pa icula , en p oblemas de con ección- di usión apa ecen peculia idades y di icul ades p opias debidas al é mino de con ección que des uye la sime ía del ope ado y que complica su esolución. La elección p opues a en es e abajo conduce a es uc u as ma iciales sencillas, que e i an los p oblemas compu acionales asociados a la ob ención de sis emas con ma iz coe icien e densa, mal condicionada e c. En la sección siguien e conside amos bases polinomiales que son combinación de polinomios de Legend e. Se consiguen así es uc u as ma iciales en la disc e ización que nos pe mi en ob ene esul ados p ecisos en égimen es aciona io, an o en el caso unidimensional como bidimensiona13. En la sección 2 p esen amos un algo i mo numé ico híb ido global pa a el caso ansi o io, en el con ex o de las ecuaciones ci adas, que se apoya en el a amien o ealizado en la sección 1 y que es á elacionado con los esul ados expues os en4Y5. Pa a lle a a cabo es e nue o en oque hacemos uso o mal de la ans o mada de Laplace y de un algo i mo de in e sión desa ollado en8 cuya implemen ación en pa alelo ha sido es udiada en3. Finalmen e, en la sección 3 desa ollamos y analizamos, en el con ex o de las ecuaciones ci adas con la disc e ización ealizada, un algo i mo de educción cíclica po bloques desa ollado e implemen ado sob e el sis ema mul ip ocesado de memo ia compa ida Allian FX/80. Las p es aciones de es e algo i mo se compa an con las de un algo i mo del ipo di ide y ence ás po bloques p opues o ambién en3. 1. RÉGIMEN ESTACIONARIO. DISCRETIZACION EN BASES NO CONVENCIONALES Conside amos el subespacio ec o ial de polinomios de g ado meno o igual que N + 2 siguien e VN = {P(x) E PN+2(x) : P(-1) = P(1) = O) y la base {Q3(x)), Q3(x) = L3+2(x) - L3(x) , siendo Lk(x) los polinomios de Legend e de g ado k. Es as bases es án incluidas en la li e a u a cien í ica den o de o as más gene ales denominadas hie á icasl. Es bien conocido que los polinomios Q3 (x) se pueden exp esa como (1 - X~)R~(X), y po an o se cumple que se anulan en la on e a. Igualmen e se e i ica que Q; (x) = (23 + 3) L3+i (x), p opiedad impo an e en los desa ollos que ealizamos pa a los p oblemas a ados. O as ó mulas explíci as deducidas de las an e io es y que son ú iles en nues os desa ollos apa ecen en3. El esquema es á basado en ap oximaciones polinomiales en subespacios cuyas bases seleccionadas son p oduc o enso ial de bases del caso unidimensiona13. De es e modo se IMPLEMENTACIÓN DE UN MÉT. NUM. HÍBRIDO GLOBAL EN EC. DE CONV.- DIF. 697 ob ienen es uc u as ma iciales, suscep ibles de se esuel as median e mé odos p opios de la compu ación en pa alelo. Conside amos el p oblema1' ( ~(5,742) = (71/2)2 - x2 donde apa ece un é mino de di usión dado po las de i adas de segundo o den, jun o con uno de con ección, dado po un luido con elocidad -2a, pa alelo al eje y. T ans o mando es e p oblema en el in e alo (-1,l) x (-1,l) se end á, en un plan eamien o Gale kin, después de aplica un eo ema de G een, y conside ando que la solución se desa olla en bases que son p oduc o enso ial de las u ilizadas en el caso unidimensional, las ecuaciones siguien es con I=(-l,l)x(-l,l), k=O ,..., N yj=O ,..., M El sis ema que se ob iene iene ma iz coe icien e idiagonal po bloques, con bloques en la diagonal p incipal con es uc u a pen adiagonal y el es o con es uc u a idiagonal. Tenemos que añadi , que como sucede á en el p oblema ans o mado que se conside a en la sección siguien e, si en el p oblema an e io se conside a en la ecuación co espondien e un é mino adicional de la o ma su(x, y), como se á el caso del p oblema ans o mado de con ección- di usión, se ob iene que odos los bloques ienen es uc u a pen adiagonal. Cuando se hace uso de la ans o mada de Laplace es impo an e dispone de un mé odo de in e sión que sea e icien e, pues en caso con a io es a he amien a analí ica pie de, en el con ex o de los mé odos numé icos, pa e de su e iciencia. U ilizamos un algo i mo de in e sión8 que se es á mos ando e icien e, como puede e se en4Y5 donde 698 E CHECA MARTÍNEZ Y HERNÁNDEZ GARCÍA se combina con el mé odo de di e encias ini as y con el de elemen os ini os, odo ello en el con ex o de la ecuación del calo . Caso unidimensional: Mé odo numé ico híb ido global Conside amos la ecuación de con ección-di usión en égimen ansi o io au(x,y) D++V~=O a2u(x ) ~(0, ) = 1, u(1, ) = O, u(x, O) = O {T- Con i iendo la ecuación en o a equi alen e con condiciones de Di ichle N homogéneas y ans o mando el p oblema, admi iendo que h(x, S) = an(s)Qn(x) es una ap oximación a la solución del p oblema ans o mado se iene, en un plan eamien o Gale kin es ánda , las ecuaciones siguien es N 4~ an(s)(S1 (2j + 3)(2n + 3)~n+i(~)~j+i(x)d~- n=O -1 1 -S_l (2~ + 3) (Ln+2(~) - Ln(x))dx+ + S S_:(~n+2(x) - L~(x))(L~+~(x) - ~j (x))dx = ~c, con ko = -2(( /s) - 1/2), kl = -11 y Ic:, = O si j > 2 Es as ecuaciones conducen a un sis ema lineal con es uc u a pen adiagonal. Los esul ados ob enidos pa a dis in os iempos apa ecen desc i os en la siguien e g á ica. Los esul ados han sido con as ados con la solución analí ica desa ollada en o ma de se ie. ~{l~(,l'lll~h THANs PHO(_'EsC) I)I IJb,I(CiION 1 ' 08 o 11 ( ' u (5 11 C a. 04 ( 1 n o2 u -1 -0 8 -0 6 -0 4 -0 2 O U '2 O 11 O O O X 1 0 = 10, + = 100, o = 2000 La si uación se complica cuando el é mino uen e es una dis ibución como la S de Di ac, pues añade p oblemas en o no al pun o donde es á cen ada dicha dis ibución. También en es os casos, en égimen ansi o io, se consiguen buenos esul ados, aunque con ap oximaciones de o den al o7. Ex ensión al caso bidimensional. Soluciones numé icas po secciones y e olución empo al en pun os ijos En es e caso, omamos como e e encia un p oblema de di usión que analiza la dispe sión de calo en una placa delgada con empe a u a inicial dada y empe a u a en la on e a cons an e. Pos e io men e se ob iene la es uc u a ma icial en el caso de con ección-di usión que se es udia á en la sección siguien e en un con ex o de compu ación en pa alelo. La ecuación en de i adas pa ciales que modeliza el enómeno an e io , con alo es pa icula es en la on e a y en la condición inicial, es con k = 519. Aplicando la ans o mada de Laplace a es e p oblema, de inimos sob e el p oblema ans o mado el uncional con = 30 y A6 = sil-k (g + $1 siendo D H~(O), y O el abie o (-1,l) x(-1,l). Aplicando un eo ema de G een sob e la exp esión del uncional y omando como base el p oduc o enso ial de bases polinomiales en el caso unidimensional, Qjk(x, y) = Qj(x)Qk(y) donde Qj(x) = (1 - x2)~j(x) y Qk(y) = (1 - y2)~k(y), buscamos una a p oximación global de la o ma Es a ap oximación puede implemen a se en gene al, aunque apa ezcan pequeños p oblemas po las dimensiones N,M con que se desa olla. Cons uimos la ap oximación pa a el pa (N, O) suponiendo po las condiciones e in e p e ación ísica del caso a ado que la solución es sua e en la di ección y, omando en es a solamen e el polinomio Qo(y). La aplicación del eo ema de G een conduce a la siguien e ecuación Después de sus i ui de i a pa cialmen e espec o de ajo y simpli ica se ob iene 700 E. CHECA MARTÍNEZ Y V. HERNÁNDEZ GARCÍA un sis ema idiagonal desacoplado siendo las incógni as impa es nulas a(2k+l)~, k = 0,1,2, .... Los esul ados ob enidos, omando dos unciones polinómicas en la di ección y, se desc iben seguidamen e a endiendo a cie as posiciones nodales3. Tpo = 1.2 h Posición N21 N28 N41 N6 1 N80 Si el desa ollo se ealiza con Qo(y),Qi(y), se ob end án dos sis emas desacoplados análogos al an e io , donde el único que o ece in o mación como consecuencia de la disc e ización es el que an es hemos desc i o. En e ec o, bas a obse a que las incógni as adicionales son ce o ya que J'~ Ql(y)Qo(y)dy = O y la es uc u a de las de i adas pa ciales espec o a ajl son análogas a las a adas. Si in oducimos los es p ime os elemen os de la base en la di ección y, se puede di idi el sis ema esul an e en subsis emas desacoplados, algunos de los cuales se pueden sup imi po ene la solución i ial. El único que no conduce a es a solución es el dado po las ecuaciones 8Fii aFü co espondien es a aa;M, aaJzM La es uc u a que apa ece conduce a una ma iz po bloques de la o ma (C E) siendo A,B,C,D idiagonales. El es udio ealizado conduce a los esul ados o ecidos en la abla an e io . Bajo el encabezamien o S. Ap ox. apa ecen los esul ados más p ecisos, y el núme o de g ados de libe ad son 15. En ealidad solo con ibuyen 10 unciones de la base, cinco en la di ección x y dos en la di ección y, que son Qo(y),Q2(y). El desa ollo ealizado si e como base pa a es ablece el siguien e esul ado en p oblemas de con ección-di usión. PROPIEDAD 1 Dado el p oblema + Lu = (x, y) con condiciones de Di ichle homogéneas y condición inicial nula, siendo L el ope ado de con ección-di usión Lu = Au - a$, se cumple que la disc e ización en las bases de Legend e adap adas en el caso bidimensional con un en oque Gale lcin y con ans o mación p e ia, conduce a un sis ema Ax = b con es uc u a idiagonal po bloques, siendo, en gene al, las ma ices que cons i uyen es os bloques, ma ices banda. La jus i icación del esul ado an e io se ob iene eniendo en cuen a la disc e ización ealizada con es as bases en el caso bidimensional, pa a el ope ado Lu = Au - a-" ay Y la del caso a.nsi o io del de di usión, en cuyo p oblema ans o mado apa ece el ac o su que se co esponde con E al aplica la T ans o mada de Laplace. B ush (A = 0.05) 0.185 1.039 1.286 1.938 0.922 TL-EFH 0.166 0.998 1.116 1.697 0.813 TL-DF 0.175 1.176 1.198 1.831 0.871 S. Exac a 0.173 1.065 1.186 1.812 0.862 S. Ap ox. mod(4,2) 0.172 1.064 1.186 1.810 0.862 IMPLEMENTACI~N DE UN MÉT. NUM. HIBRIDO GLOBAL EN EC. DE CONV.- DIF. 701 Des acamos el hecho de que el plan eamien o ealizado pe mi e el es udio del enómeno conside ado en secciones del dominio pa a un iempo cualquie a, sin que ello suponga el conoce la ap oximación a la solución del p oblema en pun os con iguos. Además con iene añadi el in e és que supone ija un pun o cualquie a del dominio y es udia aquí la e olución empo al del enómeno, con el mismo cos e compu acional que pa a un único alo de la a iable iempo, pues los p ocesos son independien es. En las secciones an e io es se ha ealizado un es udio de cie o ipo de ecuaciones de con ección-di usión que apa ecen en la p ác ica y que, con el en oque ealizado, conducen en el caso de coe icien es cons an es a sis emas de ecuaciones lineales con ma iz coe icien e idiagonal po bloques, suscep ibles de se esuel os en pa alelo de o ma ápida y e icien e. Los esul ados del apa ado siguien e no sólo ienen aplicación en los p oblemas señalados sino en con ex os más gene ales, como al aplica esquemas de di e encias ini as o elemen os ini os en ecuaciones de ipo elíp icog. En ambos se ob ienen sis emas de ecuaciones lineales con ma iz coe icien e idiagonal po bloques con bloques de es uc u a de e minada. Algo i mo de educción cíclica o pa -impa po bloques Conside emos el sis ema de ecuaciones lineales Ax = b, siendo A una ma iz idiagonal po bloques exp esada de o ma gené ica como A = (O,. . . , B,, A,, C,, . . .). El desa ollo es álido igualmen e pa a la ecuación ma icial AX = B, siendo B una ma iz. Suponemos que se e i ican condiciones de egula idad sob e las subma ices (bloques) de o ma al que puedan lle a se a e ec o las ope aciones siguien es. Conside amos el es udio del caso gene al, donde A es una ma iz idiagonal po bloques, y donde pa icionamos x y b de acue do a los bloques de la ma iz A. Suponemos que el núme o de bloques que iene A en la diagonal es N = 2m - 1, sin que es o suponga ninguna es icción, pues en la implemen ación se ha omado un alo de N cualquie a, comple ando el sis ema con ilas de la o ma (. . . , O, 1, O, . . .) y é mino independien e (1,1,. . . , I)~. Una ecuación ca ac e ís ica del sis ema end á la o ma B,X,-~ +Aix, + C,X,+~ = b, donde i = 1,2, ..., N siendo Bl = CN = O y x0 = XN+~ = O Conside amos pues la ila i-ísima de A, con i pa ,(. . . ,O, Bi, Ai, Ci, O, . . .). La idea básica consis e en p emul iplica , espec i amen e las ilas i - 1, i + 1 po ma ices con enien es ales que al es a las ambas a la ila i se ob enga o a con la siguien e es uc u a (. . . , O, B:, O, A:, O, c:, O, . . .). Es as ope aciones c ean un subsis ema idiagonal a pa i de las 2m-1 - 1 ecuaciones de índice pa . Aunque las ecuaciones impa es no se conside en, las incógni as impa es se pueden ob ene pos e io men e a pa i de las pa es po sus i ución eg esi a. Dadas aho a las 2m-1 - 1 ecuaciones con incógni as pa es solamen e, se puede elimina un nue o g upo de incógni as, consiguiendo así, un conjun o de 2m-2 - 1 ecuaciones que implican incógni as cuyo índice es un múl iplo de 4. Es e esquema puede epe i se has a ob ene una única ecuación pa a x2,-i y esol iendo el sis ema co espondien e se hab á calculado xp-l. Llegados a es e pun o se calculan las incógni as en o den in e so al que ue on eliminadas, median e sus i ución eg esi a. Supues o que es amos en la i e ación Ic del p oceso, con is as a ob ene las ó mulas gene ales pa a la pos e io implemen ación del algo i mo se deben calcula ma ices (H~)!, (H~)!, ales que El algo i mo de esolución implemen ado puede consul a se en3. Implemen ación y compa ación de esul ados sob e el mul ip ocesado de memo ia compa ida allian FX/80 Conside amos en p ime luga un ejemplo es de ma iz idiagonal escala que igu a en2 y pos e io men e los casos que su gen al a a los p ocesos de con ección- di usión disc e izados en bases hie á icas. Es os p ocesos conducen a es uc u as ma iciales po bloques, con los bloques de la diagonal p incipal pen adiagonales y los que es án en la subdiagonal y supe diagonal p incipal con es uc u a idiagonal. Aquí no se end á en cuen a es e hecho pa a da le a nues o a amien o un ca ác e más gene al. Se ha comp obado que el algo i mo de educción cíclica con 8 p ocesado es o ece, en e al algo i mo de descomposición LU con 1 p ocesado , un speed-up de has a 3.5 en el caso N1 = 2016, siendo N1 el núme o de bloques en la diagonal p incipal, y cada bloque de dimensión es en es e caso. Seguidamen e p esen amos el speed-up conseguido en la implemen ación ealizada del algo i mo de educción cíclica AL(~OKI'ih10 PAKIMPAK 8 I I I I I I I BLOQUES EN LA DIAGONAL Se obse a el al o speed-up de es e algo i mo, aunque cabe añadi que como algo i mo secuencia1 es ancamen e ine icien e, al con a io de lo que sucede á con IMPLEMENTACIÓN DE UN MÉT. NUM. HÍBRIDO GLOBAL EN EC. DE CONV.- DIF. 703 el algo i mo DAC que con un p ocesado supe a, en algunos casos, a la descomposición LU en iempos de ejecución3. La siguien e g á ica mues a una compa ación en iempos de los dos algo i mos 0 Pa impa Global, + Dac Combinado Del es udio ealizado conclumos que, en el caso gene al de ma ices idiagonales po bloques, el mejo algo i mo de los es udiados es el de educción cíclica. La si uación puede cambia si el sis ema es idiagonal po bloques con bloques de es uc u a de e minada, como sucede en el a amien o ealizado en los p ocesos de con ección- di usión donde la es uc u a de las subma ices es idiagonal y pen adiagonal. Tenemos que señala ambién en nues o con ex o que la mejo p ecisión se ob iene con eli algo i mo de educción cíclica, igualada po el algo i mo di ide y ence ás, DAC, pa a amaños de e minados, y lo que es más impo an e con N1 dado, la elección que se haga de los pa áme os IB e IK en la descomposición en subma ices pues Nl=IB.IK, siendo IB el núme o de subdi isiones en la ma iz e IK el núme o de ma ices de cada subdi isión7. P esen amos a con inuación un es udio del speed-up pa a ambos algo i mos, en unción del núme o de bloques en la diagonal p incipal y del amaño de cada bloque. Algo i mo: REDUCCIÓN CÍCLICA. Speed up N1 = Núme o de bloques diagonal p incipal N = Tamaño de bloque