Preconditioners in computational geomechanics: A survey

The finite element (FE) solution of geomechanical problems in realistic settings raises a few numerical issues depending on the actual process addressed by the analysis. There are two basic problems where the linear solver efficiency may play a crucial role: 1. fully coupled consolidation and 2. faulted uncoupled consolidation. A class of general solvers becoming increasingly popular relies on the Krylov subspace (or Conjugate Gradient‐like) methods, provided that an efficient preconditioner is available. For both problems mentioned above, the possible preconditioners include the diagonal scaling (DS), the Incomplete LU decomposition (ILU), the mixed constraint preconditioning (MCP) and the multilevel incomplete factorization (MIF). The development and the performance of these algorithms have been the topic of several recent works. The present paper aims at providing a survey of the preconditioners available to date in computational geomechanics. In particular, a review and a critical discussion of DS, ILU, MCP and MIF are given along with some comparative numerical results. Copyright © 2010 John Wiley & Sons, Ltd.     

Scaling improves stability of preconditioned CG‐like solvers for FE consolidation equations

Preconditioned projection (or conjugate gradient like) methods are increasingly used for the accurate and efficient solution to finite element (FE) coupled consolidation equations. Theory indicates that preliminary row/column scaling does not affect the eigenspectrum of the iteration matrix controlling convergence as long as the preconditioner relies on the incomplete factorization of the FE coefficient matrix. However, computational experience with mid‐large size problems shows that the above inexpensive operation can significantly accelerate the solver convergence, and to a minor extent also improve the final accuracy, as a result of a better solver stability to the accumulation and propagation of floating point round‐off errors. This is demonstrated with the aid of the least square logarithm (LSL) scaling algorithm on FE consolidation problems of increasing size up to more than 100 000. It is shown that a major source of numerical instability rests with the sub‐matrix which couples the structural to the fluid part of the underlying mathematical model. It is concluded that for mid‐large size, possibly difficult, FE consolidation problems left/right LSL scaling is to be always recommended when the incomplete factorization is used as a preconditioning technique. Copyright © 2003 John Wiley & Sons, Ltd.     

Numerical performance of projection methods in finite element consolidation models

Projection, or conjugate gradient like, methods are becoming increasingly popular for the efficient solution of large sparse sets of unsymmetric indefinite equations arising from the numerical integration of (initial) boundary value problems. One such problem is soil consolidation coupling a flow and a structural model, typically solved by finite elements (FE) in space and a marching scheme in time (e.g. the Crank–Nicolson scheme). The attraction of a projection method stems from a number of factors, including the ease of implementation, the requirement of limited core memory and the low computational cost if a cheap and effective matrix preconditioner is available. In the present paper, biconjugate gradient stabilized (Bi‐ CGSTAB) is used to solve FE consolidation equations in 2‐D and 3‐D settings with variable time integration steps. Three different nodal orderings are selected along with the preconditioner ILUT based on incomplete triangular factorization and variable fill‐in. The overall cost of the solver is made up of the preconditioning cost plus the cost to converge which is in turn related to the number of iterations and the elementary operations required by each iteration. The results show that nodal ordering affects the perfor mance of Bi‐CGSTAB. For normally conditioned consolidation problems Bi‐CGSTAB with the best ILUT preconditioner may converge in a number of iterations up to two order of magnitude smaller than the size of the FE model and proves an accurate, cost‐effective and robust alternative to direct methods. Copyright © 2001 John Wiley & Sons, Ltd.     

Parallel solution to ill‐conditioned FE geomechanical problems

