Computación en Paralelo: Nuevas
Formulaciones de los Métodos
Precondicionados de Subestructuración
Examen de Candidatura
Antonio Carrillo Ledesma
Tutor: Dr. Ismael Herrera Revilla.
1
INDICE
•
•
•
•
•
•
•
•
•
•
•
•
Motivación
Objetivos
Contexto general
Métodos iterativos de dominios ajenos
Métodos Single-Trip
Métodos Round-Trip
Teoría unificada sin multiplicadores de Lagrange
Fórmulas de Green-Herrera para matrices
Teoría unificada de métodos Dual-Primal
El cómputo paralelo
Avances y Trabajo por Hacer
Conclusiones
2
MOTIVACIÓN
3
MOTIVACIÓN…
La modelación de sistemas continuos en la Ingeniería y la
Ciencia está basada en la solución numérica de sistemas de
ecuaciones diferenciales parciales.
La solución de los sistemas que gobiernan tales modelos
tienen un gran número de grados de libertad y a pesar de los
constantes avances en cómputo, un solo procesador no puede
resolver dichos problemas.
Por ello, un recurso indispensable es el cómputo en paralelo,
que en conjunción con el desarrollo de los métodos de
descomposición de dominio permiten atacar problemas que
involucren un gran número de grados de libertad.
4
MOTIVACIÓN …
En la actualidad los métodos de descomposición de dominio
se dividen en dos grandes grupos, los de dominios
yuxtapuesto y los de dominios ajenos, nosotros trabajaremos
sobre estos últimos por presentar los mejores rendimientos al
usar el cómputo en paralelo para los problemas que nos
interesan.
Los métodos más usados, se basan en resolver problemas
locales sobre los subdominios pero en la frontera común de
los mismos estas son discontinuas y mediante el uso de los
multiplicadores de Lagrange se logra empatar dichas
soluciones para generar una solución continua.
5
OBJETIVOS
6
OBJETIVOS
Desarrollar un método de descomposición de dominio que:
– No use multiplicadores de Lagrange
– Sea una formulación unificadora de las formulaciones
del tipo subestructuración
– Quede expresado de forma matricial explícita en
términos de matrices de Schur exclusivamente
– Sea aplicable a problemas Elípticos y Parabólicos tanto
lineales como no lineales
7
CONTEXTO GENERAL
8
CLASIFICACIÓN DE LOS MÉTODOS
DE DESCOMPOSICIÓN DE DOMINIO
• Métodos de Dominios Yuxtapuestos
• Métodos de Dominios Ajenos
9
Métodos de Dominios Ajenos
10
MÉTODOS DE DESCOMPOSICIÓN
DE DOMINIO TIPO
SUBESTRUTURACIÓN
• Complemento de Schur
• Finite Element Tearing and Interconnecting (FETI)
• Finite Element Tearing and Interconnecting Dual-Primal
(FETI-DP)
11
NODOS DE FRONTERA INTERIOR
EN EL COMPLEMENTO DE SCHUR
12
COMPLEMENTO DE SCHUR
R e s o lv e r e l s is te m a v irtu a l
 E

 E

S
u

b
 i  
 i 
 i 1

 i 1

donde:
 A
S
i
i

 A
bi  A
i
I
i
I


A
i

A
II
i
II

1
1
A
i
I
i
bI
U n a v e z re s u e lto e l s is te m a v irtu a l p a ra u  , la
s o lu c ió n e n lo s n o d o s in te rio re s s e o b ti e n e
i
uI 

A
i
II
 
1
i
bI  A
i
I
i
u

13
NODOS EN FETI
Nodo Primal:
1 grado de libertad
Nodo Dual:
2 ó más
grados de libertad
Nodo
Grado de libertad
14
NODOS DE FRONTERA INTERIOR
EN FETI
15
MÉTODO FETI
R eso lver el sistem a virtu al
P F  P d
T
T
d o n d e:
P
T

T
 I  G G QG
†

1
T
G Q
T
F  B S B ,G  B R,d  F S
†
f
C u yo p reco n d icio n ad o r m ás b ásico esta d a d o p o r
M
1
E
 BS B
T


i 1
B S B
i
i
T
i
16
MÉTODO FETI
U na vez resuelto el sistem a virtual para 
L a solución en la frontera interior es d ada por
u  S
†
f

T
 B 
y la solución en los nodos interiores po r
i
uI 
 A  b
i
II
1
i
I
i
i
 A u
I

17
NODOS DE FRONTERA INTERIOR
EN FETI-DP
18
MÉTODO FETI-DP
R esolver el sistem a virtual
M
1
F  M
1
d
donde:
F  B
S  B 
1

T

,d  B

S 
1
f

C uyo precondicionador m ás básico esta da do por
M
1
 B
D ,
S
B

D ,

