Global‐basis two‐level method for indefinite systems. Part 2: computational issues

Algorithmic aspects and computational efficiency of the global‐basis two‐level method are investigated in the context of symmetric indefinite system of equations. The algorithm includes efficient construction of the global‐basis prolongator using Lanczos vectors, predictor–corrector smoothing procedures, and a heuristic two‐level feedback loop aimed at ensuring convergence. Numerical experiments consisting of 3D Helmholtz equations and shear banding problems with strain softening demonstrate the excellent performance of the method. Copyright © 2000 John Wiley & Sons, Ltd.     

Global‐basis two‐level method for indefinite systems. Part 1: convergence studies

A robust two‐level solver for high indefinite system of equations arising from the finite element discretization is developed. It is shown that the optimal coarse model is spanned by the spectrum of the highest eigenmodes of the smoothing iteration matrix. Convergence studies conducted on a model prolongation operator reveal pathological sensitivity to any deviation from the optimal coarse model. Copyright © 2000 John Wiley & Sons, Ltd.     

An algebraic two‐level preconditioner for asymmetric,positive‐definite systems

A two‐level, linear algebraic solver for asymmetric, positive‐definite systems is developed using matrices arising from stabilized finite element formulations to motivate the approach. Supported by an analysis of a representative smoother, the parent space is divided into oscillatory and smooth subspaces according to the eigenvectors of the associated normal system. Using a mesh‐based aggregation technique, which relies only on information contained in the matrix, a restriction/prolongation operator is constructed. Various numerical examples, on both structured and unstructured meshes, are performed using the two‐level cycle as the basis for a preconditioner. Results demonstrate the complementarity between the smoother and the coarse‐level correction as well as convergence rates that are nearly independent of the problem size. Copyright © 2001 John Wiley & Sons, Ltd.     

Multifrontal incomplete factorization for indefinite and complex symmetric systems

A new class of preconditioners based on the adaptive threshold incomplete multifrontal factorization for indefinite and complex symmetric systems is developed. Numerical experiments consisting of the 3D Helmholtz equations, fluid–structure interaction and localization problems demonstrate the excellent performance of the preconditioner. Copyright © 2001 John Wiley & Sons, Ltd.     

Block preconditioners for symmetric indefinite linear systems

This paper presents a systematic theoretical and numerical evaluation of three common block preconditioners in a Krylov subspace method for solving symmetric indefinite linear systems. The focus is on large‐scale real world problems where block approximations are a practical necessity. The main illustration is the performance of the block diagonal, constrained, and lower triangular preconditioners over a range of block approximations for the symmetric indefinite system arising from large‐scale finite element discretization of Biot's consolidation equations. This system of equations is of fundamental importance to geomechanics. Numerical studies show that simple diagonal approximations to the (1,1) block K and inexpensive approximations to the Schur complement matrix S may not always produce the most spectacular time savings when K is explicitly available, but is able to deliver reasonably good results on a consistent basis. In addition, the block diagonal preconditioner with a negative (2,2) block appears to be reasonably competitive when compared to the more complicated ones. These observation are expected to remain valid for coefficient matrices whereby the (1,1) block is sparse, diagonally significant (a notion weaker than diagonal dominance), moderately well‐conditioned, and has a much larger block size than the (2,2) block. Copyright © 2004 John Wiley & Sons, Ltd.     

A parallel two‐level domain decomposition based one‐shot method for shape optimization problems

A two‐level domain decomposition method is introduced for general shape optimization problems constrained by the incompressible Navier–Stokes equations. The optimization problem is first discretized with a finite element method on an unstructured moving mesh that is implicitly defined without assuming that the computational domain is known and then solved by some one‐shot Lagrange–Newton–Krylov–Schwarz algorithms. In this approach, the shape of the domain, its corresponding finite element mesh, the flow fields and their corresponding Lagrange multipliers are all obtained computationally in a single solve of a nonlinear system of equations. Highly scalable parallel algorithms are absolutely necessary to solve such an expensive system. The one‐level domain decomposition method works reasonably well when the number of processors is not large. Aiming for machines with a large number of processors and robust nonlinear convergence, we introduce a two‐level inexact Newton method with a hybrid two‐level overlapping Schwarz preconditioner. As applications, we consider the shape optimization of a cannula problem and an artery bypass problem in 2D. Numerical experiments show that our algorithm performs well on a supercomputer with over 1000 processors for problems with millions of unknowns. Copyright © 2014 John Wiley & Sons, Ltd.     

FETI‐DP: a dual–primal unified FETI method—part I: A faster alternative to the two‐level FETI method

