Domain/Mesh Decomposition of Unstructured Grids with Pre-Ordering and Smoothing. G.U. Aero Report 9506

Increasingly large scale computations are using unstructured discrete computational grids. A typical example is unstructured grid calculations based on finite volume methods (FVM) in computational fluid dynamics (CFD). One of the efficient ways to deal with such large scale problems is parallelization. The present paper will focus on domain/mesh decomposition. This is the first step for distributing unstructured computational domains on a MIMD-type parallel computer system. A graph theory framework for this problem will be constructed. Based on the framework three domain decomposition algorithms: recursive coordinate bisection (RCB), recursive angular bisection (RAB) and recursive graph bisection (RGB), will be introduced, tested and discussed. A pre-ordering and smoothing technique is proposed. It is necessary in the procedure for obtaining a 'good' domain partitioning result. Another interesting method, called the domain decomposition technique (DDT), is also investigated, which is driven in an inverse way, i.e. domain decomposition followed by mesh construction. Finally a simple and direct strategy called the mesh tailor technique (MTT) is discussed. Numerical comparisons using 2D CFD problems will be given. The further research work required to carry out a parallel implementation of a flow problem will be mentioned