you are here: Home Research lines Probabilistic Domain Decomposition

News

                                                                                                  

Contact

Email:
juan.acebron at iscte dot pt
Phone: (+351) 217 903 986

Address:

ISCTE-IUL
Av. Forças Armadas 1649-026. Lisboa.
Portugal

INESC-ID,
Rua Alves Redol,9 1000-029. Lisboa.
Portugal
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 (Maxwell-Vlasov, and  Poisson-Vlasov equations) and Fluid Dynamics (Navier-Stokes and other equations).

     Background

           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 space-time 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 suitably-generated 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