The FETI method and its two‐level extension (FETI‐2) are two numerically scalable domain decomposition methods with Lagrange multipliers for the iterative solution of second‐order solid mechanics and fourth‐order beam, plate and shell structural problems, respectively.The FETI‐2 method distinguishes itself from the basic or one‐level FETI method by a second set of Lagrange multipliers that are introduced at the subdomain cross‐points to enforce at each iteration the exact continuity of a subset of the displacement field at these specific locations. In this paper, we present a dual–primal formulation of the FETI‐2 concept that eliminates the need for that second set of Lagrange multipliers, and unifies all previously developed one‐level and two‐level FETI algorithms into a single dual–primal FETI‐DP method. We show that this new FETI‐DP method is numerically scalable for both second‐order and fourth‐order problems. We also show that it is more robust and more computationally efficient than existing FETI solvers, particularly when the number of subdomains and/or processors is very large. Copyright © 2001 John Wiley & Sons, Ltd.     

A FETI‐DP method for the parallel iterative solution of indefinite and complex‐valued solid and shell vibration problems

The dual‐primal finite element tearing and interconnecting (FETI‐DP) domain decomposition method (DDM) is extended to address the iterative solution of a class of indefinite problems of the form ( K ?σ² M ) u = f , and a class of complex problems of the form ( K ?σ² M +iσ D ) u = f , where K , M , and D are three real symmetric matrices arising from the finite element discretization of solid and shell dynamic problems, i is the imaginary complex number, and σ is a real positive number. A key component of this extension is a new coarse problem based on the free‐space solutions of Navier's equations of motion. These solutions are waves, and therefore the resulting DDM is reminiscent of the FETI‐H method. For this reason, it is named here the FETI‐DPH method. For a practically large σ range, FETI‐DPH is shown numerically to be scalable with respect to all of the problem size, substructure size, and number of substructures. The CPU performance of this iterative solver is illustrated on a 40‐processor computing system with the parallel solution, for various σ ranges, of several large‐scale, indefinite, or complex‐valued systems of equations associated with shifted eigenvalue and forced frequency response structural dynamics problems. Copyright © 2005 John Wiley & Sons, Ltd.     

A robust control chart for simple linear profiles in two‐stage processes

In many manufacturing systems, the final product is the result of several dependent stages. In particular, in multistage processes, the quality characteristics of downstream stages are influenced by those in the earlier stages (upstream). This property is referred to as the cascade property, which, if disregarded in process monitoring, may bring about misleading results for the subsequent fault diagnosis. Considering the relationships among consecutive stages of the process, the U statistic is the most widely used method for monitoring multistage processes. Using this method, our paper deals with monitoring a two‐stage process where quality characteristics are represented as simple linear profiles. To guard against the detrimental effect of contaminated data in the phase I of statistical process control, two well‐known robust M‐estimators, including Huber's and bi‐square, are employed for estimation of the process parameters. Under different degrees of autocorrelation across stages of the process and also for different contamination rates, the performances of the proposed methods are compared with that of the conventional least‐square method. From the viewpoint of estimation performance measures, including unbiasedness and efficiency, along with the capability of the control chart in identifying the true source of variation, extensive simulation results reveal that robust estimators outperform the traditional method in a two‐stage process. Meanwhile, it should be noted when there is contamination only in the first stage of the process, the least‐square method performs slightly better.     

Analysis of two‐grid methods for reaction‐diffusion equations by expanded mixed finite element methods

We present two efficient methods of two‐grid scheme for the approximation of two‐dimensional semi‐linear reaction‐diffusion equations using an expanded mixed finite element method. To linearize the discretized equations, we use two Newton iterations on the fine grid in our methods. Firstly, we solve an original non‐linear problem on the coarse grid. Then we use twice Newton iterations on the fine grid in our first method, and while in second method we make a correction on the coarse grid between two Newton iterations on the fine grid. These two‐grid ideas are from Xu's work (SIAM J. Sci. Comput. 1994; 15 :231–237; SIAM J. Numer. Anal. 1996; 33 :1759–1777) on standard finite element method. We extend the ideas to the mixed finite element method. Moreover, we obtain the error estimates for two algorithms of two‐grid method. It is showed that coarse space can be extremely coarse and we achieve asymptotically optimal approximation as long as the mesh sizes satisfy H =??(h^¼) in the first algorithm and H =??(h^?) in second algorithm. Copyright © 2006 John Wiley & Sons, Ltd.     

Estimation of missing observations in two‐level split‐plot designs

