Mathematical Sciences: Analysis of Parallel Solution Methods for Scientific Computation

点击翻译按钮获取中文摘要

9627071 Strikwerda The investigator improves, studies, and implements numerical methods for parallel and distributed computation. The project concentrates on parallel domain decomposition methods for incompressible viscous flow, implemented in a distributed environment and applying the methods to problems of significant interest. The investigator runs a domain decomposition code in a distributed computing environment using message passing. The code uses the finite difference method with the incompressible Navier-Stokes equations to solve for flow in nonsimple geometries. He analyzes the solution of linear systems by distributed relaxation methods and other methods suitable for distributed computing environments. He analyzes further recent convergence results for the GMRES(m) algorithm, a very robust method with wide applicability. The investigator has recently analyzed parallel computing methods and shown that synchronous methods are faster than asynchronous methods for a significant class of methods. He extends this work to a wider class of methods and use more powerful analytical methods to analyze parallel computations. The current code uses the PVM library to pass boundary values between domains. This project studies how best to solve some large numerical problems using parallel computation. For many of these computations, algorithms can be devised so that the total effort is split into several large pieces that are linked together. For example, determining the flow pattern of water past a submarine can be split into the flow near the front, middle, and rear, as well as the flow farther away from the submarine. For these four regions, if the solution is known in any three of the regions, the flow in the fourth region can be determined. This leads to an iterative method for computing the flow: assuming that the flow is correct in three regions, a flow in the other region can be computed. This resulting total flow can then be used to com pute a new flow in each region, and this process can be continued until it converges to the correct answer. The computations can be greatly speeded up if they are done for each region simultaneously, that is in parallel. There are a number of issues related to this sort of computation. The computation can proceed in a synchronous fashion, with a new round of updates beginning only after all have finished, or the updates could be done asynchronously, with a new update for a region beginning as soon as the previous update for that region is completed. For some problems it can be shown that the synchronous computations are faster. Some other iterative methods, in particular one called GMRES, are usually faster than the simple iteration described above. GMRES uses past information to guide the computation of the next update toward a better result. The investigator implements this in parallel and studies the gain in efficiency that results. One of the project's goals is to determine how to best decompose certain large problems to better utilize high performance computing environments.