Articoli di riviste sul tema "Multigrid solution strategy"

AbstractA finite-element multigrid scheme for elliptic Nash-equilibrium multiobjective optimal control problems with control constraints is investigated. The multigrid computational framework implements a nonlinear multigrid strategy with collective smoothing for solving the multiobjective optimality system discretized with finite elements. Error estimates for the optimal solution and two-grid local Fourier analysis of the multigrid scheme are presented. Results of numerical experiments are presented to demonstrate the effectiveness of the proposed framework.

The Composite Finite Element Mesh method is useful for the estimation of the discretization error and, in addition, for the nodal solution improvement with a small increase in the computational cost. The technique uses two meshes with different element size to discretize a given problem and, then, it redefines the resulting linear system. On the other hand, Multigrid methods solve a linear system using systems of several sizes resulting from a hierarchy of meshes. This feature motivates the study of the application of the Multigrid strategy together with the Composite Mesh technique. In this work, it is proposed a Multigrid method to solve problems where the Composite Mesh is applied. The goal of the proposal is to achieve both, the advantages of the Multigrid algorithm efficiency and the solution improvement given by the Composite Mesh technique. The new method is tested with some elliptic problems with analytical solution.

A Segmented Domain Decomposition Multigrid (SDDMG) procedure was developed for viscous flow problems as they apply to turbomachinery flows. The procedure divides the computational domain into a coarse mesh comprised of uniformly spaced cells. To resolve smaller length scales such as the viscous layer near a surface, segments of the coarse mesh are subdivided into a finer mesh. This is repeated until adequate resolution of the smallest relevant length scale is obtained. Multigrid is used to communicate information between the different grid levels [1]. To test the procedure, simulation results will be presented for a compressor and turbine cascade. These simulations are intended to show the ability of the present method to generate grid independent solutions. Comparisons with data will also be presented. These comparisons will further demonstrate the usefulness of the present work for they allow an estimate of the accuracy of the flow modeling equations independent of error attributed to numerical discretization.

The stable finite element discretization of the Stokes problem produces a symmetric indefinite system of linear algebraic equations. A variety of iterative solvers have been proposed for such systems in an attempt to construct efficient, fast, and robust solution techniques. This paper investigates one of such iterative solvers, the geometric multigrid solver, to find the approximate solution of the indefinite systems. The main ingredient of the multigrid method is the choice of an appropriate smoothing strategy. This study considers the application of different smoothers and compares their effects in the overall performance of the multigrid solver. We study the multigrid method with the following smoothers: distributed Gauss Seidel, inexact Uzawa, preconditioned MINRES, and Braess-Sarazin type smoothers. A comparative study of the smoothers shows that the Braess-Sarazin smoothers enhance good performance of the multigrid method. We study the problem in a two-dimensional domain using stable Hood-TaylorQ2-Q1pair of finite rectangular elements. We also give the main theoretical convergence results. We present the numerical results to demonstrate the efficiency and robustness of the multigrid method and confirm the theoretical results.

Abstract The application of a parallel multiblock geometric multigrid is consid-ered. It is applied to solve a two-dimensional poroelastic model. This system of PDEs is approximated by a special stabilized monotone finite-difference scheme. The obtained system of linear algebraic equations is solved by a multigrid method, when a domain is partitioned into structured blocks. A new strategy for the solution of the discrete problem on the coarsest grid is proposed and the efficiency of the obtained algorithm is investigated. The geometrical structure of the sequential multigrid method is used to develop a parallel version of the multigrid algorithm. The convergence properties of several smoothers are investigated and some computational results are presented.

Purpose – An area of great interest in current computational fluid dynamics research is that of free-surface modelling (FSM). Semi-implicit pressure-based FSM flow solvers typically involve the solution of a pressure correction equation. The latter being computationally intensive, the purpose of this paper is to involve the implementation and enhancement of an algebraic multigrid (AMG) method for its solution. Design/methodology/approach – All AMG components were implemented via object-oriented C++ in a manner which ensures linear computational scalability and matrix-free storage. The developed technology was evaluated in two- and three-dimensions via application to a dam-break test case. Findings – AMG performance was assessed via comparison of CPU cost to that of several other competitive sparse solvers. The standard AMG implementation proved inferior to other methods in three-dimensions, while the developed Freeze version achieved significant speed-ups and proved to be superior throughout. Originality/value – A so-called Freeze method was developed to address the computational overhead resulting from the dynamically changing coefficient matrix. The latter involves periodic AMG setup steps in a manner that results in a robust and efficient black-box solver.

