Mesh partitioning: A multilevel balancing and refinement algorithm

Multilevel algorithms are a successful class of optimisation techniques which address the mesh partitioning problem. They usually combine a graph contraction algorithm together with a local optimisation method which refines the partition at each graph level. In this paper we present an enhancement of the technique which uses imbalance to achieve higher quality partitions. We also present a formulation of the Kernighan-Lin partition optimisation algorithm which incorporates load-balancing. The resulting algorithm is tested against a different but related state-of the-art partitioner and shown to provide improved results.

Multilevel mesh partitioning for optimising domain shape

Multilevel algorithms are a successful class of optimisation techniques which address the mesh partitioning problem for mapping meshes onto parallel computers. They usually combine a graph contraction algorithm together with a local optimisation method which refines the partition at each graph level. To date these algorithms have been used almost exclusively to minimise the cut-edge weight in the graph with the aim of minimising the parallel communication overhead. However it has been shown that for certain classes of problem, the convergence of the underlying solution algorithm is strongly influenced by the shape or aspect ratio of the subdomains. In this paper therefore, we modify the multilevel algorithms in order to optimise a cost function based on aspect ratio. Several variants of the algorithms are tested and shown to provide excellent results.

Parallel optimisation algorithms for multilevel mesh partitioning

Abstract not available

Multiphase mesh partitioning

Abstract not available

Evaluation of the JOSTLE mesh partitioning code for practical multiphysics applications

The use of unstructured mesh codes on parallel machines is one of the most effective ways to solve large computational mechanics problems. Completely general geometries and complex behaviour can be modelled and, in principle, the inherent sparsity of many such problems can be exploited to obtain excellent parallel efficiencies. However, unlike their structured counterparts, the problem of distributing the mesh across the memory of the machine, whilst minimising the amount of interprocessor communication, must be carefully addressed. This process is an overhead that is not incurred by a serial code, but is shown to rapidly computable at turn time and tailored for the machine being used.

Parallel partitioning of unstructured meshes

A method is outlined for optimising graph partitions which arise in mapping un- structured mesh calculations to parallel computers. The method employs a combination of iterative techniques to both evenly balance the workload and minimise the number and volume of interprocessor communications. They are designed to work efficiently in parallel as well as sequentially and when combined with a fast direct partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two-stage process proves itself to be both a powerful and flexible solution to the static graph-partitioning problem. The algorithms can also be used for dynamic load-balancing and a clustering technique can additionally be employed to speed up the whole process. Experiments indicate that the resulting parallel code can provide high quality partitions, independent of the initial partition, within a few seconds.

Multilevel mesh partitioning for optimising subdomain aspect ratio

Multilevel algorithms are a successful class of optimisation techniques which address the mesh partitioning problem for mapping meshes onto parallel computers. They usually combine a graph contraction algorithm together with a local optimisation method which refines the partition at each graph level. To date these algorithms have been used almost exclusively to minimise the cut-edge weight in the graph with the aim of minimising the parallel communication overhead. However it has been shown that for certain classes of problem, the convergence of the underlying solution algorithm is strongly influenced by the shape or aspect ratio of the subdomains. In this paper therefore, we modify the multilevel algorithms in order to optimise a cost function based on aspect ratio. Several variants of the algorithms are tested and shown to provide excellent results.

Multilevel mesh partitioning for aspect ratio

Multilevel algorithms are a successful class of optimisation techniques which address the mesh partitioning problem. They usually combine a graph contraction algorithm together with a local optimisation method which refines the partition at each graph level. To date these algorithms have been used almost exclusively to minimise the cut-edge weight, however it has been shown that for certain classes of solution algorithm, the convergence of the solver is strongly influenced by the subdomain aspect ratio. In this paper therefore, we modify the multilevel algorithms in order to optimise a cost function based on aspect ratio. Several variants of the algorithms are tested and shown to provide excellent results.

Aspect ratio for mesh partitioning

This paper deals with the measure of Aspect Ratio for mesh partitioning and gives hints why, for certain solvers, the Aspect Ratio of partitions plays an important role. We define and rate different kinds of Aspect Ratio, present a new center-based partitioning method which optimizes this measure implicitly and rate several existing partitioning methods and tools under the criterion of Aspect Ratio.

Mesh partitioning and load balancing for distributed memory parallel systems

A method is outlined for optimising graph partitions which arise in mapping unstructured mesh calculations to parallel computers. The method employs a relative gain iterative technique to both evenly balance the workload and minimise the number and volume of interprocessor communications. A parallel graph reduction technique is also briefly described and can be used to give a global perspective to the optimisation. The algorithms work efficiently in parallel as well as sequentially and when combined with a fast direct partitioning technique (such as the Greedy algorithm) to give an initial partition, the resulting two-stage process proves itself to be both a powerful and flexible solution to the static graph-partitioning problem. Experiments indicate that the resulting parallel code can provide high quality partitions, independent of the initial partition, within a few seconds. The algorithms can also be used for dynamic load-balancing, reusing existing partitions and in this case the procedures are much faster than static techniques, provide partitions of similar or higher quality and, in comparison, involve the migration of a fraction of the data.

