Evaluation of three unstructured multigrid methods on 3D finite element problems in solid mechanics

Multigrid has been a popular solver method for finite element and finite difference problems with regular grids for over 20 years. The application of multigrid to unstructured grid problems, in which it is often difficult or impossible for the application to provide coarse grids, is not as well understood. In particular, methods that are designed to require only data that are easily available in most finite element applications (i.e. fine grid data), constructing the grid transfer operators and coarse grid operators internally, are of practical interest. We investigate three unstructured multigrid methods that show promise for challenging problems in 3D elasticity: (1) non‐nested geometric multigrid, (2) smoothed aggregation, and (3) plain aggregation algebraic multigrid. This paper evaluates the effectiveness of these three methods on several unstructured grid problems in 3D elasticity with up to 76 million degrees of freedom. Published in 2002 by John Wiley & Sons, Ltd.     

广义特征值问题求解的改进Ｒｉｔｚ向量法

从提高算法的稳定性和计算效率入手,采取迭代及防止漏根、多根的措施,对传统的Ｒｉｔｚ向量法进行改进,提出改进的Ｒｉｔｚ向量法。此算法仅需生成ｒ维的Ｋｒｙｌｏｖ空间,大大降低投影矩阵阶数,减少投影矩阵特征值计算时间。引入重正交方案和模态比较法,并给出Ｒｉｔｚ向量块宽ｑ与生成步数ｒ的建议取值。最后通过四参数的谱变换法,不     

Inexact Schwarz‐algebraic multigrid preconditioners for crack problems modeled by extended finite element methods

Traditional algebraic multigrid (AMG) preconditioners are not well suited for crack problems modeled by extended finite element methods (XFEM). This is mainly because of the unique XFEM formulations, which embed discontinuous fields in the linear system by addition of special degrees of freedom. These degrees of freedom are not properly handled by the AMG coarsening process and lead to slow convergence. In this paper, we proposed a simple domain decomposition approach that retains the AMG advantages on well‐behaved domains by avoiding the coarsening of enriched degrees of freedom. The idea was to employ a multiplicative Schwarz preconditioner where the physical domain was partitioned into “healthy” (or unfractured) and “cracked” subdomains. First, the “healthy” subdomain containing only standard degrees of freedom, was solved approximately by one AMG V‐cycle, followed by concurrent direct solves of “cracked” subdomains. This strategy alleviated the need to redesign special AMG coarsening strategies that can handle XFEM discretizations. Numerical examples on various crack problems clearly illustrated the superior performance of this approach over a brute force AMG preconditioner applied to the linear system. Copyright © 2011 John Wiley & Sons, Ltd.     

广义特征值问题的快速傅里叶变换法

针对广义特征值问题提出离散傅里叶变换法。该方法把结构的动力响应看作是一种信号,利用快速傅里叶变换进行分析,从而得到结构的振动频率。该方法避免对刚度矩阵求逆,可同时计算出所有的特征值,是一种直接方法。数值算例验证了该方法的正确性。     

Efficient preconditioners for boundary element matrices based on grey‐box algebraic multigrid methods

This paper is concerned with the iterative solution of the boundary element equations arising from standard Galerkin boundary element discretizations of first‐kind boundary integral operators of positive and negative order. We construct efficient preconditioners on the basis of so‐called grey‐box algebraic multigrid methods that are well adapted to the treatment of boundary element matrices. In particular, the coarsening is based on an auxiliary matrix that represents the underlying topology in a certain sense. This auxiliary matrix is additionally used for the construction of the smoothers and the transfer operators. Finally, we present the results of some numerical studies that show the efficiency of the proposed algebraic multigrid preconditioners. Copyright © 2003 John Wiley & Sons, Ltd.     

Algebraic multigrid for finite element elasticity equations: Determination of nodal dependence via edge‐matrices and two‐level convergence