AbstractWe propose and investigate a novel solution strategy to efficiently and accurately compute approximate solutions to semilinear optimal control problems, focusing on the optimal control of phase field formulations of geometric evolution laws. The optimal control of geometric evolution laws arises in a number of applications in fields including material science, image processing, tumour growth and cell motility. Despite this, many open problems remain in the analysis and approximation of such problems. In the current work we focus on a phase field formulation of the optimal control problem, hence exploiting the well developed mathematical theory for the optimal control of semilinear parabolic partial differential equations. Approximation of the resulting optimal control problemis computationally challenging, requiring massive amounts of computational time and memory storage. The main focus of this work is to propose, derive, implement and test an efficient solution method for such problems. The solver for the discretised partial differential equations is based upon a geometric multigrid method incorporating advanced techniques to deal with the nonlinearities in the problem and utilising adaptive mesh refinement. An in-house two-grid solution strategy for the forward and adjoint problems, that significantly reduces memory requirements and CPU time, is proposed and investigated computationally. Furthermore, parallelisation as well as an adaptive-step gradient update for the control are employed to further improve efficiency. Along with a detailed description of our proposed solution method together with its implementation we present a number of computational results that demonstrate and evaluate our algorithms with respect to accuracy and efficiency. A highlight of the present work is simulation results on the optimal control of phase field formulations of geometric evolution laws in 3-D which would be computationally infeasible without the solution strategies proposed in the present work.

Our task is the identification of the reluctivity $\nu\,{=}\,\nu(B)$ in $\vec{H}\,{=}\,\nu(B) \vec{B}$, ($B\,{=}\,|\vec{B}|$) from measurements of the magnetic flux for different excitation currents in a driving coil, in the context of a nonuniform magnetic field distribution. This is a nonlinear inverse problem and ill-posed in the sense of unstable data dependence, whose solution is done numerically by a Newton type iterative scheme, regularized by an appropriate stopping criterion. The computational complexity of this method is determined by the number of necessary forward evaluations, i.e. the number of numerical solutions to the three-dimensional magnetic field problem. We keep the effort minimal by applying a special discretization strategy to the inverse problem, based on multigrid methods for ill-posed problems. Numerical results demonstrate the efficiency of the proposed method.

AbstractWe have developed efficient numerical algorithms for solving 3D steady-state Poisson-Nernst-Planck (PNP) equations with excess chemical potentials described by the classical density functional theory (cDFT). The coupled PNP equations are discretized by a finite difference scheme and solved iteratively using the Gummel method with relaxation. The Nernst-Planck equations are transformed into Laplace equations through the Slotboom transformation. Then, the algebraic multigrid method is applied to efficiently solve the Poisson equation and the transformed Nernst-Planck equations. A novel strategy for calculating excess chemical potentials through fast Fourier transforms is proposed, which reduces computational complexity from O(N2) to O(NlogN), where N is the number of grid points. Integrals involving the Dirac delta function are evaluated directly by coordinate transformation, which yields more accurate results compared to applying numerical quadrature to an approximated delta function. Numerical results for ion and electron transport in solid electrolyte for lithiumion (Li-ion) batteries are shown to be in good agreement with the experimental data and the results from previous studies.

A parallel framework software, CCFD, based on the structure grid, and suitable for parallel computing of super-large-scale structure blocks, is designed and implemented. An overdecomposition method, in which the load balancing strategy is based on the domain decomposition method, is designed for the graph subdivision algorithm. This method takes computation and communication as the limiting condition and realizes the load balance between blocks by dividing the weighted graph. The fast convergence technique of a high-efficiency parallel geometric multigrid greatly improves the parallel efficiency and convergence speed of CCFD software. This paper introduces the software structure, process invocations, and calculation method of CCFD and introduces a hybrid parallel acceleration technology based on the Sunway TaihuLight heterogeneous architecture. The results calculated by Onera-M6 and DLR-F6 standard model show that the software structure and method in this paper are feasible and can meet the requirements of a large-scale parallel solution.

