Probabilistic Domain Decomposition 
Development of new efficient algorithms
for High Performance Supercomputers based on probabilistic domain decomposition methods An algorithm
has been developed recently capable to numerically solve partial
differential equations (PDEs) by
probabilistically induced domain decomposition methods (PDD). This research was
funded by the Portuguese national Science Fundation (FCT) under the direction of J.A. Acebrón, entitled "New parallel numerical algorithms for current and future high performance supercomputers".This
project aimed at developing efficient numerical methods to solve a
number of partial differential equation problems, arising from
Engineering and Physics, in particular from Plasma Physics
(MaxwellVlasov, and PoissonVlasov equations) and Fluid Dynamics
(NavierStokes and other equations).
One of the most relevant methods in this field is that of Domain
Decomposition, which is well suited to handle multiscale and
multiphysics. In fact, accomplishing a domain decomposition is
considered one of the most successful strategies to solve PDEs problems
exploiting parallel architectures, since it is based on splitting the
original domain into as many subdomains as the available processors.
Then, a local solver is used, independently, on each subdomain. The
overall solution is finally reconstructed combining all such partial
results. However, due to the global nature of the typical PDEs problems,
realizing the aforementioned splitting requires interfacial
communication, across the internal (artificial) boundaries generated by
the splitting procedure. In practice, such a interfacial
communication entails an communication overhead, the heavier the more
processors are being used. Consequently, it may be possible that
no advantage could be obtained using more and more processors, hence
scalability itself is doubtful.
In the classical domain decomposition splitting the domain into any number of subdomains
to be solved in parallel induces an interfacial communication. A new type of domain decomposition based on probabilistic methods A new hybrid parallel numerical algorithm for solving parabolic and elliptic partial differential equations in any space dimension was investigated, capable of exploiting the best features of two well known strategies: domain decomposition method, and the Monte Carlo method. A domain decomposition approach has been used to split the given spacetime domain into as many subdomains as available processors. The solutions on the interfaces separating the subdomains, being unknown, are computed by interpolating on the nodal points where the solution is obtained probabilistically. Diagram showing the probabilistic domain decomposition (PDD) at work.
It is shown schematically how a 2D bounday value problem for a parabolic partial differential equation can be solved in practice using a PDD method. The probabilistic computation for nonlinear problems consists of evaluating averages on suitablygenerated branching stochastic processes, which play a role similar to that of random paths in linear problems. In contrast to the classical deterministic method, the probabilistic approach allows to compute the solution at single points internal to the domain, without the need for first generating a computational grid and solving the full problem. This fact is of paramount importance because, once the solution on the interfaces has been computed, the tasks of evaluating the solutions inside each subdomains turn out to be totally independent of one another, and thus can be assigned to an arbitrary number of processors without any intercommunication overhead. The probabilistic domain decomposition (PDD) allows to split the domain into independent subdomains
once the solution at the interfaces was previously computed. Selected publications