We study an algebraic multigrid (AMG) method for solving elliptic finite element equations of linear elasticity problems. In this method, which has been proposed in (Kraus, SIAM J Sci Comput 2008; 30 : 505–524), the coarsening is based on the so‐called edge‐matrices, which allows to generalize the concept of strong and weak connections, as used in the classical AMG, to ‘algebraic vertices’ that accumulate the nodal degrees of freedom in case of vector‐field problems. The major contribution of this work is related to the investigation of a measure for the nodal dependence and on the generation of the edge‐matrices, which are the basic building blocks of this method. A natural measure is the cosine of the abstract angle between the two subspaces spanned by the basis functions corresponding to the respective algebraic vertices. Another original contribution of this work is a two‐level convergence analysis of the method. The presented numerical results cover also problems with jumps in Young's modulus of elasticity and orthotropic materials. Copyright © 2010 John Wiley & Sons, Ltd.     

An algebraic multigrid approach to solve extended finite element method based fracture problems

This article proposes an algebraic multigrid (AMG) approach to solve linear systems arising from applications where strong discontinuities are modeled by the extended finite element method. The application of AMG methods promises optimal scalability for solving large linear systems. However, the straightforward (or ‘black‐box’) use of existing AMG techniques for extended finite element method problems is often problematic. In this paper, we highlight the reasons for this behavior and propose a relatively simple adaptation that allows one to leverage existing AMG software mostly unchanged. Numerical tests demonstrate that optimal iterative convergence rates can be attained that are comparable with AMG convergence rates associated with linear systems for standard finite element approximations without discontinuities. Published 2012. This article is a US Government work and is in the public domain in the USA.     

A reformulated Arnoldi algorithm for non-classically damped eigenvalue problems

In applying Arnoldi method to non-symmetric eigenvalue problems for damped structures, a structure of the projected upper Hessenberg matrix is obtained in this paper. By exploiting the structure of the upper Hessenberg matrix and taking advantages of the block properties of system matrices, the Arnoldi reduction algorithm is reformulated for less computation and higher accuracy. In conjunction with the reformulated Arnoldi algorithm, real Schur decomposition instead of Jordan decomposition is adopted aiming at non-complex arithmetic, non-discriminative processing of defective and non-defective systems and numeric stability. A concise reduction algorithm for eigenproblems for undamped gyroscopic systems is obtained by directly degenerating from the reformulated Arnoldi algorithm. For safely solving engineering problems without omitting eigenvalues, a restart reduction procedure is proposed in terms of the reformulated reduction algorithm with deflation developed in this paper. Numerical examples once solved with algorithms originated from Lanczos methods were re-solved. In addition, the non-symmetric eigenvalue problem for a shear wall by BEM modeling and a damped gyroscopic system with eigenvalues of high multiplicity were also used to demonstrate the efficacy of the presented methods. © 1997 John Wiley & Sons, Ltd.     

A distributed memory parallel implementation of the multigrid method for solving three‐dimensional implicit solid mechanics problems

We describe the parallel implementation of a multigrid method for unstructured finite element discretizations of solid mechanics problems. We focus on a distributed memory programming model and use the MPI library to perform the required interprocessor communications. We present an algebraic framework for our parallel computations, and describe an object‐based programming methodology using Fortran90. The performance of the implementation is measured by solving both fixed‐ and scaled‐size problems on three different parallel computers (an SGI Origin2000, an IBM SP2 and a Cray T3E). The code performs well in terms of speedup, parallel efficiency and scalability. However, the floating point performance is considerably below the peak values attributed to these machines. Lazy processors are documented on the Origin that produce reduced performance statistics. The solution of two problems on an SGI Origin2000, an IBM PowerPC SMP and a Linux cluster demonstrate that the algorithm performs well when applied to the unstructured meshes required for practical engineering analysis. Copyright © 2004 John Wiley & Sons, Ltd.     

Direct estimation of generalized stress intensity factors using a three‐scale concurrent multigrid X‐FEM