AbstractWe propose a finite-difference ghost-point approach for the numerical solution of Cauchy-Navier equations in linear elasticity problems on arbitrary unbounded domains. The technique is based on a smooth coordinate transformation, which maps an unbounded domain into a unit square. Arbitrary geometries are defined by suitable level-set functions. The equations are discretized by classical nine-point stencil on interior points, while boundary conditions and high order reconstructions are used to define the field variables at ghost-points, which are grid nodes external to the domain with a neighbor inside the domain. The linear system arising from such discretization is solved by a multigrid strategy. The approach is then applied to solve elasticity problems in volcanology for computing the displacement caused by pressure sources. The method is suitable to treat problems in which the geometry of the source often changes (explore the effects of different scenarios, or solve inverse problems in which the geometry itself is part of the unknown), since it does not require complex re-meshing when the geometry is modified. Several numerical tests are successfully performed, which asses the effectiveness of the present approach.

To overcome the large time and memory consumption problems in large-scale high-resolution contaminant transport simulations, an efficient approach was presented to parallelize the modular three-dimensional transport model for multi-species (MT3DMS) (University of Alabama, Tuscaloosa, AL, USA) program on J adaptive structured meshes applications infrastructures (JASMIN). In this approach, a domain decomposition method and a stencil-based method were used to accomplish parallel implementation, while a ghost cell strategy was used for communication. The MODFLOW-MT3DMS coupling mode was optimized to achieve the parallel coupling of flow and contaminant transport. Five types of models were used to verify the correctness and test the parallel performance of the method. The developed parallel program JMT3D (China University of Geosciences (Beijing), Beijing, China) can increase the speed by up to 31.7 times, save memory consumption by 96% with 46 processors, and ensure that the solution accuracy and convergence do not decrease as the number of domains increases. The BiCGSTAB (Bi-conjugate gradient variant algorithm) method required the least amount of time and achieved high speedup in most cases. Coupling the flow and contaminant transport further improved the efficiency of the simulations, with a 33.45 times higher speedup achieved on 46 processors. The AMG (algebraic multigrid) method achieved a good scalability, with an efficiency above 100% on hundreds of processors for the simulation of tens of millions of cells.

Summary Simulation problems encountered in reservoir management are often computationally expensive because of the complex fluid physics for multiphase flow and the large number of grid cells required to honor geological heterogeneity. Multiscale methods have been proposed as a computationally inexpensive alternative to traditional fine-scale solvers for computing conservative approximations of the pressure and velocity fields on high-resolution geocellular models. Although a wide variety of such multiscale methods have been discussed in the literature, these methods have not yet seen widespread use in industry. One reason may be that no method has been presented so far that handles the combination of realistic flow physics and industry-standard grid formats in their full complexity. Herein, we present a multiscale method that handles both the most widespread type of flow physics (black-oil-type models) and standard grid formats such as corner-point, stair-stepped, and perpendicular bisector (PEBI), as well as general unstructured, polyhedral grids. Our approach is derived from a finite-volume formulation in which the basis functions are constructed by use of restricted smoothing to effectively capture the local features of the permeability. The method can also be formulated easily for other types of flow models, provided that one has a reliable (iterative) solution strategy that computes flow and transport in separate steps. The proposed method is implemented as open-source software and validated on a number of two- and three-phase test cases with significant compressibility and gas dissolution. The test cases include both synthetic models and models of real fields with complex wells, faults, and inactive and degenerate cells. Through a prescribed tolerance, the solver can be set to either converge to a sequential solution or the fully implicit solution, in both cases with a significant speedup compared with a fine-scale multigrid solver. Altogether, this ensures that one can easily and systematically trade accuracy for efficiency, or vice versa.