Parallel computers are potentially very attractive for the implementation of large size geomechanical models. One of the main difficulties of parallelization, however, relies on the efficient solution of the frequently ill‐conditioned algebraic system arising from the linearization of the discretized equilibrium equations. While very efficient preconditioners have been developed for sequential computers, not much work has been devoted to parallel solution algorithms in geomechanics. The present study investigates the state‐of‐the‐art performance of the factorized sparse approximate inverse (FSAI) as a preconditioner for the iterative solution of ill‐conditioned geomechanical problems. Pre‐and post‐filtration strategies are experimented with to increase the FSAI efficiency. Numerical results show that FSAI exhibits a promising potential for parallel geomechanical models mainly because of its almost ideal scalability. With the present formulation, however, at least 4 or 8 processors are required in the selected test cases to outperform one of the most efficient sequential algorithms available for FE geomechanics, i.e. the multilevel incomplete factorization (MIF). Further research is needed to improve the FSAI efficiency with a more effective selection of the preconditioner non‐zero pattern. Copyright © 2011 John Wiley & Sons, Ltd.     

基于粗细网格的有限元并行分析方法

并行计算己成为求解大规模岩土工程问题的一种强大趋势。探讨了粗细网格与预处理共轭梯度法结合的并行有限元算法。从多重网格刚度矩阵推得有效的预处理子。该算法在工作站机群上实现。用地基处理时土体强夯的数值模拟分析进行了数值测试,对其并行性能进行了详细分析。计算结果表明：该算法具有良好的并行加速比和效率,是一种有效的并行算法。     

A supercoarsening multigrid method for poroelasticity in 3D coupled flow and geomechanics modeling

The Galerkin finite-element discretization of the force balance equation typically leads to large linear systems for geomechanical problems with realistic dimensions. In iteratively coupled flow and geomechanics modeling, a large linear system is solved at every timestep often multiple times during coupling iterations. The iterative solution of the linear system stemming from the poroelasticity equations constitutes the most time-consuming and memory-intensive component of coupled modeling. Block Jacobi, LSOR, and Incomplete LU factorization are popular preconditioning techniques used for accelerating the iterative solution of the poroelasticity linear systems. However, the need for more effective, efficient, and robust iterative solution techniques still remains especially for large coupled modeling problems requiring the solution of the poroelasticity system for a large number of timesteps. We developed a supercoarsening multigrid method (SCMG) which can be multiplicatively combined with commonly used preconditioning techniques. SCMG has been tested on a variety of coupled flow and geomechanics problems involving single-phase depletion and multiphase displacement of in-situ hydrocarbons, CO₂ injection, and extreme material property contrasts. Our analysis indicates that the SCMG consistently improves the convergence properties of the linear systems arising from the poroelasticity equations, and thus, accelerates the coupled simulations for all cases subject to investigation. The joint utilization of the two-level SCMG with the ILU1 preconditioner emerges as the most optimal preconditioning/iterative solution strategy in a great majority of the problems evaluated in this work. The BiCGSTAB iterative solver converges more rapidly compared to PCG in a number of test cases, in which various SCMG-accelerated preconditioning strategies are applied to both iterators.     

GPU-accelerated iterative solutions for finite element analysis of soil–structure interaction problems

Soil–structure interaction problems are commonly encountered in engineering practice, and the resulting linear systems of equations are difficult to solve due to the significant material stiffness contrast. In this study, a novel partitioned block preconditioner in conjunction with the Krylov subspace iterative method symmetric quasiminimal residual is proposed to solve such linear equations. The performance of these investigated preconditioners is evaluated and compared on both the CPU architecture and the hybrid CPU–graphics processing units (GPU) computing environment. On the hybrid CPU–GPU computing platform, the capability of GPU in parallel implementation and high-intensity floating point operations is exploited to accelerate the iterative solutions, and particular attention is paid to the matrix–vector multiplications involved in the iterative process. Based on a pile-group foundation example and a tunneling example, numerical results show that the partitioned block preconditioners investigated are very efficient for the soil–structure interaction problems. However, their comparative performances may apparently depend on the computer architecture. When the CPU computer architecture is used, the novel partitioned block symmetric successive over-relaxation preconditioner appears to be the most efficient, but when the hybrid CPU–GPU computer architecture is adopted, it is shown that the inexact block diagonal preconditioners embedded with simple diagonal approximation to the soil block outperform the others.     

A parallel block preconditioner for large-scale poroelasticity with highly heterogeneous material parameters

