Parallel multi-frontal solver for p adaptive finite element modeling of multi-physics computational problems

The paper presents a parallel direct solver for multi-physics problems. The solver is dedicated for solving problems resulting from adaptive finite element method computations. The concept of finite element is actually replaced by the concept of the node. The computational mesh consists of several nodes, related to element vertices, edges, faces and interiors. The ordering of unknowns in the solver is performed on the level of nodes. The concept of the node can be efficiently utilized in order to recognize unknowns that can be eliminated at a given node of the elimination tree. The solver is tested on the exemplary three-dimensional multi-physics problem involving the computations of the linear acoustics coupled with linear elasticity. The three-dimensional tetrahedral mesh generation and the solver algorithm are modeled by using graph grammar formalism. The execution time and the memory usage of the solver are compared with the MUMPS solver.     

A tearing-based hybrid parallel banded linear system solver

A new parallel algorithm for the solution of banded linear systems is proposed. The scheme tears the coefficient matrix into several overlapped independent blocks in which the size of the overlap is equal to the system’s bandwidth. A corresponding splitting of the right-hand side is also provided. The resulting independent, and smaller size, linear systems are solved under the constraint that the solutions corresponding to the overlap regions are identical. This results in a linear system whose size is proportional to the sum of the overlap regions which we refer to as the “balance” system. We propose a solution strategy that does not require obtaining this “balance” system explicitly. Once the balance system is solved, retrieving the rest of the solution can be realized with almost perfect parallelism. Our proposed algorithm is a hybrid scheme that combines direct and iterative methods for solving a single banded system of linear equations on parallel architectures. It has broad applications in finite-element analysis, particularly as a parallel solver of banded preconditioners that can be used in conjunction with outer Krylov iterative schemes.     

Numerical simulation of microwave thawing using a coupled solver approach

Thawing of a frozen food product in a domestic microwave oven is numerically simulated using a coupled solver approach. The approach consists of a dedicated electromagnetic FDTD solver and a closely coupled UFVM multi-physics package. Two overlapping numerical meshes are defined; the food material and container were meshed for heat transfer and phase change solution, whilst the microwave oven cavity and waveguide were meshed for the microwave irradiation. The two solution domains were linked using a cross-mapping routine. This approach allowed the rotation of the food load to be captured. Power densities obtained on the structured FDTD mesh were interpolated onto the UFVM mesh for each timestep/turntable position. The UFVM solver utilised the power density data to advance the temperature and phase distribution solution. The temperature-dependant dielectric and thermo-physical properties of the food load were updated prior to revising the electromagnetic solution. Changes in thermal/electric properties associated with the phase transition were fully accounted for as well as heat losses from product to cavity. Two scenarios were investigated: a centric and eccentric placement on the turntable. Developing temperature fields predicted by the numerical solution are validated against experimentally obtained data. Presented results indicate the feasibility of fully coupled simulations of the microwave heating of a frozen product. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Stochastic Domain Decomposition for Time Dependent Adaptive Mesh Generation

The efficient generation of meshes is an important component in the numerical solution of problems in physics and engineering. Of interest are situations where global mesh quality and a tight coupling to the solution of the physical partial differential equation (PDE) is important. We consider parabolic PDE mesh generation and present a method for the construction of adaptive meshes in two spatial dimensions using stochastic domain decomposition that is suitable for an implementation in a multi- or many-core environment. Methods for mesh generation on periodic domains are also provided. The mesh generator is coupled to a time dependent physical PDE and the system is evolved using an alternating solution procedure. The method uses the stochastic representation of the exact solution of a parabolic linear mesh generator to find the location of an adaptive mesh along the (artificial) subdomain interfaces. The deterministic evaluation of the mesh over each subdomain can then be obtained completely independently using the probabilistically computed solutions as boundary conditions. A small scaling study is provided to demonstrate the parallel performance of this stochastic domain decomposition approach to mesh generation. We demonstrate the approach numerically and compare the mesh obtained with the corresponding single domain mesh using a representative mesh quality measure.     

Automatic domain decomposition on unstructured grids (DOUG)

This paper describes a parallel iterative solver for finite element discretisations of elliptic partial differential equations on 2D and 3D domains using unstructured grids. The discretisation of the PDE is assumed to be given in the form of element stiffness matrices and the solver is automatic in the sense that it requires minimal additional information about the PDE and the geometry of the domain. The solver parallelises matrix–vector operations required by iterative methods and provides parallel additive Schwarz preconditioners. Parallelisation is implemented through MPI. The paper contains numerical experiments showing almost optimal speedup on unstructured mesh problems on a range of four platforms and in addition gives illustrations of the use of the package to investigate several questions of current interest in the analysis of Schwarz methods. The package is available in public domain from the home page http://www.maths.bath.ac.uk/^∼mjh/. This revised version was published online in August 2006 with corrections to the Cover Date.     

