WAVE_MPI
Parallel Solution of the 1D Wave Equation using MPI


WAVE_MPI is a FORTRAN90 program which solves the 1D wave equation in parallel, using MPI.

This program solves the 1D wave equation of the form:

        Utt = c^2 Uxx
      
over the spatial interval [X1,X2] and time interval [T1,T2], with initial conditions:
        U(X,T1)  = U_T1(X),
        Ut(X,T1) = UT_T1(X),
      
and boundary conditions of Dirichlet type:
        U(X1,T) = U_X1(T),
U(X2,T) = U_X2(T).
The value C represents the propagation speed of waves.

The program uses the finite difference method, and marches forward in time, solving for all the values of U at the next time step by using the values known at the previous two time steps.

Central differences may be used to approximate both the time and space derivatives in the original differential equation.

Thus, assuming we have available the approximated values of U at the current and previous times, we may write a discretized version of the wave equation as follows:

        Uxx(X,T) = ( U(X+dX,T   ) - 2 U(X,T) + U(X-dX,T,  ) ) / dX^2
        Utt(X,T) = ( U(X,   T+dT) - 2 U(X,T) + U(X,   T-dt) ) / dT^2
      
If we multiply the first term by C^2 and solve for the single unknown value U(X,T+dt), we have:
        U(X,T+dT) =        (     C^2 * dT^2 / dX^2 ) * U(X+dX,T)
                    +  2 * ( 1 - C^2 * dT^2 / dX^2 ) * U(X,   T)
                    +      (     C^2 * dT^2 / dX^2 ) * U(X-dX,T)
                    -                                  U(X,   T-dT)
      
(Equation to advance from time T to time T+dT, except for FIRST step!)

However, on the very first step, we only have the values of U for the initial time, but not for the previous time step. In that case, we use the initial condition information for dUdT which can be approximated by a central difference that involves U(X,T+dT) and U(X,T-dT):

        dU/dT(X,T) = ( U(X,T+dT) - U(X,T-dT) ) / ( 2 * dT )
      
and so we can estimate U(X,T-dT) as
        U(X,T-dT) = U(X,T+dT) - 2 * dT * dU/dT(X,T)
      
If we replace the "missing" value of U(X,T-dT) by the known values on the right hand side, we now have U(X,T+dT) on both sides of the equation, so we have to rearrange to get the formula we use for just the first time step:
        U(X,T+dT) =   1/2 * (     C^2 * dT^2 / dX^2 ) * U(X+dX,T)
                    +       ( 1 - C^2 * dT^2 / dX^2 ) * U(X,   T)
                    + 1/2 * (     C^2 * dT^2 / dX^2 ) * U(X-dX,T)
                    +  dT *                         dU/dT(X,   T   )
      
(Equation to advance from time T to time T+dT for FIRST step.)

It should be clear now that the quantity ALPHA = C * dT / dX will affect the stability of the calculation. If it is greater than 1, then the middle coefficient (1-C^2 dT^2 / dX^2) is negative, and the sum of the magnitudes of the three coefficients becomes unbounded.

We wish to use MPI in order to accelerate this computation. We use the method of domain decomposition - that is, we assume we have P MPI processes, we divide the original interval into P subintervals, and we expect each process to update the data associated with its subinterval.

However, to compute the estimated solution U(X,T+dT) at the next time step requires information about U(X-dX,T) and U(X+dX,T). When process ID tries to make these estimates, it will need one value from process ID-1, and one from process ID+1, before it can make all the updates. MPI allows the processes to communicate this information using messages.

At the end of the complete calculation, we wish to print a table of the solution at the final time. To do this in an organized fashion, we want each process to send its final result to the master process (with ID = 0). Once all the data has been collected, the master process prints it.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

WAVE_MPI is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version.

Related Data and Programs:

COMMUNICATOR_MPI, a FORTRAN90 program which creates new communicators involving a subset of initial set of MPI processes in the default communicator MPI_COMM_WORLD.

HEAT_MPI, a FORTRAN90 program which solves the 1D Time Dependent Heat Equation using MPI.

HELLO_MPI, a FORTRAN90 program which prints out "Hello, world!" using the MPI parallel programming environment.

MOAB, examples which illustrate the use of the MOAB job scheduler for a computer cluster.

MPI, FORTRAN90 programs which illustrate the use of the MPI application program interface for carrying out parallel computations in a distributed memory environment.

MPI_STUBS, a FORTRAN90 library which contains "stub" MPI routines, allowing a user to compile, load, and possibly run an MPI program on a serial machine.

MULTITASK_MPI, a FORTRAN90 program which demonstrates how to "multitask", that is, to execute several unrelated and distinct tasks simultaneously, using MPI for parallel execution.

PRIME_MPI, a FORTRAN90 program which counts the number of primes between 1 and N, using MPI for parallel execution.

QUAD_MPI, a FORTRAN90 program which approximates an integral using a quadrature rule, and carries out the computation in parallel using MPI.

RANDOM_MPI, a FORTRAN90 program which demonstrates one way to generate the same sequence of random numbers for both sequential execution and parallel execution under MPI.

RING_MPI, a FORTRAN90 program which uses the MPI parallel programming environment, and measures the time necessary to copy a set of data around a ring of processes.

SATISFY_MPI, a FORTRAN90 program which demonstrates, for a particular circuit, an exhaustive search for solutions of the circuit satisfiability problem, using MPI to carry out the calculation in parallel.

SEARCH_MPI, a FORTRAN90 program which searches integers between A and B for a value J such that F(J) = C, using MPI.

Reference:

  1. Geoffrey Fox, Mark Johnson, Gregory Lyzenga, Steve Otto, John Salmon, David Walker,
    Solving problems on concurrent Processors,
    Volume 1: General Techniques and Regular Problems,
    Prentice Hall, 1988,
    ISBN: 0-13-8230226,
    LC: QA76.5.F627.

Source Code:

Examples and Tests:

WAVE_FSU compiles and runs the program on the FSU HPC cluster.

WAVE_LOCAL compiles and runs the program on a local machine with multiple processors.

You can go up one level to the FORTRAN90 source codes.


Last revised on 17 November 2013.