Boundary or interior layer problems of high-dimensional convection–diffusion equations have distinct asymmetry. Consequently, computational grid distributions and linear algebraic systems arising from finite difference schemes for them are also asymmetric. Numerical solutions for these kinds of problems are more complicated than those symmetric problems. In this paper, we extended our previous work on the partial semi-coarsening multigrid method combined with the high-order compact (HOC) difference scheme for solving the two-dimensional (2D) convection–diffusion problems on non-uniform grids to the three-dimensional (3D) cases. The main merit of the present method is that the multigrid method on non-uniform grids can be performed with a different number of grids in different coordinate axes, which is more efficient than the multigrid method on non-uniform grids with the same number of grids in different coordinate axes. Numerical experiments are carried out to validate the accuracy and efficiency of the present method. It is shown that, without losing the high precision, the present method is very effective to reduce computing cost by cutting down the number of grids in the direction(s) which does/do not contain boundary or interior layer(s).

AbstractAn adaptive mesh refinement strategy is proposed in this paper for the Immersed Boundary and Immersed Interface methods for two-dimensional elliptic interface problems involving singular sources. The interface is represented by the zero level set of a Lipschitz function ϕ(x,y). Our adaptive mesh refinement is done within a small tube of |ϕ(x,y)|≤δ with finer Cartesian meshes. The discrete linear system of equations is solved by a multigrid solver. The AMR methods could obtain solutions with accuracy that is similar to those on a uniform fine grid by distributing the mesh more economically, therefore, reduce the size of the linear system of the equations. Numerical examples presented show the efficiency of the grid refinement strategy.

An automatic agglomeration methodology to generate coarse grids for 3D flow solutions on anisotropic unstructured grids has been introduced in this paper. The algorithm combines isotropic octree based coarsening and anisotropic directional agglomeration to yield a desired coarsening ratio and high quality of coarse grids, which developed for cell-centered multigrid applications. This coarsening strategy developed is presented on an unstructured grid over 3D ONERA M6 wing. It is shown that the present method provides suitable coarsening ratio and well defined aspect ratio cells at all coarse grid levels.

This paper develops an automatic nested agglomeration methodology for 2D multigrid flow solutions over anisotropic unstructured grids. The algorithm combines isotropic quadtree based coarsening and anisotropic directional agglomeration method to yield a desired coarsening ratio and high quality of coarse grids, which works on cell-centered finite volume scheme. This coarsening strategy developed is presented on an unstructured grid over the RAE2822 airfoil. It is shown that the present method provides more suitable coarsening ratio and aspect ratio at all coarse grid levels than only quadtree based coarsening method.

Several viscous incompressible two and three-dimensional flows with strong inviscid interaction and/or axial flow reversal are considered with a segmented domain decomposition multigrid (SDDMG) procedure. Specific examples include the laminar flow recirculation in a trough geometry and in a three-dimensional step channel. For the latter case, there are multiple and three-dimensional recirculation zones. A pressure-based form of flux-vector splitting is applied to the Navier-Stokes equations, which are represented by an implicit, lowest-order reduced Navier-Stokes (RNS) system and a purely diffusive, higher-order, deferred-corrector. A trapezoidal or box-like form of discretization insures that all mass conservation properties are satisfied at interfacial and outflow boundaries, even for this primitive-variable non-staggered grid formulation. The segmented domain strategy is adapted herein for three-dimensional flows and is extended to allow for disjoint subdomains that do not share a common boundary.