Inserting estimates for the missing observations from split‐plot designs restores their balanced or orthogonal structure and alleviates the difficulties in the statistical analysis. In this article, we extend a method due to Draper and Stoneman to estimate the missing observations from unreplicated two‐level factorial and fractional factorial split‐plot (FSP and FFSP) designs. The missing observations, which can either be from the same whole plot, from different whole plots, or comprise entire whole plots, are estimated by equating to zero a number of specific contrast columns equal to the number of the missing observations. These estimates are inserted into the design table and the estimates for the remaining effects (or alias chains of effects as the case with FFSP designs) are plotted on two half‐normal plots: one for the whole‐plot effects and the other for the subplot effects. If the smaller effects do not point at the origin, then different contrast columns to some or all of the initial ones should be discarded and the plots re‐examined for bias. Using examples, we show how the method provides estimates for the missing observations that are very close to their actual values. Copyright © 2007 John Wiley & Sons, Ltd.     

On a two‐level Newton‐type procedure applied for solving non‐linear elasticity problems

The present work is devoted to the damped Newton method applied for solving a class of non‐linear elasticity problems. Following the approach suggested in earlier related publications, we consider a two‐level procedure which involves (i) solving the non‐linear problem on a coarse mesh, (ii) interpolating the coarse‐mesh solution to the fine mesh, (iii) performing non‐linear iterations on the fine mesh. Numerical experiments suggest that in the case when one is interested in the minimization of the L₂‐norm of the error rather than in the minimization of the residual norm the coarse‐mesh solution gives sufficiently accurate approximation to the displacement field on the fine mesh, and only a few (or even just one) of the costly non‐linear iterations on the fine mesh are needed to achieve an acceptable accuracy of the solution (the accuracy which is of the same order as the accuracy of the Galerkin solution on the fine mesh). Copyright © 2000 John Wiley & Sons, Ltd.     

Multi‐level incomplete factorizations for the iterative solution of non‐linear finite element problems

Several engineering applications give rise quite naturally to linearized FE systems of equations possessing a multi‐level structure. An example is provided by geomechanical models of layered and faulted geological formations. For such problems the use of a multi‐level incomplete factorization (MIF) as a preconditioner for Krylov subspace methods can prove a robust and efficient solution accelerator, allowing for a fine tuning of the fill‐in degree with a significant improvement in both the solver performance and the memory consumption. The present paper develops two novel MIF variants for the solution of multi‐level symmetric positive definite systems. Two correction algorithms are proposed with the aim of preserving the positive definiteness of the preconditioner, thus avoiding possible breakdowns of the preconditioned conjugate gradient solver. The MIF variants are experimented with in the solution of both a single system and a long‐term quasi‐static simulation dealing with a multi‐level geomechanical application. The numerical results show that MIF typically outperforms by up to a factor 3 a more traditional algebraic preconditioner such as an incomplete Cholesky factorization with partial fill‐in. The advantage is emphasized in a long‐term simulation where the fine fill‐in tuning allowed for by MIF yields a significant improvement for the computer memory requirement as well. Copyright © 2009 John Wiley & Sons, Ltd.     

Transformation properties of an indefinite media slab for paraxial beams

On the basis of paraxial beam propagation theory in indefinite media, the effective refraction index for both of the two types of polarized electromagnetic wave, TE and TM waves, are introduced. According to the definition of effective refraction index, we obtain the conditions that paraxial beams pass through the indefinite media. We propose to employ a slab of indefinite media to construct a polarizer or polarizing beam splitter by choosing appropriate anisotropic parameters. Under certain conditions, the indefinite media slab exhibits polarization-selective focusing effect.     

Extended discontinuous Galerkin methods for two‐phase flows: the spatial discretization

This work discusses a discontinuous Galerkin (DG) discretization for two‐phase flows. The fluid interface is represented by a level set, and the DG approximation space is adapted such that jumps and kinks in pressure and velocity fields can be approximated sharply. This adaption of the original DG space, which can be performed ‘on‐the‐fly’ for arbitrary interface shapes, is referred to as extended discontinuous Galerkin. By combining this ansatz with a special quadrature technique, one can regain spectral convergence properties for low‐regularity solutions, which is demonstrated by numerical examples. This work focuses on the aspects of spatial discretization, and special emphasis is devoted on how to overcome problems related to quadrature, small cut cells, and condition number of linear systems. Temporal discretization will be discussed in future works. Copyright © 2016 John Wiley & Sons, Ltd.     

A comparison of transformation methods for evaluating two‐dimensional weakly singular integrals

