Keywords: obstacle problem, parallel algorithm, synchronous method, asynchronous method, Schwarz alternating method, constrained mechanical structures.

The obstacle problem occurs in many applications such as mechanics, free boundary problems and financial derivatives. In the present study we concentrate mainly on the obstacle problem occurring in civil engineering computing. The problem consists of solving a time dependant nonlinear boundary value problem in which the displacement of the mechanical structure subjected to external strain satisfy an imposed constraint. The previous evolution equation is solved numerically by considering a time marching implicit scheme, where at each time step a stationary nonlinear problem is solved. For each stationary obstacle problem, we consider here a multi-valued formulation taking into account the constraint exercised on the displacement.

The Euler implicit time marching scheme has been used for the discretization of the evolution part. Besides, the domain is discretized with a uniform mesh and for the spatial part of the problem, a finite difference method is used. Thus, the numerical solution consists of solving a large linear algebraic system at each time step. So, it is necessary to use parallel iterative methods.

The solution of the algebraic system is carried out with the parallel projected Schwarz alternating method; in Schwarz alternating method the subdomains overlap each other. The parallel iterative scheme of computation can be synchronous or asynchronous. In the asynchronous case, computations are carried out in parallel without order nor synchronization, so processors go at their own pace according to their intrinsic characteristics and computational load. The use of an appropriate spatial discretization scheme leads to very interesting properties of the matrices to invert, ensuring the convergence of the parallel iterative synchronous and more generally asynchronous algorithms [1,2].

The algorithms are implemented using Fortran 90 language. The parallelisation is carried out with MPI facilities according to the SPMD paradigm on the Grid'5000 platform, a distributed and heterogeneous architecture.

We have used up to 128 machines located in up to two or three distant sites. Results show that all asynchronous schemes of computation scale better than the synchronous ones, as a result of less sensitivity to granularity, network bandwidth, latency and load unbalancing issues. Asynchronous schemes are more adapted to the heterogeneous and distant distributed clusters than the synchronous ones.

1

J. Miellou, P. Spiteri, "Un critère de convergence pour des méthodes générales de point fixe", M2AN, 19, 645-669, 1985.

2

J. Miellou, D. El Baz, P. Spiteri, "A new class of asynchronous iterative algorithms with order interval", Mathematics of Computation, 67, 221, 237-255, 1998. doi:10.1090/S0025-5718-98-00885-0

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £130 +P&P)