A simple numerical approach for assessing coupled transport processes in partitioning systems

Recent concepts in the solution of multidomain equation systems are applied to the problem of distinct transport processes coupled over geometrically disjoint domains. The (time dependent) transport equations for the composite system are solved using a simple domain decomposition approach, with parallel implementations of detailed Schwarz balances for the system subdomain interfaces. An existing numerical partial differential equation (PDE) solver is coupled with the interface algorithms to provide a code capable of handling a wide range of dynamical equations within the subdomains. Interface partitioning conditions corresponding to sharply discontinuous Dirichlet constraints, and to (discontinuous) rate-limited Neumann constraints are also incorporated into the code. A variety of transport operators can be handled simply by altering the equation system code block. The code is validated against analytical solutions for representative parabolic transport equations including recent solutions for diffusive transport in partitioning laminates, useful for describing the movement of chemical species in composite materials. The code is then applied to an example problem of coupled multiphase chemical transport in a variably saturated soil column with a low-permeability capping.     

Parallel structural optimization applied to bone remodeling on distributed memory machines

In this paper, we investigate parallel structural optimization methods on distributed memory MIMD machines. We have restricted ourselves to the case of minimizing a multivariate non-linear function subject to bounds on the independent variables, when the objective function is expensive to evaluate as compared to the linear algebra portion of the optimization. This is the case in structural applications, when a large three-dimensional finite element mesh is used to model the structure.This paper demonstrates how parallelism can be exploited during the function and gradient computation as well as the optimization iterations. For the finite element analysis, a torus wrap skyline solver is used. The reflective Newton method, which attempts to reduce the number of iterations at the expense of more linear algebra per iteration, is compared with the more conventional active set method. All code is developed for an Intel iPSC/860, but can be ported to other distributed memory machines.The methods developed are applied to problems in bone remodeling. In the area of biomechanics, optimization models can be used to predict changes in the distribution of material properties in bone due to the presence of an artificial implant. The model we have used minimizes a linear combination of the mass and strain energy in the entire domain subject to bounds on the densities in each finite element.Early results show that the reflective Newton method can outperform active set methods when few variables are active at the minimum.     

An asynchronous direct solver for banded linear systems

Banded linear systems occur frequently in mathematics and physics. However, direct solvers for large systems cannot be performed in parallel without communication. The aim of this paper is to develop a general asymmetric banded solver with a direct approach that scales across many processors efficiently. The key mechanism behind this is that reduction to a row-echelon form is not required by the solver. The method requires more floating point calculations than a standard solver such as LU decomposition, but by leveraging multiple processors the overall solution time is reduced. We present a solver using a superposition approach that decomposes the original linear system into q subsystems, where q is the number of superdiagonals. These methods show optimal computational cost when q processors are available because each system can be solved in parallel asynchronously. This is followed by a q×q dense constraint matrix problem that is solved before a final vectorized superposition is performed. Reduction to row echelon form is not required by the solver, and hence the method avoids fill-in. The algorithm is first developed for tridiagonal systems followed by an extension to arbitrary banded systems. Accuracy and performance is compared with existing solvers and software is provided in the supplementary material.     

Diagnostic assessment of children’s proportional reasoning

A proportional reasoning item bank was created from the relevant literature and tested in various forms. Rasch analyses of 303 pupils’ test results were used to calibrate the bank, and data from 84 pupils’ interviews was used to confirm our diagnostic interpretations. A number of sub-tests were scaled, including parallel ‘without models’ and ‘with models’ forms. We provide details of the 13-item ‘without models’ test which was formed from the ‘richest’ diagnostic items and verified on a further test sample (N=212, ages 10-13). Two scales were constructed for this test, one that measures children’s ‘ratio attainment’ and one that measures their ‘tendency for additive strategy.’ Other significant errors — ‘incorrect build-up,’ ‘magical doubling/halving,’ ‘constant sum’ and ‘incomplete reasoning’ — were identified. Finally, an empirical hierarchy of pupils’ attainment of proportional reasoning was formed, incorporating the significant errors and the additive scale.     

A GPU-based algorithm for efficient LES of high Reynolds number flows in heterogeneous CPU/GPU supercomputers

