Academic literature on the topic 'Substructuring preconditioner'

AbstractA DD (domain decomposition) preconditioner of almost optimal in p arithmetical complexity is presented for the hierarchical hp discretizations of 3-d second order elliptic equations. We adapt the wire basket substructuring technique to the hierarchical hp discretization, obtain a fast preconditioner-solver for faces by Kinterpolation technique and show that a secondary iterative process may be efficiently used for prolongations from faces. The fast solver for local Dirichlet problems on subdomains of decomposition is based on our earlier derived finite-difference like preconditioner for the internal stiffness matrices of p-finite elements and fast solution procedures for systems with this preconditioner, which appeared recently.

Abstract The discretization of optimal control of elliptic partial differential equations problems yields optimality conditions in the form of large sparse linear systems with block structure. Correspondingly, when the solution method is a Dirichlet-Dirichlet non-overlapping domain decomposition method, we need to solve interface problems which inherit the block structure. It is therefore natural to consider block preconditioners acting on the interface variables for the acceleration of Krylov methods with substructuring preconditioners. In this paper we describe a generic technique which employs a preconditioner block structure based on the fractional Sobolev norms corresponding to the domains of the boundary operators arising in the matrix interface problem, some of which may include a dependence on the control regularization parameter. We illustrate our approach on standard linear elliptic control problems. We present analysis which shows that the resulting iterative method converges independently of the size of the problem. We include numerical results which indicate that performance is also independent of the control regularization parameter and exhibits only a mild dependence on the number of the subdomains.

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.

Cette thèse étudie les méthodes de décomposition de domaine généralement classées soit comme des méthodes de Schwarz avec recouvrement ou des méthodes par sous-structuration s'appuyant sur des sous-domaines sans recouvrement. Nous nous focalisons principalement sur la méthode des éléments finis joints, aussi appelée la méthode mortar, une approche non conforme des méthodes par sous-structuration impliquant des contraintes de continuité faible sur l'espace d'approximation. Nous introduisons un framework élément fini pour la conception et l'analyse des préconditionneurs par sous-structuration pour une résolution efficace du système linéaire provenant d'une telle méthode de discrétisation. Une attention particulière est accordée à la construction du préconditionneur grille grossière, notamment la principale variante proposée dans ce travailutilisant la méthode de Galerkin Discontinue avec pénalisation intérieure comme problème grossier. D'autres méthodes de décomposition de domaine, telles que les méthodes de Schwarz et la méthode dite three-field sont étudiées dans l'objectif d'établir un environnement de programmation générique d'enseignement et de recherche pour une large gamme de ces méthodes. Nous développons un framework de calcul avancé et dédié à la mise en oeuvre parallèle des méthodesnumériques et des préconditionneurs introduits dans cette thèse. L'efficacité et la scalabilité des préconditionneurs, ainsi que la performance des algorithmes parallèles sont illustrées par des expériences numériques effectuées sur des architectures parallèles à très grande échelle<br>This thesis investigates domain decomposition methods, commonly classified as either overlapping Schwarz methods or iterative substructuring methods relying on nonoverlapping subdomains. We mainly focus on the mortar finite element method, a nonconforming approach of substructuring method involving weak continuity constraints on the approximation space. We introduce a finiteelement framework for the design and the analysis of the substructuring preconditioners for an efficient solution of the linear system arising from such a discretization method. Particular consideration is given to the construction of the coarse grid preconditioner, specifically the main variantproposed in this work, using a Discontinuous Galerkin interior penalty method as coarse problem. Other domain decomposition methods, such as Schwarz methods and the so-called three-field method are surveyed with the purpose of establishing a generic teaching and research programming environment for a wide range of these methods. We develop an advanced computational framework dedicated to the parallel implementation of numerical methods and preconditioners introduced in this thesis. The efficiency and the scalability of the preconditioners, and the performance of parallel algorithms are illustrated by numerical experiments performed on large scale parallel architectures

This paper presents a computational method for formulating and solving the dynamical equations of motion for complex mechanisms and multibody systems. The equations of motion are formulated in a preconditioned form using kinematic substructuring with a heuristic application of Generalized Coordinate Partitioning (GCP). This results in an optimal split of dependent and independent variables during run time. It also allows reliable handling of end-of-stroke conditions and bifurcations in mechanisms, thereby facilitating dynamic simulation of paradoxical linkages such as Bricard’s mechanism that has been known to cause problems with some multibody dynamic codes. The new Preconditioned Equations of Motion are then solved using a recursive formulation of the Schur Complement Method combined with Sparse Matrix Techniques. In this fashion the Preconditioned Equations of Motion are recursively uncoupled and solved one kinematic substructure at a time. The results are demonstrated using examples.