B
D ,

T
E


i 1
i
i
i



D B S
1
1
E1
E
  D B ,..., D B 
  

 
 
B
i

T
D
i

19
MÉTODO FETI-DP
D efin ien d o en cad a su b d o m in io  i , la s m atrices
i
i
II
I
A ,A
,A
i
I
,A
i

,A
i

,A
i

así d efin im o s
 A
II

 
i
A

I
i
i
S  A
i


i

A
I

 
T
A
i


T

A

T
 A
II

 
i
A

I
A
i
i
f

 f
i




A
I

i
 A 
T
i

T

i
I
i

A

T
A




i
I
i

1




 Ai
 I
 Ai
 
1




 f i
 I
 f i
 




20
MÉTODO FETI-DP
U n a vez resu elto el sistem a virtu al p ara 
L a so lu ció n en la fro n tera in terio r es d ad a p o r
u 
S
1


f

B 
T



y la so lu ció n en lo s n o d o s in terio res p o r
i
uI 
 A  b
i
II
1
i
I
i
i
 A u
I

21
FUNCIONES DEFINIDAS POR
PEDAZOS

Г

    1 , ...,  E 
D1  D1   1   ...  D1   E  y D 2  D 2   1   ...  D 2   E 
u   u 1 , ..., u E 
22
ESPACIOS DE SOBOLEV DE FUNCIONES
DEFINIDAS POR PEDAZOS
D efinición :
Hˆ
2
  
H
2
  1   ...  H 2   E 
M étrica :

   v
  1
E
vˆ
E ntonces , Hˆ
p , ,
2
2
p ,



1
2
   es un espacio de H ilbert.
23
SALTO Y PROMEDIO
u  u  u
u 
y
1
2
u  u 

Г
n
-
N ota : u   u 
1
2
+
u
y
u  u 
1
u
2
24
MÉTODOS ITERATIVOS DE
DOMINIOS AJENOS
25
FÓRMULAS DE GREEN-HERRERA
y otras propiedades
O perador diferencial de segundo orden
L u    u  u ; en  1 y  2
u  0; en 
F órm ula de G reen - H errera

w
u

G  u , w    w L udx    u
w


n
n




 dx 




u
w 

u
L
w
dx

w

u

 dx  G  w , u 


n
n 



P ropiedades :


w
u 

G  u , w      u  w  uw  dx    u
 w
 dx



n

n






u
u 

   u  w  uw  dx   w L udx    w  n  w  n  dx 






w
w 

 u L w dx    u  n  u  n  d x




26
ECUACIONES DE SEGUNDO ORDEN
en funciones discontinuas
  u  u  f  , en  1 y  2
u  0; en 
u 0 

 , en 
u
 0
n

F orm ulación débil : u es solución si y só lo si
G u, w  


w f  dx ,  w  Hˆ   
27
FUNCIONES ARMÓNICAS
C onsidere funciones tales que
L w  0; en  1 y  2
E ntonces

w
u

G u, w     u
w

n
n




 dx 




u
w 

w

u

 dx

n
n 



P ropiedades :


w
u 

G  u , w      u  w  uw  dx    u
 w
 dx


n
n 








u

u

w

w





u

w

uw
dx


w

w
dx


u

u





 dx




n
n 
n
n 






28
FORMULACIÓN CON ARMÓNICAS
discontinuas
  u  u  0, en  1 y  2
u  0; en 


 , en 
1
 j 

u  j
0
u
n
F orm ulación débil : u es solución si sólo si


 0 w

1
G  u , w     j
 j  w  dx ,  w  Hˆ   

n




29
SUBESPACIOS DE ARMÓNICAS
Sea D el espacio de las funciones arm óni cas y definim os


D1 1  w  D w  0, en  , D 1 2   w  D
D 21
w  0, en  


w



 w  D
 0, en   , D 2 2   w  D
n





w
n

 0, en  

30
RESUMEN GEOMÉTRICO
Producto Interior de Energía
D 22
w  Au
D1 1
D 21
D12
Propiedad : En las funciones arm ónicas la funcional bilineal,
G  u , w  es sim étrica y "silla" : positiva en D12 y negativa en D 22
31
MÉTODOS SINGLE-TRIP
32
A L G O R IT M O 1. - B asado en problem as de D ir ichlet

j  0  .
0
B usque u  D 12 tal que
G  u , w     j  w dx ,  w  D 12
1

A L G O R IT M O 2. - B asado en problem as de N eu m ann
j
1

 0.
B usq ue u  D 22 tal que
G u, w  


j
0

w
n
dx ,  w  D 12
33
MÉTODOS DE ROUND-TRIP
34
DOS SISTEMAS DE
COORDENADAS
T oda función arm ónica u  D puede escrbirse de dos m aneras :
 u  u 11  u 12 , con u 11  D11 y u 12  D12

 u  u 21  u 22 , con u 21  D 21 y u 22  D 22