Large-scale simulations of coupled flow in deformable porous media require iterative methods for solving the systems of linear algebraic equations. Construction of efficient iterative methods is particularly challenging in problems with large jumps in material properties, which is often the case in realistic geological applications, such as basin evolution at regional scales. The success of iterative methods for such problems depends strongly on finding effective preconditioners with good parallel scaling properties, which is the topic of the present paper. We present a parallel preconditioner for Biot’s equations of coupled elasticity and fluid flow in porous media. The preconditioner is based on an approximation of the exact inverse of the two-by-two block system arising from a finite element discretisation. The approximation relies on a highly scalable approximation of the global Schur complement of the coefficient matrix, combined with generally available state-of-the-art multilevel preconditioners for the individual blocks. This preconditioner is shown to be robust on problems with highly heterogeneous material parameters. We investigate the weak and strong parallel scaling of this preconditioner on up to 512 processors and demonstrate its ability on a realistic basin-scale problem in poroelasticity with over eight million tetrahedral elements.     

Block-preconditioned Newton–Krylov solvers for fully coupled flow and geomechanics

The focus of this work is efficient solution methods for mixed finite element models of variably saturated fluid flow through deformable porous media. In particular, we examine preconditioning techniques to accelerate the convergence of implicit Newton–Krylov solvers. We highlight an approach in which preconditioners are built from block-factorizations of the coupled system. The key result of the work is the identification of effective preconditioners for the various sub-problems that appear within the block decomposition. We use numerical examples drawn from both linear and nonlinear hydromechanical models to test the robustness and scalability of the proposed methods. Results demonstrate that an algebraic multigrid variant of the block preconditioner leads to mesh-independent convergence, good parallel efficiency, and insensitivity to the material parameters of the medium.     

Decoupling and Block Preconditioning for Sedimentary Basin Simulations

The simulation of sedimentary basins aims at reconstructing its historical evolution in order to provide quantitative predictions about phenomena leading to hydrocarbon accumulations. The kernel of this simulation is the numerical solution of a complex system of partial differential equations of mixed parabolic–hyperbolic type. A discretisation and linearisation of this system leads to large ill-conditioned nonsymmetric linear systems with three unknowns per mesh element. The preconditioning which we will present for these systems consists in three stages: (i) a local decoupling of the equations which (in addition) aims at concentrating the elliptic part of the system in the “pressure block”; (ii) an efficient preconditioning of the pressure block using AMG; (iii) the “recoupling” of the equations. In all our numerical tests on real case studies we observed a reduction of the CPU-time for the linear solver (up to a factor 4.3 with respect to the current preconditioner ILU(0)) and almost no degradation with respect to physical and numerical parameters. This revised version was published online in July 2006 with corrections to the Cover Date.     

大区域地下水模拟的预优并行GMRES(m)算法研究

大区域研究区由于涉及范围大、水文地质参数复杂多变,一直是进行地下水数值模拟的热点和难点。针对大区域地下水模拟的特点,在MPI环境中对Krylov子空间GMRES(m)算法的并行性进行分析,提出基于区域分解法的并行实现策略,并对不同的预条件子的加速效果进行比较。数值实验结果表明:并行GMRES(m)算法在求解大区域三维地下水模型时可以显著的加快求解速度,且具有较好的可扩展性。另外,Jacobi预条件子与GMRES算法的组合具有更优的加速比和执行效率,是一种求解大型化、复杂化地下水水流问题的可行方案。     

Modelling transient heat and moisture transfer in unsaturated soil using a parallel computing approach

A parallel numerical model, employing a finite difference explicit scheme for the analysis of coupled heat and moisture transfer in unsaturated soil, is employed to simulate a laboratory experiment of heating of medium sand. The model, written in a two-dimensional polar co-ordinate formulation, is programmed in the concurrent language Occam and executed on a parallel computing network of transputers. Parallelization is adopted as a means of overcoming computing difficulties, which limited numerical solutions to those at steady state, to enable transient behaviour to be simulated. The parallel algorithm was found to be very efficient, enabling a full solution of transient behaviour to be obtained. An investigation of the ability of the model to accurately simulate the complex, interrelated coupled nature of both two-dimensional transient and steady-state behaviour yielded very good correlation between experimental and numerical results. It can therefore be concluded that overall the results obtained provide confidence in the validity of the approach proposed.     

