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