funciones radiales y m´etodos adaptivos pedro gonz´alez ... › smc-2007 › archivos ›...
TRANSCRIPT
![Page 1: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/1.jpg)
Descomposicion de Dominio conFunciones Radiales y Metodos Adaptivos
Pedro Gonzalez-Casanova Henrıquez
DGSCA, UNAM
Jose A. Munoz Gomez
Gustavo Rodrıguez Gomez
INAOE
Seminario de Modelacion Matematica y
Computacional
Instituto de Geofısisca, UNAM, Mexico
2007
![Page 2: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/2.jpg)
Introduction
Why RBF-PDE methods?
![Page 3: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/3.jpg)
Introduction
Why RBF-PDE methods?
• Classical methods like finite differences, finite
elements, etc. are based on grids.
![Page 4: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/4.jpg)
Introduction
Why RBF-PDE methods?
• Classical methods like finite differences, finite
elements, etc. are based on grids.
• In 2D frequently, 70 % of CPU time of real life
PDE’s problems are used on grid generation.
![Page 5: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/5.jpg)
Introduction
Why RBF-PDE methods?
• Classical methods like finite differences, finite
elements, etc. are based on grids.
• In 2D frequently, 70 % of CPU time of real life
PDE’s problems are used on grid generation.
• In 3D, mesh generation is even more time con-
suming and moving mesh methods are extremely
expensive.
![Page 6: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/6.jpg)
Introduction
Why RBF-PDE methods?
• Classical methods like finite differences, finite
elements, etc. are based on grids.
• In 2D frequently, 70 % of CPU time of real life
PDE’s problems are used on grid generation.
• In 3D, mesh generation is even more time con-
suming and moving mesh methods are extremely
expensive.
• Physics is modified according to the numerical
method and not the way around.
![Page 7: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/7.jpg)
Introduction
• Radial basis functions: φ : IR+ → IR, ‖ ‖ Euclidian
norm of IRd
Φ(x) ≡ φ(‖ ‖) : IRd → IR
• x1, ..., xN ∈ Ω ⊂ IRd, set of nodes. RBF inter-
polant:
s(x, ε) =N∑
j=1
λiφ(‖x − xj‖, ε) + pn(x)
• Interpolation conditions:
s(xi, ε) = u(xi), i = 1, ..., N
![Page 8: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/8.jpg)
Introduction
• No grid is needed to built the RBF interpolant.
![Page 9: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/9.jpg)
Introduction
• No grid is needed to built the RBF interpolant.
• The fact that the RBF depends on the Eu-
clidian norm, implies the Gramm matrix has the
same complexity in 2D and 3D.
![Page 10: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/10.jpg)
Introduction
• No grid is needed to built the RBF interpolant.
• The fact that the RBF depends on the Eu-
clidian norm, implies the Gramm matrix has the
same complexity in 2D and 3D.
• Partial derivatives can be approximated in a
highly accurate way by using RBF.
![Page 11: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/11.jpg)
Introduction
• No grid is needed to built the RBF interpolant.
• The fact that the RBF depends on the Eu-
clidian norm, implies the Gramm matrix has the
same complexity in 2D and 3D.
• Partial derivatives can be approximated in a
highly accurate way by using RBF.
• To solve PDE, several methods have appeared:
![Page 12: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/12.jpg)
Introduction
• No grid is needed to built the RBF interpolant.
• The fact that the RBF depends on the Eu-
clidian norm, implies the Gramm matrix has the
same complexity in 2D and 3D.
• Partial derivatives can be approximated in a
highly accurate way by using RBF.
• To solve PDE, several methods have appeared:
– Colocation techniques, (un-symmetric and
symetric)
– Moving last square methods with RBF ker-
nels
![Page 13: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/13.jpg)
The problem
RBF collocation methods suffer from a bad condi-
tioning as the number of nodes increases. Strate-
gies to face this problem:
1. Domain decomposition methods.
![Page 14: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/14.jpg)
The problem
RBF collocation methods suffer from a bad condi-
tioning as the number of nodes increases. Strate-
gies to face this problem:
1. Domain decomposition methods.
2. Node and shape parameter adaptive algorithms,
and
![Page 15: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/15.jpg)
The problem
RBF collocation methods suffer from a bad condi-
tioning as the number of nodes increases. Strate-
gies to face this problem:
1. Domain decomposition methods.
2. Node and shape parameter adaptive algorithms,
and
3. Preconditioning thechniques.
![Page 16: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/16.jpg)
The problem
RBF collocation methods suffer from a bad condi-
tioning as the number of nodes increases. Strate-
gies to face this problem:
1. Domain decomposition methods.
2. Node and shape parameter adaptive algorithms,
and
3. Preconditioning thechniques.
In this talk we shall be concerned with points (1)
and (2).
![Page 17: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/17.jpg)
Outline of the talk
Up to our knowledge, no algorithm has appeared
which combines Domain decomposition techniques
with node adaptive methods. In this talk:
![Page 18: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/18.jpg)
Outline of the talk
Up to our knowledge, no algorithm has appeared
which combines Domain decomposition techniques
with node adaptive methods. In this talk:
1. Review Domain decomposition methods.
![Page 19: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/19.jpg)
Outline of the talk
Up to our knowledge, no algorithm has appeared
which combines Domain decomposition techniques
with node adaptive methods. In this talk:
1. Review Domain decomposition methods.
2. Formulate a Node and shape parameter addaptive
algorithms, and
![Page 20: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/20.jpg)
Outline of the talk
Up to our knowledge, no algorithm has appeared
which combines Domain decomposition techniques
with node adaptive methods. In this talk:
1. Review Domain decomposition methods.
2. Formulate a Node and shape parameter addaptive
algorithms, and
3. Formulate a new algorithm which combines these
techniques .
![Page 21: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/21.jpg)
Outline of the talk
Up to our knowledge, no algorithm has appeared
which combines Domain decomposition techniques
with node adaptive methods. In this talk:
1. Review Domain decomposition methods.
2. Formulate a Node and shape parameter addaptive
algorithms, and
3. Formulate a new algorithm which combines these
techniques .
More precisely, we have the following objective.
![Page 22: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/22.jpg)
Objective:
• Build a numerical scheme based on sets of non
uniform node distributions, rather than on Carte-
sian grids.
![Page 23: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/23.jpg)
Objective:
• Build a numerical scheme based on sets of non
uniform node distributions, rather than on Carte-
sian grids.
• Build a node adaptive thinning RBF method for
PDE’s based on scattered data.
![Page 24: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/24.jpg)
Objective:
• Build a numerical scheme based on sets of non
uniform node distributions, rather than on Carte-
sian grids.
• Build a node adaptive thinning RBF method for
PDE’s based on scattered data.
• Combine a domain decomposition algorithm with
the node adaptive thinning technique to solve the
PDEs problems.
![Page 25: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/25.jpg)
Objective:
• Build a numerical scheme based on sets of non
uniform node distributions, rather than on Carte-
sian grids.
• Build a node adaptive thinning RBF method for
PDE’s based on scattered data.
• Combine a domain decomposition algorithm with
the node adaptive thinning technique to solve the
PDEs problems.
• Numerical examples will be presented for a Pois-
son and a stationary convection diffusion prob-
lems in 2D.
![Page 26: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/26.jpg)
RBF Domain Decomposition Methods
Several Domain Decomposition Methods for RBFs
collocation techniques have been recently formu-
lated:
• For stationary PDE’s, [5,18,7,19,8,10,9,13].
![Page 27: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/27.jpg)
RBF Domain Decomposition Methods
Several Domain Decomposition Methods for RBFs
collocation techniques have been recently formu-
lated:
• For stationary PDE’s, [5,18,7,19,8,10,9,13].
• Evolutionary PDE’s, [15, 3].
![Page 28: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/28.jpg)
RBF Domain Decomposition Methods
Several Domain Decomposition Methods for RBFs
collocation techniques have been recently formu-
lated:
• For stationary PDE’s, [5,18,7,19,8,10,9,13].
• Evolutionary PDE’s, [15, 3].
• In Zhang et. al. [21], a convergence prove is
given for Schwarz additive and multiplicative
methods.
![Page 29: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/29.jpg)
RBF Domain Decomposition Methods
Several Domain Decomposition Methods for RBFs
collocation techniques have been recently formu-
lated:
• For stationary PDE’s, [5,18,7,19,8,10,9,13].
• Evolutionary PDE’s, [15, 3].
• In Zhang et. al. [21], a convergence prove is
given for Schwarz additive and multiplicative
methods.
These methods have ben formulated in 2D, both
for linear and non linear problems.
![Page 30: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/30.jpg)
RBF Domain Decomposition Methods
Dispite these considerable advances, several lim-
itations and open problems remains to be solved
• Except for Wong et al. [15], which uses a
multizone formulation for a non-regular node
distribution, all these works has been formulated
for Cartesian Grids.
![Page 31: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/31.jpg)
RBF Domain Decomposition Methods
Dispite these considerable advances, several lim-
itations and open problems remains to be solved
• Except for Wong et al. [15], which uses a
multizone formulation for a non-regular node
distribution, all these works has been formulated
for Cartesian Grids.
• None of the former algorithms do combine adap-
tive techniques with DD methods.
![Page 32: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/32.jpg)
RBF Domain Decomposition Methods
Dispite these considerable advances, several lim-
itations and open problems remains to be solved
• Except for Wong et al. [15], which uses a
multizone formulation for a non-regular node
distribution, all these works has been formulated
for Cartesian Grids.
• None of the former algorithms do combine adap-
tive techniques with DD methods.
• Moreover, the number of sub domains remains
fixed during the iteration process.
![Page 33: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/33.jpg)
Schwarz Methods for RBF-PDE
All these methods are based on Schwarz approach,
Zhou et. al. [19]:
![Page 34: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/34.jpg)
Schwarz Methods for RBF-PDE
All these methods are based on Schwarz approach,
Zhou et. al. [19]:
• Schwarz additive method: Easer to parallelize
than the multiplicative version.
![Page 35: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/35.jpg)
Schwarz Methods for RBF-PDE
All these methods are based on Schwarz approach,
Zhou et. al. [19]:
• Schwarz additive method: Easer to parallelize
than the multiplicative version.
• Schwarz multiplicative method. Twice faster
than the additive version.
![Page 36: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/36.jpg)
Schwarz Methods for RBF-PDE
All these methods are based on Schwarz approach,
Zhou et. al. [19]:
• Schwarz additive method: Easer to parallelize
than the multiplicative version.
• Schwarz multiplicative method. Twice faster
than the additive version.
In this talk we shall consider the multiplicative
Schwarz method in the context of a non uniform
data distribution.
![Page 37: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/37.jpg)
Schwarz Methods for RBF-PDE
DD-RBF Schwarz Ovelapping Methods. Generic el-
liptic PDE problem:
Lu = f in Ω ⊂ IRd,
Bu = g on ∂Ω,
In Kansa’s approach, the exact solution u(x) of
the problem is approximated by the expansion
u(x) =N∑
j=1
λjφ(‖x − xj‖) + p(x), x ∈ IRd,
where p ∈ πdm is a polynomial of degree at most
m in d-dimensions, which depend on the RBF.
![Page 38: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/38.jpg)
Schwarz Methods for RBF-PDE
Some classical RBF:
Multiquadric (MQ) φ(r) =√
r2 + c2
Inverse Multiquadric (IMQ) φ(r) = 1/√
r2 + c2
Gaussian (GA) φ(r) = e−(cr2)
Thin-Plate Splines (TPS) φ(r) = rmlogr, m = 2, 4, 6, . . .Smooth Splines (SS) φ(r) = rm, m = 1, 3, 4, . . .
The collocation technique applied to the former
problem, gives us the linear system:
AΛ = F,
![Page 39: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/39.jpg)
Schwarz Methods for RBF-PDE
where
• F = [f g]T , A = [LΦa BΦb]T ,
– Λ ∈ IRN ,
– Φa ∈ IRni×N ,
– Φb ∈ IRnf×N , N = ni + nf .
• The entries of the matrix A are
– LΦa = Lφ(‖xi − xj‖), i = 1, . . . , ni and
– BΦb = Bφ(‖xi − xj‖), i = ni + 1, . . . , N ,
j = 1, . . . , N .
![Page 40: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/40.jpg)
RBF Schwarz Methods: Artificial boundaries are updatedfrom the boundary vector F i.
Λn+1i = Λn
i + A−1i (F i − AiΛ
ni ), n = 0, 1, 2, ...
BUT ui = HiΛi i = 1, 2, where Hi = (φ1, ..., φni)
un+1i = un
i + HiA−1i (F i − AiH
−1i un
i ), n = 0, 1, 2, ...
for i = 1, 2.
![Page 41: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/41.jpg)
Schwarz Methods for RBF-PDE
• RBF additive version: Artificial boundaries are
updated from the results of the nth step.
un+1i = un
i + HiA−1i (F n
i − AiH−1i un
i ), n = 0, 1, 2, ...
for i = 1, 2.
• RBF multiplicative version: Artificial boundaries
updated from most recent neighboring subdo-
mains. For n = 0, 1, 2, ...
un+1/21 = un
i + H1A−11 (F n
1 − A1H−11 un
1 )
un+12 = u
n+1/22 + H2A
−12 (F
n+1/22 − A2H
−12 u
n+1/22 ),
![Page 42: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/42.jpg)
Adaptive RBF Collocation Method
This algorithm combines Behrens et al. refine-
ment method with a quad-tree type technique.
• Use unsymmetric collocation to solve the PDE.
![Page 43: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/43.jpg)
Adaptive RBF Collocation Method
This algorithm combines Behrens et al. refine-
ment method with a quad-tree type technique.
• Use unsymmetric collocation to solve the PDE.
• Let Ξ be the initial set of nodes. For each node
x ∈ Ξ select a set of neighboring nodes Nx\x ∈ Ξ.
![Page 44: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/44.jpg)
Adaptive RBF Collocation Method
This algorithm combines Behrens et al. refine-
ment method with a quad-tree type technique.
• Use unsymmetric collocation to solve the PDE.
• Let Ξ be the initial set of nodes. For each node
x ∈ Ξ select a set of neighboring nodes Nx\x ∈ Ξ.
• Use a quadtree type technique to locate the neigh-
boring nodes.
![Page 45: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/45.jpg)
Adaptive RBF Collocation Method
This algorithm combines Behrens et al. refine-
ment method with a quad-tree type technique.
• Use unsymmetric collocation to solve the PDE.
• Let Ξ be the initial set of nodes. For each node
x ∈ Ξ select a set of neighboring nodes Nx\x ∈ Ξ.
• Use a quadtree type technique to locate the neigh-
boring nodes.
• Construct a local TPS interpolant r2i log(ri)+p1:
Iu(x) based on Nx\x
![Page 46: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/46.jpg)
Adaptive RBF Collocation Method
• Let u(x) the RBF numerical approximation of
PDE and Iu(x) the local interpolant. Define
the error indicator
η(x) = |u(x) − Iu(x)|, (1)
![Page 47: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/47.jpg)
Adaptive RBF Collocation Method
• Let u(x) the RBF numerical approximation of
PDE and Iu(x) the local interpolant. Define
the error indicator
η(x) = |u(x) − Iu(x)|, (1)
• For all x If η(x) > θr refine. If η(x) < θc remove.
![Page 48: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/48.jpg)
Adaptive RBF Collocation Method
• Let u(x) the RBF numerical approximation of
PDE and Iu(x) the local interpolant. Define
the error indicator
η(x) = |u(x) − Iu(x)|, (1)
• For all x If η(x) > θr refine. If η(x) < θc remove.
• Node insertion/remotion is performed by using
the quadtree algorithm. For each cell marked
to be refined, four nodes are inserted, following
the rule: 2:1.
![Page 49: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/49.jpg)
![Page 50: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/50.jpg)
RBF Adaptive Methods
• Behrens et al. method uses a Delauny triangu-
lation, our approach a quadtree technique.
![Page 51: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/51.jpg)
RBF Adaptive Methods
• Behrens et al. method uses a Delauny triangu-
lation, our approach a quadtree technique.
• Quadtree technique can be replaced by octree
for 3D problems, thus extending the algorithm.
![Page 52: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/52.jpg)
RBF Adaptive Methods
• Behrens et al. method uses a Delauny triangu-
lation, our approach a quadtree technique.
• Quadtree technique can be replaced by octree
for 3D problems, thus extending the algorithm.
• In 1D several adaptive methods have appeared
in the literature.
![Page 53: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/53.jpg)
RBF Adaptive Methods
• Behrens et al. method uses a Delauny triangu-
lation, our approach a quadtree technique.
• Quadtree technique can be replaced by octree
for 3D problems, thus extending the algorithm.
• In 1D several adaptive methods have appeared
in the literature.
In 2D and for scattered data we find the following
approaches:
![Page 54: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/54.jpg)
RBF Adaptive Methods
• The method presented in this talk is based on
a local error estimate and a quadtree algorithm in
order to perform the knot insertion/remotion
of nodes.
![Page 55: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/55.jpg)
RBF Adaptive Methods
• The method presented in this talk is based on
a local error estimate and a quadtree algorithm in
order to perform the knot insertion/remotion
of nodes.
• Driscoll et al., [4] formulated a method based
on a global error estimate and a quadtree tech-
nique to perform the adaptive knot strategy to
build their algorithm.
![Page 56: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/56.jpg)
RBF Adaptive Methods
• The method presented in this talk is based on
a local error estimate and a quadtree algorithm in
order to perform the knot insertion/remotion
of nodes.
• Driscoll et al., [4] formulated a method based
on a global error estimate and a quadtree tech-
nique to perform the adaptive knot strategy to
build their algorithm.
• Moreover, in Pereyra et al., [20] a global op-
timization method is formulated to solve the
PDE, which adapts the nodes location and the
shape parameters simultaneously.
![Page 57: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/57.jpg)
Local node refinement and DomainDecomposition Algorithm:
• The following algorithm, is based on a Multi-
quadric collocation method.
![Page 58: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/58.jpg)
Local node refinement and DomainDecomposition Algorithm:
• The following algorithm, is based on a Multi-
quadric collocation method.
• Numerical experiments with thin plate splines
r4log(r) where performed and indicated that
multiquadrics are faster for a given error.
![Page 59: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/59.jpg)
Local node refinement and DomainDecomposition Algorithm:
• The following algorithm, is based on a Multi-
quadric collocation method.
• Numerical experiments with thin plate splines
r4log(r) where performed and indicated that
multiquadrics are faster for a given error.
• The local error η(x) is define by a thin plate
spline RBF: r2log(r) + x + y + 1.
![Page 60: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/60.jpg)
Local node refinement and DomainDecomposition Algorithm:
• The following algorithm, is based on a Multi-
quadric collocation method.
• Numerical experiments with thin plate splines
r4log(r) where performed and indicated that
multiquadrics are faster for a given error.
• The local error η(x) is define by a thin plate
spline RBF: r2log(r) + x + y + 1.
• An initial value of the shape parameter cini is
given, and it is actualized at each iteration by
cnewj = cold
j /2.
![Page 61: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/61.jpg)
Local node refinement and DomainDecomposition Algorithm:
• A recursive coordinate bisecction is use to form
the subdomains.
![Page 62: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/62.jpg)
Local node refinement and DomainDecomposition Algorithm:
• A recursive coordinate bisecction is use to form
the subdomains.
• A given number Nmax is used to determine
whether the subdomain should be divided or not.
![Page 63: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/63.jpg)
Local node refinement and DomainDecomposition Algorithm:
• A recursive coordinate bisecction is use to form
the subdomains.
• A given number Nmax is used to determine
whether the subdomain should be divided or not.
• The number levelini determines whether a given
node is refined or not: a node can be removed
only if its level in the tree is greater than levelini
![Page 64: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/64.jpg)
Local node refinement and DomainDecomposition Algorithm:
• A recursive coordinate bisecction is use to form
the subdomains.
• A given number Nmax is used to determine
whether the subdomain should be divided or not.
• The number levelini determines whether a given
node is refined or not: a node can be removed
only if its level in the tree is greater than levelini
• The stopping criteria for the Schuarz multiplica-
tive algorithm is given by: ‖uk − uk−1‖ ≤ 0.001,
where k denotes the iteration of the DDM
method.
![Page 65: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/65.jpg)
Local node refinement and DomainDecomposition Algorithm:
1. Define The variables: levelini, cini, θr, θc, Nmax.
![Page 66: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/66.jpg)
Local node refinement and DomainDecomposition Algorithm:
1. Define The variables: levelini, cini, θr, θc, Nmax.
2. Built the initial tree and refine two times in the
boundary
![Page 67: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/67.jpg)
Local node refinement and DomainDecomposition Algorithm:
1. Define The variables: levelini, cini, θr, θc, Nmax.
2. Built the initial tree and refine two times in the
boundary
3. While maxη(x) > θr or iterations <50
![Page 68: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/68.jpg)
Local node refinement and DomainDecomposition Algorithm:
1. Define The variables: levelini, cini, θr, θc, Nmax.
2. Built the initial tree and refine two times in the
boundary
3. While maxη(x) > θr or iterations <50
4. Partition Ω by recursive coordinate bisecction
and form the overlaping zones.
![Page 69: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/69.jpg)
Local node refinement and DomainDecomposition Algorithm:
1. Define The variables: levelini, cini, θr, θc, Nmax.
2. Built the initial tree and refine two times in the
boundary
3. While maxη(x) > θr or iterations <50
4. Partition Ω by recursive coordinate bisecction
and form the overlaping zones.
5. Solve PDE by multiplicative Schwarz algorithm.
![Page 70: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/70.jpg)
Local node refinement and DomainDecomposition Algorithm:
1. Define The variables: levelini, cini, θr, θc, Nmax.
2. Built the initial tree and refine two times in the
boundary
3. While maxη(x) > θr or iterations <50
4. Partition Ω by recursive coordinate bisecction
and form the overlaping zones.
5. Solve PDE by multiplicative Schwarz algorithm.
6. Join the solution obtained in each Ωi to built the
soution in Ω.
![Page 71: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/71.jpg)
Local node refinement and DomainDecomposition Algorithm:
1. Define The variables: levelini, cini, θr, θc, Nmax.
2. Built the initial tree and refine two times in the
boundary
3. While maxη(x) > θr or iterations <50
4. Partition Ω by recursive coordinate bisecction
and form the overlaping zones.
5. Solve PDE by multiplicative Schwarz algorithm.
6. Join the solution obtained in each Ωi to built the
soution in Ω.
7. Perform the local refinement of nodes. End While.
![Page 72: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/72.jpg)
Local node refinement and DomainDecomposition Algorithm:
1. The stopping criteria: there are no more nodes
to insert or number of iterations exceeded.
![Page 73: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/73.jpg)
Local node refinement and DomainDecomposition Algorithm:
1. The stopping criteria: there are no more nodes
to insert or number of iterations exceeded.
2. Overlapping zones are built by using the quadtree
structure: The more level on the tree the more
traslapping nodes.
RefinementLevel Expansion5 - 6 26 - 10 311 - 14 4
Moreover: the more refinement level, the greater
gradient of the solution.
![Page 74: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/74.jpg)
Local node refinement and DomainDecomposition Algorithm:
1. To join the solution of each sub-domain, a node
is index both to the domain and to the sub-
domain.
![Page 75: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/75.jpg)
Local node refinement and DomainDecomposition Algorithm:
1. To join the solution of each sub-domain, a node
is index both to the domain and to the sub-
domain.
2. Given a sub-domain Ωi: if each node of all other
sub-domains do not belongs to Ωi then it is in-
cluded in Ωi and otherwise discarded.
![Page 76: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/76.jpg)
Local node refinement and DomainDecomposition Algorithm:
1. To join the solution of each sub-domain, a node
is index both to the domain and to the sub-
domain.
2. Given a sub-domain Ωi: if each node of all other
sub-domains do not belongs to Ωi then it is in-
cluded in Ωi and otherwise discarded.
3. Point (7) corresponds to Schwarz and local thin-
ing perviously seen.
![Page 77: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/77.jpg)
Numerical Results:
Poisson Problem:
∂2u
∂x2+
∂2u
∂y2= f en Ω ⊂ R2, (2)
Convection Diffusion Problem:
β∇2u + v · ∇u = 0 x ∈ Ω ⊂ IR2, (3)
in both problems Dirichlet boundary conditions are
considered.
![Page 78: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/78.jpg)
Poisson Equation: As iteration increases: error tends to zeroand the number of domains increases
Iter Party N e_rms e_inf0 2 2152 2.669998924940 13.3818063379121 2 2884 0.764945619834 3.0789971096302 4 3589 0.034990848404 0.1083082937013 4 5344 0.003880880328 0.0105377659304 8 7252 0.003988968225 0.0102399888965 8 8548 0.002610737155 0.0068887014006 8 8686 0.002520146497 0.0068920291977 8 8728 0.002505314335 0.006890463882
Error in each sub-domain:
[0] rms = 0.0025494 e_inf = 0.006890[1] rms = 0.0025529 e_inf = 0.003909[2] rms = 0.0025491 e_inf = 0.006890[3] rms = 0.0027670 e_inf = 0.004143[4] rms = 0.0025112 e_inf = 0.003887[5] rms = 0.0023968 e_inf = 0.006883[6] rms = 0.0023192 e_inf = 0.003637[7] rms = 0.0023970 e_inf = 0.006883
![Page 79: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/79.jpg)
![Page 80: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/80.jpg)
![Page 81: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/81.jpg)
![Page 82: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/82.jpg)
![Page 83: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/83.jpg)
![Page 84: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/84.jpg)
Convection Diffusion Equation: As iteration increases: errortends to zero and the number of domains increases. Pe = 1000.0
Iter Party N e_rms e_inf0 2 2152 0.055968003702 0.3647553841261 5 4714 0.006318200112 0.0824869612412 5 4909 0.008948974295 0.0811974179723 10 7609 0.012955619297 0.0526049472264 10 7723 0.012924100339 0.0504036994175 10 7744 0.012912038660 0.0504261940576 10 7747 0.012910525584 0.050441756859
Error in each sub-domain:[0] rms = 0.0182151 e_inf = 0.050442[1] rms = 0.0161961 e_inf = 0.045017[2] rms = 0.0167162 e_inf = 0.044046[3] rms = 0.0158089 e_inf = 0.044153[4] rms = 0.0166283 e_inf = 0.044033[5] rms = 0.0152495 e_inf = 0.046928[6] rms = 0.0004666 e_inf = 0.001923[7] rms = 0.0153632 e_inf = 0.043525[8] rms = 0.0142846 e_inf = 0.047231[9] rms = 0.0001769 e_inf = 0.001006
![Page 85: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/85.jpg)
![Page 86: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/86.jpg)
![Page 87: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/87.jpg)
![Page 88: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/88.jpg)
![Page 89: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/89.jpg)
![Page 90: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/90.jpg)
Node adaptive scheme versus non-adaptive with DD:
• Maximum error: 4 × 10−2.
• Graph in a loglog scale, in the x−axis number of nodesand the y−axis time in seconds.
• The node adaptive scheme with domain decompositionmethod requires only an 27% of the time required of thethe non-adaptive scheme.
![Page 91: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/91.jpg)
Conclusions and Further Work
• Based on a quadtree algorithm and a RBF lo-
cal error estimate, a domain decomposition node
adaptive algorithm has been presented.
![Page 92: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/92.jpg)
Conclusions and Further Work
• Based on a quadtree algorithm and a RBF lo-
cal error estimate, a domain decomposition node
adaptive algorithm has been presented.
• The number of subdomaines are dynamically adapted
as the nodes are refined.
![Page 93: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/93.jpg)
Conclusions and Further Work
• Based on a quadtree algorithm and a RBF lo-
cal error estimate, a domain decomposition node
adaptive algorithm has been presented.
• The number of subdomaines are dynamically adapted
as the nodes are refined.
• Numerical experiments on an elliptic and a sta-
tionary convection diffusion problem suggests
that the algorithm can be applied to a large amount
of data.
![Page 94: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/94.jpg)
Conclusions and Further Work
• As far as to the authors knowledge this is the
first algorithm that combines an adaptive tech-
nique with a domain decomposition algorithm
for scattered data.
![Page 95: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/95.jpg)
Conclusions and Further Work
• As far as to the authors knowledge this is the
first algorithm that combines an adaptive tech-
nique with a domain decomposition algorithm
for scattered data.
• The method presented in this talk has not
been proved in parallel machines.
• The coordinate bisection algorithm is only a
first attempt to partitioning the domain, more
flexible methods should be considered.
Thank you.
![Page 96: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/96.jpg)
References:
[1] J. Behrens and A. Iske. Grid-free adaptive semi-lagrangian ad-vection using radial basis functions. Computers and Mathematics withApplications, 43(3- 5):319327, 2002.
[2] J. Behrens, A. Iske, and M. Kaser. Adaptive Meshfree Methodof Backward Characteristics for Nonlinear Transport Equations, pages2136. Springer Verlag, 2003.
[3] Phani P. Chinchapatnam, K. Djidjeli, and Prasanth B. Nair. Domaindecomposition for time-dependent problems using radial based mesh-less methods. Numerical Methods for Partial Differential Equations,23(1):3859, 2007.
[4] T.A. Driscoll and A.R.H. Heryudono. Adaptive residual subsam-pling methods for radial basis function interpolation and collocationproblems. Submited to Comp. Math. with Applications.
[5] M.R. Dubal. Domain decomposition and local refinement for mul-tiquadric approximations. I: Second-order equations in one-dimension.. Appl. Sci. Comp., 1(1):146171, 1994.
[6] Y. C. Hon. Multiquadric collocation method with adaptive techniquefor problems with boundary layer. Appl. Sci. Comput., 6(3):17184,1999.
![Page 97: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/97.jpg)
[7] E. J. Kansa and Y. C. Hon. Circumventing the ill-conditioningproblem with multiquadric radial basis functions: Applications to el-liptic partial differential equations. Computers and Mathematics withApplications, 39(78):123 137, 2000.
[8] Jichun Li and C.S. Chen. Some observations on unsymemetricradial basis function collocation methods for convection-diffusion prob-lems. International Journal for Numerical Methods in Engineering,57(8):10851094, 2003.
[9] Jichun Li and Y. C. Hon. Domain decomposition for radial basismeshless methods. Numerical Methods for Partial Differential Equa-tions, 20(3):450 462, 2004.
[10] Leevan Ling and E. J. Kansa. Preconditioning for radial basis func-tions with domain decomposition methods. Mathematical and Com-puter Modelling, 40(13):14131427, 2004.
[11] Leevan Ling and Manfred R. Trummer. Adaptive multiquadriccollocation for boundary layer problem. Journal of Computational andApplied Mathematics, 188(2):265282, 2006.
[12] Jose Antonio Munoz-Gomez, Pedro Gonzalez-Casanova, and Gus-tavo Rodrguez-Gomez. Adaptive node refinement collocation methodfor partial differential equations. In ENC06: Proceedings of the Sev-enth Mexican International Conference on Computer Science, pages7080, Washington, DC, USA, September 2006. IEEE Computer Soci-ety.
[13] Jose Antonio Munoz-Gomez, Pedro Gonzalez-Casanova, and Gus-tavo Rodrguez-Gomez. Domain decomposition by radial basis functions
![Page 98: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/98.jpg)
for time dependent partial differential equations. In ACST06: Proceed-ings of the IASTED International Conference on Advances in ComputerScience and Technology, pages 105109, Anaheim, CA, USA, January2006. ACTA Press.
[14] Scott A. Sarra. Adaptive radial basis function methods for timedependent partial differential equation. Applied Numerical Mathemat-ics, 54(1):7994, 2005.
[15] A. S. M.Wong, Y. C. Hon, T. S. Li, S. L. Chung, and E. J. Kansa.Multizone decomposition for simulation of time-dependent problemsusing the multiquadric schem. Computers and Mathematics with Ap-plications, 37(8):23 43, 1999.
[16] Zongmin Wu. Dynamically knots setting in meshless method forsolving time dependent propagations equation. Computer Methods inApplied Mechanics and Engineering, 193(12-14):12211229, 2004.
[17] Zongmin Wu. Dynamical knot and shape parameter setting forsimulating shock wave by using multi-quadric quasi-interpolation. En-gineering Analysis with Boundary Elements, 29(4):354358, 2005.
[18] Zongmin Wu and Y.C. Hon. Additive schwarz domain decompo-sition with radial basis approximation. Int. J. Appl. Math., 4(1):8198,2000.
[19] X. Zhou, Y. C. Hon, and Jichun Li. Overlapping domain decom-position method by radial basis functions. Applied Numerical Mathe-matics, 44(1 2):241255, 2003.
![Page 99: Funciones Radiales y M´etodos Adaptivos Pedro Gonz´alez ... › smc-2007 › Archivos › PGC.pdf · Outline of the talk Up to our knowledge, no algorithm has appeared which combines](https://reader034.vdocumento.com/reader034/viewer/2022042322/5f0bf5e27e708231d433120e/html5/thumbnails/99.jpg)
[20] V. Pereyra , G. Scherer and P. Gonzlez Casanova, Radial FunctionCollocation Solution of Partial Differential Equations in Irregular Do-mains, to appear in: International Journal of Computing Science andMathematics, to appear, (2007).
[21] Yunxin Zhang , Yongji Tan, Convergence of general meshlessSchwarz method using radial basis functions, Applied Numerical Math-ematics 56 (2006) 916936.