Summary The major issues for parallel solvers in a modern reservoir simulator are robustness, scalability, efficiency, and flexibility. There is significant interest in running fast field-scale simulations for complex giant Middle Eastern reservoirs, which will require tens of millions to hundreds of millions of grid cells to give reasonable resolution. At the same time, significant geologic complexity will require the treatment of dual-permeability regions, faulting and fractures, and high variations of reservoir and fluid properties. Of course, the methods should also work well for extracted-sector simulation with local grid refinements in both the structured and unstructured discretization. The preconditioning methods considered in this work include both the single-stage and multistage frameworks. In the single-stage framework, a novel method is considered in addition to the well-known variants of incomplete lower-upper (ILU) factorizations [ILU0, ILU(k), and ILUT]. The new method is a highly parallel method, which, in this paper, will be referred to as the unstructured line-solve power-series (LSPS) method. The method will be discussed and contrasted in light of key issues for parallel linear solvers. The unstructured LSPS has certain interesting properties in the parallel construct, which make it a highly effective component. The multistage method researched in this work is of the constraint pressure residual (CPR) framework. The method uses approximate pressure solve as the first-stage preconditioning to the full-system preconditioning. A number of original adaptations based on this concept were researched. Here, the use of the parallel algebraic multigrid (PAMG) method and other single-level methods mentioned previously in combinations within the multistage CPR framework were explored. Certain methods constructed in this way are found to be highly efficient, scalable, and robust. The methods developed are discussed, and several test problems are included, in this paper. The largest simulation model tested to date using these solver methods is a 172-million-cell full-field model of a supergiant carbonate complex with more than 3,000 wells and 60 years of history simulation. Introduction Parallel reservoir simulation involving millions of grid cells is now common practice and is an essential component for the management of many giant carbonate complexes in the Middle East. The recent advances are aided in part by the computational power offered by inexpensive PC clusters. Many of today's parallel machines are built with mass-produced commodity-based components. At the same time, research and development on parallel highly scalable methods in the modern reservoir simulator have made routine field-scale simulation an effective and useful part of resource planning and analysis. Field-scale analyses are often desired over sector simulation for a comprehensive understanding of overall reservoir-behavior and recovery-processes performance. Special study involving an area of interest frequently arises in a full-field project. For example, evaluation of alternative designs for expensive maximum-reservoir-contact wells with intelligent downhole controls and production equipment requires near-wellbore reservoir simulation and optimization workflow. Thus, the demand is high for simulation capabilities with mixed structured and unstructured grids for fast field-scale megacell modeling. The capability to refine and coarsen at ease regionally and perform simulation and analyses at multiple scales within a single project is a primary near-term goal. This paper addresses one critical component of the tool set required to accomplish this mission--the linear solver. The primary solver methods in the old generation of reservoir simulators typically use nested factorization or variants of ILU-factorization method for preconditioning. While extension to small-scale parallel processing was achieved in the late 1990s, these methods have limitations in terms of scalability or robustness for the very-large-scale simulations where parallel processing with hundreds or even thousands of processors is required for speed and performance. Previously, within the structured-grid framework, a solver method known as the z-line Neumann series, which is more scalable for parallel field-scale simulation of structured grid, was documented by Dogru et al. (2002). Later, a parallel structured multigrid method was introduced by Fung and Dogru (2000) for treating the local-grid-refinement problems. The additional solver method for the dual-porosity dual-permeability system was later described by Fung and Al-Shaalan (2005). In this work, new ideas in the fully unstructured setting are being researched and developed. These ideas involve both the single-stage method and the multistage method. In the single-stage method, a novel idea of building an approximate inverse preconditioner through matrix substructuring of the Jacobian matrix was investigated. This substructuring method, which we refer to as LSPS, is a powerful generalization of the z-line Neumann series method. The method is fully unstructured. It increases robustness by tracing the maximum-transmissibility direction of the 3D unstructured graph. The strategy is particularly beneficial for reservoirs with fracture corridors and superpermeability (super-K) regions that cause difficulties for other solver methods. Furthermore, parallel efficiency is maintained, which is crucial for large-scale multiprocessor applications of the method. In the multistage method, the two-stage CPR method was investigated. The CPR method was first introduced into the petroleum literature by Wallis (1983) and Wallis et al. (1985). It was recently applied by Gratien et al. (2004) and Cao et al. (2005) in a new simulator development in which they have used the PAMG method as the pressure preconditioner. The research documented here explores the quasi-implicit-pressure-explicit-saturation (quasi-IMPES) reduction methods and the use of various approaches to solve the pressure approximately as a first-stage preconditioning to the full-system matrix. Solver results for several sample problems are included for comparison of the various methods. These include the public-domain data sets for the SPE1 (Odeh 1981) and SPE10 (Christie and Blunt 2001) comparative-solution projects and several megacell-simulation models. To add some challenge for the solver methods, the SPE1 grid system has been refined uniformly to 300,000 cells. To put all the methods into proper prospective, the three variants of the ILU factorizations [ILU0, ILU(k), and ILUT] are used as baseline comparison for some problems. The ILU preconditioners are well-known and are described in Saad (2003), thus descriptions of them are not included here. Interested readers can refer to Saad (2003) or the many other reference papers concerned with them.