Parallel dynamic graph-partitioning for unstructured meshes

A parallel method for the dynamic partitioning of unstructured meshes is described. The method introduces a new iterative optimisation technique known as relative gain optimisation which both balances the workload and attempts to minimise the interprocessor communications overhead. Experiments on a series of adaptively refined meshes indicate that the algorithm provides partitions of an equivalent or higher quality to static partitioners (which do not reuse the existing partition) and much more rapidly. Perhaps more importantly, the algorithm results in only a small fraction of the amount of data migration compared to the static partitioners.

Dynamic multi-partitioning for parallel finite element applications

The central product of the DRAMA (Dynamic Re-Allocation of Meshes for parallel Finite Element Applications) project is a library comprising a variety of tools for dynamic re-partitioning of unstructured Finite Element (FE) applications. The input to the DRAMA library is the computational mesh, and corresponding costs, partitioned into sub-domains. The core library functions then perform a parallel computation of a mesh re-allocation that will re-balance the costs based on the DRAMA cost model. We discuss the basic features of this cost model, which allows a general approach to load identification, modelling and imbalance minimisation. Results from crash simulations are presented which show the necessity for multi-phase/multi-constraint partitioning components.

Chemical changes and heavy metal partitioning in an oxisol cultivated with maize (Zea mays, L.) after 5 years disposal of a domestic and an industrial sewage sludge.

The need for solutions to minimize the negative environmental impacts of anthropogenic activities Fhas increased. Sewage sludge is composed of predominantly organic matter and can be used to improve soil characteristics, such as fertility. Therefore, its application in agriculture is an adequate alternative for its final disposal. However, there is a lack of information on its long-term effects on soil changes in tropical areas. Thus, the objectives of this study were to determine (i) the effect of sewage sludge application on heavy metal build-up in soil and maize grains and leaves, and (ii) the effects of soil amendment with sewage sludge on the chemical properties of a Brazilian oxisol. Besides the increasing levels of Zn, Cu, Ni, and Cr, amending soil with sewage sludge also alters the distribution of these metals by increasing the mobile Phases, which correlated significantly with the increase in metal extraction with two single extractants, Mehlich 1 and DTPA (Diethylene triamine pentaacetic acid). The levels of Fe, Mn, Zn, and Cu in maize grains and leaves increased with the type and rate of sewage sludge application. Nevertheless, metal build-up in soil and plants was within the allowed limits. Significant differences were also found in soil characteristics like humic fractionation with the applied sewage doses. The data obtained does not indicate any expressive drawbacks in the use of sewage sludge as a soil amendment, as the heavy metal concentrations observed are unlikely to cause any environmental or health problems, even overestimated loadings, and are in accordance with the Brazilian regulations on farming land biosolid disposal.

Emergence and fate of siloxanes in waste streams: Release mechanisms, partitioning and persistence in three environmental compartments

Siloxanes are widely used in personal care and industrial products due to their low surface tension, thermal stability, antimicrobial and hydrophobic properties, among other characteristics. Volatile methyl siloxanes (VMS) have been detected both in landfill gas and biogas from anaerobic digesters at wastewater treatment plants. As a result, they are released to gas phase during waste decomposition and wastewater treatment. During transformation processes of digester or landfill gas to energy, siloxanes are converted to silicon oxides, leaving abrasive deposits on engine components. These deposits cause increased maintenance costs and in some cases complete engine overhauls become necessary. ^ The objectives of this study were to compare the VMS types and levels present in biogas generated in the anaerobic digesters and landfills and evaluate the energetics of siloxane transformations under anaerobic conditions. Siloxane emissions, resulting from disposal of silicone-based materials, are expected to increase by 29% within the next 10 years. Estimated concentrations and the risk factors of exposure to siloxanes were evaluated based on the initial concentrations, partitioning characteristics and persistence. It was determined that D4 has the highest risk factor associated to bioaccumulation in liquid and solid phase, whereas D5 was highest in gas phase. Additionally, as siloxanes are combusted, the particle size range causes them to be potentially hazardous to human health. When inhaled, they may affix onto the alveoli of the lungs and may lead to development of silicosis. Siloxane-based COD-loading was evaluated and determined to be an insignificant factor concerning COD limits in wastewater. ^ Removal of siloxane compounds is recommended prior to land application of biosolids or combustion of biogas. A comparison of estimated costs was made between maintenance practices for removal of siloxane deposits and installation/operation of fixed-bed carbon absorption systems. In the majority of cases, the installation of fixed-bed adsorption systems would not be a feasible option for the sole purpose of siloxane removal. However they may be utilized to remove additional compounds simultaneously.^