Accurate numerical evaluation of integrals arising in the boundary element method is fundamental to achieving useful results via this solution technique. In this paper, a number of techniques are considered to evaluate the weakly singular integrals which arise in the solution of Laplace's equation in three dimensions and Poisson's equation in two dimensions. Both are two‐dimensional weakly singular integrals and are evaluated using (in a product fashion) methods which have recently been used for evaluating one‐dimensional weakly singular integrals arising in the boundary element method. The methods used are based on various polynomial transformations of conventional Gaussian quadrature points where the transformation polynomial has zero Jacobian at the singular point. Methods which split the region of integration into sub‐regions are considered as well as non‐splitting methods. In particular, the newly introduced and highly accurate generalized composite subtraction of singularity and non‐linear transformation approach (GSSNT) is applied to various two‐dimensional weakly singular integrals. A study of the different methods reveals complex relationships between transformation orders, position of the singular point, integration kernel and basis function. It is concluded that the GSSNT method gives the best overall results for the two‐dimensional weakly singular integrals studied. Copyright © 2002 John Wiley & Sons, Ltd.     

New two‐dimensional slope limiters for discontinuous Galerkin methods on arbitrary meshes

In this paper, we introduce an extension of Van Leer's slope limiter for two‐dimensional discontinuous Galerkin (DG) methods on arbitrary unstructured quadrangular or triangular grids. The aim is to construct a non‐oscillatory shock capturing DG method for the approximation of hyperbolic conservative laws without adding excessive numerical dispersion. Unlike some splitting techniques that are limited to linear approximations on rectangular grids, in this work, the solution is approximated by means of piecewise quadratic functions. The main idea of this new reconstructing and limiting technique follows a well‐known approach where local maximum principle regions are defined by enforcing some constraints on the reconstruction of the solution. Numerical comparisons with some existing slope limiters on structured as well as on unstructured meshes show a superior accuracy of our proposed slope limiters. Copyright © 2004 John Wiley & Sons, Ltd.     

On a two‐level finite element method for the incompressible Navier–Stokes equations

We consider the Galerkin finite element method for the incompressible Navier–Stokes equations in two dimensions, where the finite‐dimensional space(s) employed consist of piecewise polynomials enriched with residual‐free bubble functions. To find the bubble part of the solution, a two‐level finite element method (TLFEM) is described and its application to the Navier–Stokes equation is displayed. Numerical solutions employing the TLFEM are presented for three benchmark problems. We compare the numerical solutions using the TLFEM with the numerical solutions using a stabilized method. Copyright © 2001 John Wiley & Sons, Ltd.     

A two‐level domain decomposition method with accurate interface conditions for the Helmholtz problem

A new and efficient two‐level, non‐overlapping domain decomposition (DD) method is developed for the Helmholtz equation in the two Lagrange multiplier framework. The transmission conditions are designed by utilizing perfectly matched discrete layers (PMDLs), which are a more accurate representation of the exterior Dirichlet‐to‐Neumann map than the polynomial approximations used in the optimized Schwarz method. Another important ingredient affecting the convergence of a DD method, namely, the coarse space augmentation, is also revisited. Specifically, the widely successful approach based on plane waves is modified to that based on interface waves, defined directly on the subdomain boundaries, hence ensuring linear independence and facilitating the estimation of the optimal size for the coarse problem. The effectiveness of both PMDL‐based transmission conditions and interface‐wave‐based coarse space augmentation is illustrated with an array of numerical experiments that include comprehensive scalability studies with respect to frequency, mesh size and the number of subdomains. Copyright © 2015 John Wiley & Sons, Ltd.     

A scalable multi‐level preconditioner for matrix‐free µ‐finite element analysis of human bone structures

The recent advances in microarchitectural bone imaging disclose the possibility to assess both the apparent density and the trabecular microstructure of intact bones in a single measurement. Coupling these imaging possibilities with microstructural finite element (µFE) analysis offers a powerful tool to improve bone stiffness and strength assessment for individual fracture risk prediction. Many elements are needed to accurately represent the intricate microarchitectural structure of bone; hence, the resulting µFE models possess a very large number of degrees of freedom. In order to be solved quickly and reliably on state‐of‐the‐art parallel computers, the µFE analyses require advanced solution techniques. In this paper, we investigate the solution of the resulting systems of linear equations by the conjugate gradient algorithm, preconditioned by aggregation‐based multigrid methods. We introduce a variant of the preconditioner that does not need assembling the system matrix but uses element‐by‐element techniques to build the multilevel hierarchy. The preconditioner exploits the voxel approach that is common in bone structure analysis, and it has modest memory requirements, at the same time robust and scalable. Using the proposed methods, we have solved in 12min a model of trabecular bone composed of 247 734 272 elements, yielding a matrix with 1 178 736 360 rows, using 1024 CRAY XT3 processors. The ability to solve, for the first time, large biomedical problems with over 1 billion degrees of freedom on a routine basis will help us improve our understanding of the influence of densitometric, morphological, and loading factors in the etiology of osteoporotic fractures such as commonly experienced at the hip, spine, and wrist. Copyright © 2007 John Wiley & Sons, Ltd.