Αn optimized MPI+OpenACC implementation model that performs efficiently in CPU/GPU systems using large-eddy simulation is presented. The code was validated for the simulation of wave boundary-layer flows against numerical and experimental data in the literature. A direct Fast-Fourier-Transform-based solver was developed for the solution of the Poisson equation for pressure taking advantage of the periodic boundary conditions. This solver was optimized for parallel execution in CPUs and outperforms by 10 times in computational time a typical iterative preconditioned conjugate gradient solver in GPUs. In terms of parallel performance, an overlapping strategy was developed to reduce the overhead of performing MPI communications using GPUs. As a result, the weak scaling of the algorithm was improved up to 30%. Finally, a large-scale simulation (Re = 2 × 10⁵) using a grid of 4 × 10⁸ cells was executed, and the performance of the code was analyzed. The simulation was launched using up to 512 nodes (512 GPUs + 6144 CPU-cores) on one of the current top 10 supercomputers of the world (Piz Daint). A comparison of the overall computational time showed that the GPU version was 4.2 times faster than the CPU one. The parallel efficiency of this strategy (47%) is competitive compared with the state-of-the-art CPU implementations, and it has the potential to take advantage of modern supercomputing capabilities.     

Hopf algebras of primitive Lie pseudogroups and Hopf cyclic cohomology

We associate to each infinite primitive Lie pseudogroup a Hopf algebra of ‘transverse symmetries,’ by refining a procedure due to Connes and the first author in the case of the general pseudogroup. The affiliated Hopf algebra can be viewed as a ‘quantum group’ counterpart of the infinite-dimensional primitive Lie algebra of the pseudogroup. It is first constructed via its action on the étale groupoid associated to the pseudogroup, and then realized as a bicrossed product of a universal enveloping algebra by a Hopf algebra of regular functions on a formal group. The bicrossed product structure allows to express its Hopf cyclic cohomology in terms of a bicocyclic bicomplex analogous to the Chevalley-Eilenberg complex. As an application, we compute the relative Hopf cyclic cohomology modulo the linear isotropy for the Hopf algebra of the general pseudogroup, and find explicit cocycle representatives for the universal Chern classes in Hopf cyclic cohomology. As another application, we determine all Hopf cyclic cohomology groups for the Hopf algebra associated to the pseudogroup of local diffeomorphisms of the line.     

A coarse–fine‐mesh stabilization for an alternating Schwarz domain decomposition method

Domain decomposition methods can be solved in various ways. In this paper, domain decomposition in strips is used. It is demonstrated that a special version of the Schwarz alternating iteration method coupled with coarse–fine‐mesh stabilization leads to a very efficient solver, which is easy to implement and has a behavior nearly independent of mesh and problem parameters. The novelty of the method is the use of alternating iterations between odd‐ and even‐numbered subdomains and the replacement of the commonly used coarse‐mesh stabilization method with coarse–fine‐mesh stabilization.     

On the parallel between normality and extremal disconnectedness

Several familiar results about normal and extremally disconnected (classical or pointfree) spaces shape the idea that the two notions are somehow dual to each other and can therefore be studied in parallel. This paper investigates the source of this ‘duality’ and shows that each pair of parallel results can be framed by the ‘same’ proof. The key tools for this purpose are relative notions of normality, extremal disconnectedness, semicontinuity and continuity (with respect to a fixed class of complemented sublocales of the given locale) that bring and extend to locale theory a variety of well-known classical variants of normality and upper and lower semicontinuities in an illuminating unified manner. This approach allows us to unify under a single localic proof all classical insertion, as well as their corresponding extension results.     

Basic randomness of nature and ether-drift experiments

We re-consider the idea that quantum fluctuations might reflect the existence of an ‘objective randomness’, i.e. a basic property of the vacuum state which is independent of any experimental accuracy of the observations or limited knowledge of initial conditions. Besides being responsible for the observed quantum behavior, this might introduce a weak, residual form of ‘noise’ which is intrinsic to natural phenomena and could be important for the emergence of complexity at higher physical levels. By adopting Stochastic Electro Dynamics as a heuristic model, we are driven to a picture of the vacuum as a form of highly turbulent ether, which is deep-rooted into the basic foundational aspects of both quantum physics and relativity, and to search for experimental tests of this scenario. An analysis of the most precise ether-drift experiments, operating both at room temperature and in the cryogenic regime, shows that, at present, there is some ambiguity in the interpretation of the data. In fact the average amplitude of the signal has precisely the magnitude expected, in a ‘Lorentzian’ form of relativity, from an underlying stochastic ether and, as such, might not be a spurious instrumental effect. This puzzle, however, should be solved in a next future with the use of new cryogenically cooled optical resonators whose stability should improve by about two orders of magnitude. In these new experimental conditions, the persistence of the present amplitude would represent a clean evidence for the type of random vacuum we are envisaging.     

基于多GPU的格子Boltzmann法对槽道湍流的直接数值模拟