A concurrent multigrid method is devised for the direct estimation of stress intensity factors and higher‐order coefficients of the elastic crack tip asymptotic field. The proposed method bridges three characteristic length scales that can be present in fracture mechanics: the structure, the crack and the singularity at the crack tip. For each of them, a relevant model is proposed. First, a truncated analytical reduced‐order model based on Williams' expansion is used to describe the singularity at the tip. Then, it is coupled with a standard extended finite element (FE) method model which is known to be suitable for the scale of the crack. A multigrid solver finally bridges the scale of the crack to that of the structure for which a standard FE model is often accurate enough. Dedicated coupling algorithms are presented and the effects of their parameters are discussed. The efficiency and accuracy of this new approach are exemplified using three benchmarks. Copyright © 2010 John Wiley & Sons, Ltd.     

A comparison of eigensolvers for large‐scale 3D modal analysis using AMG‐preconditioned iterative methods

The goal of our paper is to compare a number of algorithms for computing a large number of eigenvectors of the generalized symmetric eigenvalue problem arising from a modal analysis of elastic structures. The shift‐invert Lanczos algorithm has emerged as the workhorse for the solution of this generalized eigenvalue problem; however, a sparse direct factorization is required for the resulting set of linear equations. Instead, our paper considers the use of preconditioned iterative methods. We present a brief review of available preconditioned eigensolvers followed by a numerical comparison on three problems using a scalable algebraic multigrid (AMG) preconditioner. Copyright © 2005 John Wiley & Sons, Ltd.     

Truly monolithic algebraic multigrid for fluid–structure interaction

The coupling of flexible structures to incompressible fluids draws a lot of attention during the last decade. Many different solution schemes have been proposed. In this contribution, we concentrate on the strong coupling fluid–structure interaction by means of monolithic solution schemes. Therein, a Newton–Krylov method is applied to the monolithic set of nonlinear equations. Such schemes require good preconditioning to be efficient. We propose two preconditioners that apply algebraic multigrid techniques to the entire fluid–structure interaction system of equations. The first is based on a standard block Gauss–Seidel approach, where approximate inverses of the individual field blocks are based on a algebraic multigrid hierarchy tailored for the type of the underlying physical problem. The second is based on a monolithic coarsening scheme for the coupled system that makes use of prolongation and restriction projections constructed for the individual fields. The resulting nonsymmetric monolithic algebraic multigrid method therefore involves coupling of the fields on coarse approximations to the problem yielding significantly enhanced performance. Copyright © 2010 John Wiley & Sons, Ltd.     

Random matrix eigenvalue problems in structural dynamics

Natural frequencies and mode shapes play a fundamental role in the dynamic characteristics of linear structural systems. Considering that the system parameters are known only probabilistically, we obtain the moments and the probability density functions of the eigenvalues of discrete linear stochastic dynamic systems. Current methods to deal with such problems are dominated by mean‐centred perturbation‐based methods. Here two new approaches are proposed. The first approach is based on a perturbation expansion of the eigenvalues about an optimal point which is ‘best’ in some sense. The second approach is based on an asymptotic approximation of multidimensional integrals. A closed‐form expression is derived for a general rth‐order moment of the eigenvalues. Two approaches are presented to obtain the probability density functions of the eigenvalues. The first is based on the maximum entropy method and the second is based on a chi‐square distribution. Both approaches result in simple closed‐form expressions which can be easily calculated. The proposed methods are applied to two problems and the analytical results are compared with Monte Carlo simulations. It is expected that the ‘small randomness’ assumption usually employed in mean‐centred‐perturbation‐based methods can be relaxed considerably using these methods. Copyright © 2006 John Wiley & Sons, Ltd.     

The Trefftz method for solving eigenvalue problems

For Laplace's eigenvalue problems, this paper presents new algorithms of the Trefftz method (i.e. the boundary approximation method), which solve the Helmholtz equation and then use an iteration process to yield approximate eigenvalues and eigenfunctions. The new iterative method has superlinear convergence rates and gives a better performance in numerical testing, compared with the other popular methods of rootfinding. Moreover, piecewise particular solutions are used for a basic model of eigenvalue problems on the unit square with the Dirichlet condition. Numerical experiments are also conducted for the eigenvalue problems with singularities. Our new algorithms using piecewise particular solutions are well suited to seek very accurate solutions of eigenvalue problems, in particular those with multiple singularities, interfaces and those on unbounded domains. Using piecewise particular solutions has also the advantage to solve complicated problems because uniform particular solutions may not always exist for the entire solution domain.     

