Introduction to Parallel Computing using MPI

Math 700 - Special Topics in Applied and Numerical Mathematics

Matthias K. Gobbert, Susan E. Minkoff, and Madhu Nayakkankuppam

Fall 2001 - Project Presentations

This page can be reached via my homepage at http://www.math.umbc.edu/~gobbert.

Program for Day 1

Tuesday, December 11, 2001, 04:00-05:15 p.m., MP 401

04:05-04:20
A Parallel Divide-Conquer Sorting Algorithm and its Implementation
Qinghong He
A parallel sorting algorithm for the distributed computation of a large integer array is presented based on the divide-conquer approach. The algorithm includes four steps: (1) select a pivot; (2) send all numbers below the pivot to one set of processors, and all numbers above the pivot to the other set of processors; (3) recurse on the above steps on each of the two subgroups of processors; (4) sort the numbers internally on the processors after they get to the right group. Using only log p (p is the number of processes) rounds of regular all-to-all personalized communication, the algorithm takes advantage of the topological properties of a hypercube and yields very good load balancing with virtually no overhead. It has been shown that such algorithm has computational complexity given by O(n/p log (n/p)) and communication complexity given by O(n/p log p + (log p)²) on average, where n is the array size and p is the number of processors. Experimental results indicate this algorithm is efficient and scalable.
Faculty mentor: Susan E. Minkoff
PDF-file of the report.
04:20-04:35
Two-Dimensional Decomposition of Game of Life using MPI Cartesian Topology
Naiqian Zhu
In MPI, a topology is a mechanism for associating different addressing schemes with the processes belonging to a group. In this project, the popular John Conway's Game of Life program is parallelized by MPI Cartesian topology. Game of Life is one example of a cellular automaton, which is any system in which rules are applied to cells and their neighbors in a regular grid. The project divides the game of life simulation grids among processors using a two-dimensional decomposition. MPI Cartesian topology functions MPI_Dims_create, MPI_Cart_create, MPI_Cart_shift, MPI_Cart_coords and MPI derived types are implemented in the program.
Faculty mentor: Susan E. Minkoff
PDF-file of the report.
04:35-04:50
An Explicit Finite Difference Method for a Parabolic Test Problem
Ana Maria Soane
In this project we implemented a parallel finite difference algorithm for solving the heat equation using explicit Euler in time and centered differences in space. We used a 1-D decomposition of the global domain of the problem, with each process handling the computations on its part of the domain. An analysis of the results obtained is presented.
Faculty mentor: Matthias K. Gobbert
ps-file of the report.
04:50-05:05
A Parallel Interior-Point Method for Linear Programming
Dan Wang
A Linear Program (LP) is a problem that can be expressed as follows
```
           minimize    c' x
           subject to  A x = b
                       x >= 0
```
where x is the vector of variables to be solved for. Mehrotra's Predictor Corrector algorithm is one of the methods to find the solution of such a problem. In my project, I finished the parallel implementation of MPC method, which involves matrix-matrix multiplication, matrix-vector multiplication, and Cholesky decompostion. Finally, numerical results will be presented.
Faculty mentor: Madhu Nayakkankuppam
ps-file of the report.

Program for Day 2

Wednesday, December 12, 2001, 04:00-05:30 p.m., MP 401

04:05-04:20
Numerical Implementation of a Calcium Spark Model
Alexander L. Hanhart
Contraction in human heart cells is controlled by the release of calcium ions at calcium release units (CRUs) in the cell. Calcium concentration is described as a system of three nonlinear reaction-diffusion equations. The release of calcium, or calcium spark event, is modeled by a delta function in the forcing term. High resolution, 3D solutions are obtained using the standard Galerkin method with piecewise linear trial functions on quadrilateral elements. Memory and timing issues require that an efficient implimentation of such a numerical scheme involve some sort of parallization. A first step would be to decouple the equations and work on each independently.
Faculty mentor: Matthias K. Gobbert
ps-file of the report.
04:20-04:35
Parallel Implementation of the Discontinuous Galerkin Method for the Scalar Transport Equation
Samuel G. Webster
Solutions of the scalar hyperbolic transport equation in two spatial dimensions using a parallel implementation of the discontinuous Galerkin finite element method are examined. Advantages of the parallel implementation will be highlighted.
Faculty mentor: Matthias K. Gobbert
ps-file of the report.
04:35-04:50
Large-Scale Nonlinear Programming with Parallel Limited Memory Quasi-Newton Methods
Terence J. Sabaka
Sequential quadratic programming is a well established approach to the solution of nonlinear programming (NLP) problems. Large NLPs, resulting in large quadratic subproblems, become tractable when we combine limited memory quasi-Newton methods with parallelism. We discuss our preliminary implementation of such an algorithm, and illustrate its performance on a test NLP with 10,000 variables and 1,000 constraints. We also point out several directions for improvement and future work.
Faculty mentor: Madhu Nayakkankuppam
ps-file of the report.
04:50-05:05
Parallel Bundle Methods for Semidefinite Programming
Yevgen Tymofyeyev
Semidefinite programs with bounded primal feasible sets can be written as unconstrained eigenvalue optimization problems. This formulation, particularly amenable to the use of subgradient bundle methods, is an attractive alternative to interior-point methods for large-scale problems. We discuss a parallel implementation of such an algorithm and provide some preliminary numerical results.
Faculty mentor: Madhu Nayakkankuppam
ps-file of the report.
05:05-05:20
Coding a Finite Difference Method in Parallel
Alexandra L. Chaillou We consider the Poisson problem on the unit cube, and seek a solution using finite differences. We look at the linear system resulting from this method, and solve this system by the conjugate gradient method using the parallel library PETSc (Portable Extensible Toolkit for Scientific Computation).
Faculty mentor: Matthias K. Gobbert
ps-file of the report.