采用多GPU并行的格子Boltzmann方法（lattice Boltzmann method, LBM）对充分发展的槽道湍流进行了直接数值模拟．GPU(graphic processing unit)的数据并行单指令多线程（single-instruction multiple-thread, SIMT)特征与LBM完美的并行性相匹配,使得LBM求解器在GPU上运行获得了极高的性能,亦使得大规模DNS(direct numerical simulation)在桌面级计算机上进行成为可能．采用8个GPU,网格数目达到6.7×107,全场网格尺寸Δ+=1.41．模拟3×106个时间步长,用时仅24 h．另外,直接模拟结果无论是在平均流速或湍流统计量上均与Moser等的结果吻合得很好,这也证实了二阶精度的格子Boltzmann法直接模拟湍流的能力与有效性     

Bubble simulations with an interface tracking technique based on a partitioned fluid-structure interaction algorithm

Numerical techniques frequently used for the simulation of one bubble can be classified as interface tracking techniques and interface capturing techniques. Most of these techniques calculate both the flow around the bubble and the shape of the interface between the gas and the liquid with one code. In this paper, a rising axisymmetric bubble is simulated with an interface tracking technique that uses separate codes to determine the position of the gas-liquid interface and to calculate the flow around the bubble. The grid converged results correspond well with the experimental data.The gas-liquid interface is conceived as a zero-mass, zero-thickness structure whose position is determined by the liquid forces, a uniform gas pressure and surface tension. Iterations between the two codes are necessary to obtain the coupled solution of both problems and these iterations are stabilized with a fluid-structure interaction (FSI) algorithm. The flow around the bubble is calculated on a moving mesh in a reference frame that rises at the same speed as the bubble. The flow solver first updates the mesh throughout the liquid domain given a position of the gas-liquid interface and then calculates the flow around the bubble. It is considered as a black box with the position of the gas-liquid interface as input and the liquid forces on the interface as output. During the iterations, a reduced-order model of the flow solver is generated from the inputs and outputs of the solver. The solver that calculates the interface position uses this model to adapt the liquid forces on the gas-liquid interface during the calculation of the interface position.     

A parallel block overlap preconditioning with inexact submatrix inversion for linear elasticity problems

We present a parallel preconditioned iterative solver for large sparse symmetric positive definite linear systems. The preconditioner is constructed as a proper combination of advanced preconditioning strategies. It can be formally seen as being of domain decomposition type with algebraically constructed overlap. Similar to the classical domain decomposition technique, inexact subdomain solvers are used, based on incomplete Cholesky factorization. The proper preconditioner is shown to be near optimal in minimizing the so‐called K‐condition number of the preconditioned matrix. The efficiency of both serial and parallel versions of the solution method is illustrated on a set of benchmark problems in linear elasticity. Copyright © 2002 John Wiley & Sons, Ltd.     

Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing

This paper describes new models and exact solution algorithms for the fixed destination multidepot salesmen problem defined on a graph with n nodes where the number of nodes each salesman is to visit is restricted to be in a predefined range. Such problems arise when the time to visit a node takes considerably longer as compared to the time of travel between nodes, in which case the number of nodes visited in a salesman’s tour is the determinant of their ‘load’. The new models are novel multicommodity flow formulations with O(n²) binary variables, which is contrary to the existing formulations for the same (and similar) problems that typically include O(n³) binary variables. The paper also describes Benders decomposition algorithms based on the new formulations for solving the problem exactly. Results of the computational experiments on instances derived from TSPLIB show that some of the proposed algorithms perform remarkably well in cases where formulations solved by a state-of-the-art optimization code fail to yield optimal solutions within reasonable computation time.     

A distributed combustion solver for engine simulations on grids

Multi-dimensional models for predictive simulations of modern engines are an example of multi-physics and multi-scale mathematical models, since lots of thermofluiddynamic processes in complex geometrical configurations have to be considered. Typical models involve different submodels, including turbulence, spray and combustion models, with different characteristic time scales. The predictive capability of the complete models depends on the accuracy of the submodels as well as on the reliability of the numerical solution algorithms. In this work we propose a multi-solver approach for reliable and efficient solution of the stiff Ordinary Differential Equation (ODE) systems arising from detailed chemical reaction mechanisms for combustion modeling. Main aim was to obtain high-performance parallel solution of combustion submodels in the overall procedure for simulation of engines on distributed heterogeneous computing platforms. To this aim we interfaced our solver with the CHEMKIN-II package and the KIVA3V-II code and carried out multi-computer simulations of realistic engines. Numerical experiments devoted to test reliability of the simulation results and efficiency of the distributed combustion solver are presented and discussed.