Plan of Investigation

We will investiagte two approaches:

1.

Application of MUMPS: Once the matrix is generated (and stored on disk perhaps) the matrix problem could be fed to an existing parallel direct sparse matrix code such as MUltifrontal Massively Parallel Solver (MUMPS). This should be a relatively easy job (at least if the most straight forward matrix format is used). Statistics could be gathered comparing the performance of this code on different architectures (eg. shared memory multi-processor, high performance cluster, poor network cluster...) and different sized problems. Some MPI coding may be needed, but the amount will be limited.

2.

Data Parallelization or Domain Decomposition: Using partitioning software such as METIS the grid can be partitioned to the processors. A picture of the mesh used in Figure 1, partitioned into 8 submeshes is shown in Figure 2.

  

Figure 2: The sphere mesh used in Figure 1 partitioned into 8 submeshes using METIS.

The matrix can then be constructed on each subgrid (but this will require significant communication unlike in the finite element case). Having computed the matrix in parallel, we can then implement a parallel matrix multiplication routine and hence fully parallelize the code. This will require significant investment of time to take care of renumbering and indexing the grid and unknowns at various times in the solution process.