T R A N SF O R M A C IÓ N D E C O O R D E N A D A S
   : D  D   ,  ,  = 1,2
P R O P IE D A D E S : L as transform aciones
 12 21 : D12  D12
y  22 11 : D 22  D 22
son sim étricas y positivas definidas. A d em ás :
 12 21     12 22
y  22 11     22 12
35
TRANSFORMACIÓN DE
COORDENADAS
O B SE R V A C IO N E S
"P roblem as de D irichlet" : C uando u  D 12 la o btención
de u 21  D 21 y u 22  D 22 requiere resolver un
problem a de D irichlet .
"P roblem as de N eum ann" : C uando u  D 22 la obtención
de u 11  D11 y u 12  D12 requiere resolver un
problem a de N eum ann .
36
MÉTODOS NEUMANN-NEUMANN Y
FETI
M étodo N eum ann - N eum ann
u  D12
y  12 21u   12 u 21
M étodo F E T I
u  D 22
y  22 12 u   22 u 12
37
EL NEUMANN-NEUMANN
CONSISTE DE UN DIRICHLET
SEGUIDO DE UN NEUMANN
P orque
 12 21     12 22
A dem ás :
C uando u  D12 D irichlet da  22 u
Y  12 22 u se obtiene por N eum ann   22 u  D 22 
38
EL FETI CONSISTE DE UN
NEUMANN
SEGUIDO DE UN DIRICHLET
P orque
 22 11     22 12
A dem ás :
C uando u  D 22 N eum ann da  12 u
Y  22 12 u se obtiene por D irichlet   12 u  D 12 
39
TEORÍA UNIFICADA SIN
MULTIPLICADORES DE
LAGRANGE
40
GENERACIÓN DE LA MATRIZ “A”
Nodo
Grado de libertad
Nodo Primal:
1 grado de libertad
Nodo Dual:
2 ó más
grados de libertad
41
GENERACIÓN DE LA MATRIZ “A”
42
REPRESENTACIÓN MATRICIAL
M a triz o rig in a l A y d e ella se d eriva o tra
 A   A  
A  

A
A
   
 A  A  
L  
,
 0 0 
 0 0 
R  

A
A
   
A  L  R,
43
ESPACIOS DE VECTORES
E l esp a cio to ta l d e vecto res es D   
E l esp a cio d e lo s vecto res co n tin u o s es D   
L a m a triz a : D     D    es la p ro yecció n en D   
L a m a triz j : D     D    es :
j  I a
N O T A C IÓ N :
u  au
y
u
 ju
44
FÓRMULAS GREEN-HERRERA
PARA MATRICES
45
A  L R
w Lu  u L w  u R w  w Ru y w Ru  w
R u w
Ru
F ó rm u la d e G reen - H errera p a ra m a trices
w Lu  u
Rww
R u  u Lw  w
Ru u
R

w
Aquí :
R
 a R m ien tra s q u e R  j R
46
FORMULACIÓN MATRICIAL
DEL PROBLEMA
E l problem a original tom a la form a
Lu  R u  R u  f
A dem ás, por G reen - H errera
L  R j  aR  L  R j  aR
T
i.e. la m atriz es sim étrica.
E ntonces el probl em a original queda escrito com o

T

L  aR  R j u  f
47
ESPACIO DE VECTORES ARMÓNICOS
E l p ro b lem a o rig in a l se tra n sfo rm a en
Lu  0
R u  R u  f

S e d efin e el esp a cio
D  u L u  0 ,
48
DOS SISTEMAS DE COORDENADAS
P rim er S istem a d e C o o rd en a d a s


D1 1  u  D u  0 , D1 2   u  D
D 21
u
 0
S eg u n d o S istem a d e C o o rd en a d a s


  u  D R u  0  , D1 2  u  D R u  0