This paper presents an adaptive strategy dedicated to non-linear transient dynamic problems. The spatial mesh is optimized to ensure the accuracy of the solution. Beginning from a coarse mesh, an error indicator is used to estimate the discretization error and new elements are created where the prescribed accuracy is not reached. A localized multigrid solver is used and the strategy is applied recursively until the local mesh size ensures that the discretization error is less than the prescribed accuracy. The spatial mesh is recreated at each time step.

ABSTRACTWe consider the modeling and simulation of multiscale phenomena which arise in finding the optimal shape design of microcellular composite materials with heterogeneous microstructures. The paper focuses on the solution of the resulting partial differential equation (PDE) constrained structural optimization problem and development of efficient multiscale numerical algorithms which are challenging tools in reducing the computational complexity. The modeling strategy is applied in materials science for microstructural ceramic materials of multiple constituents. Our multiscale method is based on the efficient combination of both macroscopic and microscopic models. The homogenization technique based on the concept of strong separation of scales and the asymptotic expansion of the unknown displacements is applied to extract the macroscopic information from the microscale model.In the framework of all-at-once approach we find a proper combination of the iterative procedure for the nonlinear problem arising from the first order necessary optimality conditions, also known as Karush-Kuhn-Tucker (KKT) conditions, and efficient large-scale solvers for the stress-strain constitutive equation. We use the path-following predictor-corrector schemes by means of Newton's method and fast multigrid (MG) solution techniques. The performance of two preconditioners, incomplete Cholesky (IC) and algebraic multigrid (AMG), for the resulting homogenized state equation is studied. The comparative analysis for both preconditioners in terms of number of iterations and computing times is presented and discussed. Our interests focus on the parallel implementation of the preconditioning techniques and the use of BoomerAMG as a part of the free software library Hypre developed at the Center for Applied Scientific Computing (CASC), Lawrence Livermore National Laboratory (LLNL).

AbstractBattery performance is strongly correlated with electrode microstructure. Electrode materials for lithium-ion batteries have complex microstructure geometries that require millions of degrees of freedom to solve the electrochemical system at the microstructure scale. A fast-iterative solver with an appropriate preconditioner is then required to simulate large representative volume in a reasonable time. In this work, a finite element electrochemical model is developed to resolve the concentration and potential within the electrode active materials and the electrolyte domains at the microstructure scale, with an emphasis on numerical stability and scaling performances. The block Gauss-Seidel (BGS) numerical method is implemented because the system of equations within the electrodes is coupled only through the nonlinear Butler–Volmer equation, which governs the electrochemical reaction at the interface between the domains. The best solution strategy found in this work consists of splitting the system into two blocks—one for the concentration and one for the potential field—and then performing block generalized minimal residual preconditioned with algebraic multigrid, using the FEniCS and the Portable, Extensible Toolkit for Scientific Computation libraries. Significant improvements in terms of time to solution (six times faster) and memory usage (halving) are achieved compared with the MUltifrontal Massively Parallel sparse direct Solver. Additionally, BGS experiences decent strong parallel scaling within the electrode domains. Last, the system of equations is modified to specifically address numerical instability induced by electrolyte depletion, which is particularly valuable for simulating fast-charge scenarios relevant for automotive application.

This paper proposes an efficient and robust procedure for the design optimization of turbomachinery cascades in inviscid and turbulent transonic flow conditions. It employs a progressive strategy, based on the simultaneous convergence of the design process and of all iterative solutions involved (flow analysis, gradient evaluation), also including the global refinement from a coarse to a sufficiently fine mesh. Cheap, flexible and easy-to-program Multigrid-Aided Finite Differences are employed for the computation of the sensitivity derivatives. The entire approach is combined with an upwind finite-volume method for the Euler and the Navier-Stokes equations on cell-vertex unstructured (triangular) grids, and validated versus the inverse design of a turbine cascade. The methodology turns out to be robust and highly efficient, the converged design optimization being obtained in a computational time equal to that required by 15 to 20 (depending on the application) multigrid flow analyses on the finest grid.