Quasi-Monte Carlo integration on the grid for sensitivity studies

In this paper we present error and performance analysis of quasi-Monte Carlo algorithms for solving multidimensional integrals (up to 100 dimensions) on the grid using MPI. We take into account the fact that the Grid is a potentially heterogeneous computing environment, where the user does not know the specifics of the target architecture. Therefore parallel algorithms should be able to adapt to this heterogeneity, providing automated load-balancing. Monte Carlo algorithms can be tailored to such environments, provided parallel pseudorandom number generators are available. The use of quasi-Monte Carlo algorithms poses more difficulties. In both cases the efficient implementation of the algorithms depends on the functionality of the corresponding packages for generating pseudorandom or quasirandom numbers. We propose efficient parallel implementation of the Sobol sequence for a grid environment and we demonstrate numerical experiments on a heterogeneous grid. To achieve high parallel efficiency we use a newly developed special grid service called Job Track Service which provides efficient management of available computing resources through reservations.     

An MSSS-preconditioned matrix equation approach for the time-harmonic elastic wave equation at multiple frequencies

In this work, we present a new numerical framework for the efficient solution of the time-harmonic elastic wave equation at multiple frequencies. We show that multiple frequencies (and multiple right-hand sides) can be incorporated when the discretized problem is written as a matrix equation. This matrix equation can be solved efficiently using the preconditioned IDR(s) method. We present an efficient and robust way to apply a single preconditioner using MSSS matrix computations. For 3D problems, we present a memory-efficient implementation that exploits the solution of a sequence of 2D problems. Realistic examples in two and three spatial dimensions demonstrate the performance of the new algorithm.     

Performance of Jacobi preconditioning in Krylov subspace solution of finite element equations

This paper examines the performance of the Jacobi preconditioner when used with two Krylov subspace iterative methods. The number of iterations needed for convergence was shown to be different for drained, undrained and consolidation problems, even for similar condition number. The differences were due to differences in the eigenvalue distribution, which cannot be completely described by the condition number alone. For drained problems involving large stiffness ratios between different material zones, ill‐conditioning is caused by these large stiffness ratios. Since Jacobi preconditioning operates on degrees‐of‐freedom, it effectively homogenizes the different spatial sub‐domains. The undrained problem, modelled as a nearly incompressible problem, is much more resistant to Jacobi preconditioning, because its ill‐conditioning arises from the large stiffness ratios between volumetric and distortional deformational modes, many of which involve the similar spatial domains or sub‐domains. The consolidation problem has two sets of degrees‐of‐freedom, namely displacement and pore pressure. Some of the eigenvalues are displacement dominated whereas others are excess pore pressure dominated. Jacobi preconditioning compresses the displacement‐dominated eigenvalues in a similar manner as the drained problem, but pore‐pressure‐dominated eigenvalues are often over‐scaled. Convergence can be accelerated if this over‐scaling is recognized and corrected for. Copyright © 2002 John Wiley & Sons, Ltd.     

Mixed precision parallel preconditioner and linear solver for compositional reservoir simulation

Reservoir simulation role in value creation and strategic management decisions cannot be over emphasized. Simulation of complex challenging reservoirs with millions of grid blocks especially in compositional mode is very time-consuming even with fast modern computers. On the other hand, high price of cluster supercomputers prevents them for being commonly used for fast simulation of such reservoirs. In recent years, the development of many-core processors like cell processors, DSPs, and graphical processing units (GPUs) has provided a very cost-effective hardware platform for fast computational operations. However, programming for such processors is much more difficult than conventional CPUs, and new parallel algorithm design and special parallel implementation methods are needed. Using the computational power of CPUs, GPUs, and/or any other processing unit, Open Computing Language (OpenCL) provides a framework for programming for heterogeneous platforms. In this paper, OpenCL is used to employ the computational power of a GPU to build a preconditioner and solve the linear system arising from compositional formulation of multiphase flow in porous media. The proposed parallel preconditioner is proved to be quite effective, even in heterogeneous porous media. Using data-parallel modules on GPU, the preconditioner/solver runtime reduced at least 1 order of magnitude compared to their serial implementation on CPU.     