A fast and robust iterative solver for nonlinear contact problems using a primal‐dual active set strategy and algebraic multigrid

For extending the usability of implicit FE codes for large‐scale forming simulations, the computation time has to be decreased dramatically. In principle this can be achieved by using iterative solvers. In order to facilitate the use of this kind of solvers, one needs a contact algorithm which does not deteriorate the condition number of the system matrix and therefore does not slow down the convergence of iterative solvers like penalty formulations do. Additionally, an algorithm is desirable which does not blow up the size of the system matrix like methods using standard Lagrange multipliers. The work detailed in this paper shows that a contact algorithm based on a primal‐dual active set strategy provides these advantages and therefore is highly efficient with respect to computation time in combination with fast iterative solvers, especially algebraic multigrid methods. Copyright © 2006 John Wiley & Sons, Ltd.     

Parallel multipole implementation of the generalized Helmholtz decomposition for solving viscous flow problems

The evaluation of a domain integral is the dominant bottleneck in the numerical solution of viscous flow problems by vorticity methods, which otherwise demonstrate distinct advantages over primitive variable methods. By applying a Barnes–Hut multipole acceleration technique, the operation count for the integration is reduced from O(N²) to O(NlogN), while the memory requirements are reduced from O(N²) to O(N). The algorithmic parameters that are necessary to achieve such scaling are described. The parallelization of the algorithm is crucial if the method is to be applied to realistic problems. A parallelization procedure which achieves almost perfect scaling is shown. Finally, numerical experiments on a driven cavity benchmark problem are performed. The actual increase in performance and reduction in storage requirements match theoretical predictions well, and the scalability of the procedure is very good. Copyright © 2003 John Wiley Sons, Ltd.     

Parallel multigrid solvers for 3D unstructured finite element problems in large deformation elasticity and plasticity

Multigrid is a popular solution method for the set of linear algebraic equations that arise from PDEs discretized with the finite element method. The application of multigrid to unstructured grid problems, however, is not well developed. We discuss a method, that uses many of the same techniques as the finite element method itself, to apply standard multigrid algorithms to unstructured finite element problems. We use maximal independent sets (MISs) as a mechanism to automatically coarsen unstructured grids; the inherent flexibility in the selection of an MIS allows for the use of heuristics to improve their effectiveness for a multigrid solver. We present parallel algorithms, based on geometric heuristics, to optimize the quality of MISs and the meshes constructed from them, for use in multigrid solvers for 3D unstructured problems. We discuss parallel issues of our algorithms, multigrid solvers in general, and the parallel finite element application that we have developed to test our solver on challenging problems. We show that our solver, and parallel finite element architecture, does indeed scale well, with test problems in 3D large deformation elasticity and plasticity, with 40 million degree of freedom problem on 240 IBM four‐way SMP PowerPC nodes. Copyright © 2000 John Wiley & Sons, Ltd.     

Coupling techniques in boundary-combined methods for solving elliptic problems with singularities

Three coupling strategies in matching the Ritz-Galerkin method and the finite element method are introduced for general elliptic equations, and useful numerical techniques are provided. Numerical experiments have been carried out for solving the typical, singular Motz problem, which shows that optimal convergence rates of numerical solutions can be achieved by using the combined methods and techniques provided in this paper.     

Efficient method for lasing eigenvalue problems of periodic structures

Lasing eigenvalue problems (LEPs) are non-conventional eigenvalue problems involving the frequency and gain threshold at the onset of lasing directly. Efficient numerical methods are needed to solve LEPs for the analysis, design and optimization of microcavity lasers. Existing computational methods for two-dimensional LEPs include the multipole method and the boundary integral equation method. In particular, the multipole method has been applied to LEPs of periodic structures, but it requires sophisticated mathematical techniques for evaluating slowly converging infinite sums that appear due to the periodicity. In this paper, a new method is developed for periodic LEPs based on the so-called Dirichlet-to-Neumann maps. The method is efficient since it avoids the slowly converging sums and can easily handle periodic structures with many arrays.