P ro p ied a d es d e lo s S istem a d e C o o rd en a d a s
D  D1 1  D1 2 ,  0  D1 1  D1 2
D  D 2 1  D 2 2 ,  0  D 2 1  D 2 2
49
TEORÍA UNIFICADA DE MÉTODOS
DUAL-PRIMAL
50
MÉTODOS SINGLE-TRIP
• Método del complemento de Schur
• Método FETI sin precondicionar
MÉTODOS ROUND-TRIP
• Método del Neumann-Neumann
• Método FETI
51
MÉTODOS SINGLE-TRIP
• Método del complemento de Schur
aSu  f
2
• Método FETI sin precondicionar
S
1
ju   S
1
jS
1
f
2
52
MÉTODOS ROUND-TRIP
• Método del Neumann-Neumann
aS
1
aSu  aS
1
f
2
• Método FETI
S
1
j S ju   S
1
jS
1
jS
1
f
2
53
EL CÓMPUTO PARALELO
54
LOS DDM EN LA COMPUTACIÓN EN
PARALELO
Dificultades del Cómputo en Paralelo: La coordinación de los
múltiples procesadores y la transmisión de la información
entre ellos
Características de los DDM: El método, genera una serie de
tareas, las cuales se asignan a cada procesador; y en gran
medida son independientes y por eso mismo, la información
que se requiere transmitir entre ellos es muy poca
Ventajas de los DDM: Minimizan las necesidades de coordinación y también las de transmisión de información
55
LOS DDM EN LA COMPUTACIÓN EN
PARALELO
Ventajas del uso de Clusters de PC´s
•La construcción y puesta en marcha de un cluster es
barata.
•Reemplazar componentes defectuosos y escalar el
cluster es sencillo.
Cluster (Bajo Esquema Maestro-Esclavo)
56
COMPUTACIÓN EN PARALELO
A partir de los modelos matemáticos y los modelos numéricos
se desarrollará el modelo computacional contenido en un
programa de cómputo orientado a objetos en el lenguaje de
programación C++ en su forma secuencial y en su forma
paralela en C++ usando la interfaz de paso de mensajes (MPI)
bajo el esquema maestro-esclavo.
Esto no sólo nos ayudará a demostrar que es factible la
construcción del propio modelo computacional a partir del
modelo matemático y numérico para la solución de problemas
reales. Además, se mostrará los alcances y limitaciones en el
consumo de los recursos computacionales, evaluando algunas
de las variantes de los métodos numéricos con los que es
posible implementar el modelo computacional y haremos el
análisis de rendimiento.
57
COMPUTACIÓN EN PARALELO
También exploraremos los alcances y limitaciones de cada uno
de los métodos implementados y como es posible optimizar los
recursos computacionales con los que se cuente.
Hay que destacar que el paradigma de programación
orientada a objetos es un método de implementación de
programas, organizados como colecciones cooperativas de
objetos. Cada objeto representa una instancia de alguna clase
y cada clase es miembro de una jerarquía de clases unidas
mediante relaciones de herencia, contención, agregación o uso.
58
COMPUTACIÓN EN PARALELO
Esto nos permite dividir en niveles la semántica de los sistemas
complejos tratando así con las partes, que son más manejables
que el todo, permitiendo su extensión y un mantenimiento más
sencillo. Así, mediante la herencia, contención, agregación o
usó nos permite generar clases especializadas que manejan
eficientemente la complejidad del problema.
La programación orientada a objetos organiza un programa
entorno a sus datos (atributos) y a un conjunto de interfases
bien definidas para manipular estos datos (métodos dentro de
clases reusables) esto en oposición a los demás paradigmas de
programación.
59
AVANCES Y TRABAJO POR
HACER
60
AVANCES
• Se a coadyuvado en el desarrollo de una formulación
unificadora que no usa multiplicadores de Lagrange de la
cual se obtienen expresiones matriciales explícitas en
términos de matrices de Schur exclusivamente
• Se ha desarrollado la implementación secuencial y paralela
de los métodos de descomposición de dominio:
– Complemento de Schur
– FETI y FETI-DP
• Se está desarrollando la implementación secuencial de los
métodos Single-Trip
– Complemento de Schur
– FETI sin precondicionar
61
AVANCES
• Se está desarrollando la implementación secuencial de los
métodos Round-Trip
– Neumann-Neumann
– FETI
62
POR HACER
• Implementación paralela de los métodos Single-Trip
– Complemento de Schur
– FETI sin precondicionar
• Implementación paralela de los métodos Round-Trip
– Neumann-Neumann
– FETI
• Implementación de los métodos cuando el Ker(S) no es
trivial
63
POR HACER
• Comparación de los métodos desarrollados con los
métodos más usados como FETI y FETI-DP
• Aplicar el método desarrollado a problemas Elípticos y
Parabólicos, tanto lineales como no lineales
64
CONCLUSIONES
65
• Se ha desarrollado una teoría unificadora
• Se simplifica las formulaciones que unifica
• Se obtienen expresiones matriciales explícitas en términos
de matrices de Schur exclusivamente
• Los algoritmos se pueden derivan directamente del
planteamiento matricial, independientemente de la
ecuación diferencial parcial o sistema que lo origina y del
número de dimensiones del problema original
66
• Libertad para elegir nodos duales y primales,
resultando de esta elección en diferentes
precondicionadores a priori para ese problema en
particular
• El método desarrollado:
– Es aplicable a problemas Elípticos y Parabólicos, tanto
lineales como no lineales
– Reduce el esfuerzo de programación
– Reduce el esfuerzo computacional al momento de
ejecución
67
Descargar

Computacion en Paralelo: Nuevas Formulaciones de los