The analysis of consolidation by a quasi-Newton technique

A quasi-Newton algorithm is implemented for the solution of multi-dimensional, linear consolidation problems. The study is motivated by the need to implement an efficient equation-solving technique for the solution of large systems of equations typical in problems of consolidation of saturated porous media. The proposed procedure obviates the need to reassemble and re-factorize the global coefficient matrix every load increment, albeit the time step may be held variable in the analysis. The method employs the combined techniques of ‘line search’ and BFGS updates applied to the coupled equations. A numerical example is presented to show that the proposed method is computationally more efficient than the conventional direct equation-solving scheme, particularly when solving large systems of finite element equations.     

The role of preconditioning in the solution to FE coupled consolidation equations by Krylov subspace methods

The repeated solution in time of the linear system arising from the finite element integration of coupled consolidation equations is a major computational effort. This system can be written in either a symmetric or an unsymmetric form, thus calling for the implementation of different preconditioners and Krylov subspace solvers. The present paper aims at investigating when either a symmetric or an unsymmetric approach should be better used. The results from a number of representative numerical experiments indicate that a major role in selecting either form is played by the preconditioner rather than by the Krylov subspace method itself. Two other important issues addressed are the size of the time integration step and the possible lumping of the flow capacity matrix. It appears that ad hoc block constrained preconditioners provide the most robust algorithm independently of the time step size, lumping, and symmetry. Copyright © 2008 John Wiley & Sons, Ltd.     

A parallel, implicit, cell‐centered method for two‐phase flow with a preconditioned Newton–Krylov solver

A new parallel solution technique is developed for the fully implicit three‐dimensional two‐phase flow model. An expandedcell‐centered finite difference scheme which allows for a full permeability tensor is employed for the spatial discretization, and backwardEuler is used for the time discretization. The discrete systems are solved using a novel inexact Newton method that reuses the Krylov information generated by the GMRES linear iterative solver. Fast nonlinear convergence can be achieved by composing inexact Newton steps with quasi‐Newton steps restricted to the underlying Krylov subspace. Furthermore, robustness and efficiency are achieved with a line‐search backtracking globalization strategy for the nonlinear systems and a preconditioner for each coupled linear system to be solved. This inexact Newton method also makes use of forcing terms suggested by Eisenstat and Walker which prevent oversolving of the Jacobian systems. The preconditioner is a new two‐stage method which involves a decoupling strategy plus the separate solutions of both nonwetting‐phase pressure and saturation equations. Numerical results show that these nonlinear and linear solvers are very effective.     

A modified Jacobi preconditioner for solving ill‐conditioned Biot's consolidation equations using symmetric quasi‐minimal residual method

This paper identifies imbalanced columns (or rows) as a significant source of ill‐conditioning in the preconditioned coefficient matrix using the standard Jacobi preconditioner, for finite element solution of Biot's consolidation equations. A simple and heuristic preconditioner is proposed to reduce this source of ill‐conditioning. The proposed preconditioner modifies the standard Jacobi preconditioner by scaling the excess pore pressure degree‐of‐freedoms in the standard Jacobi preconditioner with appropriate factors. The performance of such preconditioner is examined using the symmetric quasi‐minimal residual method. To alleviate storage requirements, element‐by‐element iterative strategies are implemented. Numerical experiment results show that the proposed preconditioner reduces both the number of iteration and CPU execution time significantly as compared with the standard Jacobi preconditioner. Copyright © 2001 John Wiley & Sons, Ltd.