Application of Robust Incomplete Cholesky Factorizations Preconditioned CG Algorithms for FEM Analysis of Millimeter Wave Filters

The Incomplete Cholesky factorizations preconditioning scheme is applied to the conjugate gradient (CG) method for solving a large system of linear equations resulting from finite element method (FEM) analysis of millimeter wave filters. As is well known, the convergence of CG method deteriorates with increasing EM wave number and in millimeter wave band the eigen-values of A are more and more scattered between both the right and the left half-plane. The efficient implementation of this preconditioned CG (PCG) algorithm is described in details for Complex coefficient matrix. With incomplete factorization preconditioning scheme in the conjugate gradient algorithm, this PCG approach can reach convergence in 20 times CPU time shorter than CG for several typical millimeter wave structures.     

A fast parallel Poisson solver on irregular domains applied to beam dynamics simulations

We discuss the scalable parallel solution of the Poisson equation within a Particle-In-Cell (PIC) code for the simulation of electron beams in particle accelerators of irregular shape. The problem is discretized by Finite Differences. Depending on the treatment of the Dirichlet boundary the resulting system of equations is symmetric or ‘mildly’ nonsymmetric positive definite. In all cases, the system is solved by the preconditioned conjugate gradient algorithm with smoothed aggregation (SA) based algebraic multigrid (AMG) preconditioning. We investigate variants of the implementation of SA-AMG that lead to considerable improvements in the execution times. We demonstrate good scalability of the solver on distributed memory parallel processor with up to 2048 processors. We also compare our iterative solver with an FFT-based solver that is more commonly used for applications in beam dynamics.     

Research of the Algebraic Multigrid Method for Electron Optical Simulator

At present, electron optical simulator (EOS) takes a long time to solve linear FEM systems. The algebraic multigrid preconditioned conjugate gradient (AMGPCG) method can improve the efficiency of solving systems. This paper is focused on the implementation of the AMGPCG method in EOS. The aggregation-based scheme, which uses two passes of a pairwise matching algorithm and the K-cyle scheme, is adopted in the aggregation-based algebraic multigrid method. Numerical experiments show the advantages and disadvantages of the AMG algorithm in peak memory and solving efficiency. The AMGPCG is more efficient than the iterative methods used in the past and only needs one coarsening when EOS computes the particle motion trajectory.     

Two-Level Hierarchical FEM Method for Modeling Passive Microwave Devices

In recent years multigrid methods have been proven to be very efficient for solving large systems of linear equations resulting from the discretization of positive definite differential equations by either the finite difference method or theh-version of the finite element method. In this paper an iterative method of the multiple level type is proposed for solving systems of algebraic equations which arise from thep-version of the finite element analysis applied to indefinite problems. A two-levelV-cycle algorithm has been implemented and studied with a Gauss–Seidel iterative scheme used as a smoother. The convergence of the method has been investigated, and numerical results for a number of numerical examples are presented.     

并行代数多重网格算法可扩展性能分析

对当今求解大型稀疏线性代数方程组最有效的迭代方法之--代数多重网格(AMG)算法的并行计算进行可扩展性能分析.给出一套并行计算可扩展性能分析方法,用于分析和指导并行迭代算法及实现技术的设计与优化并应用于并行AMG算法.分析表明,网格算子的平均模式大小和迭代过程的算法效率分别制约了AMG算法启动阶段和迭代求解阶段并行性能的发挥,成为该类算法急需解决的两个关键问题.     

An h-adaptive finite element solver for the calculations of the electronic structures

In this paper, a framework of using h-adaptive finite element method for the Kohn–Sham equation on the tetrahedron mesh is presented. The Kohn–Sham equation is discretized by the finite element method, and the h-adaptive technique is adopted to optimize the accuracy and the efficiency of the algorithm. The locally optimal block preconditioned conjugate gradient method is employed for solving the generalized eigenvalue problem, and an algebraic multigrid preconditioner is used to accelerate the solver. A variety of numerical experiments demonstrate the effectiveness of our algorithm for both the all-electron and the pseudo-potential calculations.     

Explicit and implicit FEM-FCT algorithms with flux linearization

A new approach to the design of flux-corrected transport (FCT) algorithms for continuous (linear/multilinear) finite element approximations of convection-dominated transport problems is pursued. The algebraic flux correction paradigm is revisited, and a family of nonlinear high-resolution schemes based on Zalesak’s fully multidimensional flux limiter is considered. In order to reduce the cost of flux correction, the raw antidiffusive fluxes are linearized about an auxiliary solution computed by a high- or low-order scheme. By virtue of this linearization, the costly computation of solution-dependent correction factors is to be performed just once per time step, and there is no need for iterative defect correction if the governing equation is linear. A predictor–corrector algorithm is proposed as an alternative to the hybridization of high- and low-order fluxes. Three FEM-FCT schemes based on the Runge–Kutta, Crank–Nicolson, and backward Euler time-stepping are introduced. A detailed comparative study is performed for linear convection–diffusion equations.     

基于Tahoe框架的某夹具并行计算

在开源软件Tahoe框架基础上,结合有限元前后处理程序MSC.Patran及Tecplot,对某复杂夹具进行建模.通过区域分解、编制接口和采用PHG中提供的PCG(preconditioned conjugate gradient,预处理共轭梯度法)迭代解法成功实现262×10⁴自由度模型的串、并行计算.结果表明,并行计算收敛速度更快,4进程并行计算时间不到串行计算时间的1/4.通过与商用程序MSC.Nastran比较,验证计算结果的正确性.利用大型并行计算机对该模型并行计算性能进行研究,获得最高32进程的并行计算加速比.研究表明,改进后的Tahoe计算框架对于开展大规模自由度下的结构并行计算分析研究是可行的,并且随计算节点增加,并行计算过程基本呈线性加速.     

一种可扩展的三维半导体器件并行数值模拟算法

在基于漂移-扩散模型的三维半导体器件数值模拟中,通过有限体积法进行数值离散,采用完全耦合的牛顿迭代求解非线性代数方程组,并使用基于代数多重网格预条件子的GMRES方法求解牛顿迭代中的线性方程组,构造一种稳健且高度可扩展的非结构四面体网格上求解半导体方程的并行算法.基于PHG平台实现该算法的并行计算程序,并对PN结和MOS场效应晶体管等问题进行了最大网格规模达到5亿单元、最大并行规模达到1 024进程的大规模数值模拟实验,结果表明,该算法计算效率高,可扩展性好.     

Accelerated Block Preconditioned Gradient method for large scale wave functions calculations in Density Functional Theory

An Accelerated Block Preconditioned Gradient (ABPG) method is proposed to solve electronic structure problems in Density Functional Theory. This iterative algorithm is designed to solve directly the non-linear Kohn–Sham equations for accurate discretization schemes involving a large number of degrees of freedom. It makes use of an acceleration scheme similar to what is known as RMM-DIIS in the electronic structure community. The method is illustrated with examples of convergence for large scale applications using a finite difference discretization and multigrid preconditioning.     

An accurate and efficient method for the incompressible Navier–Stokes equations using the projection method as a preconditioner

The projection method is a widely used fractional-step algorithm for solving the incompressible Navier–Stokes equations. Despite numerous improvements to the methodology, however, imposing physical boundary conditions with projection-based fluid solvers remains difficult, and obtaining high-order accuracy may not be possible for some choices of boundary conditions. In this work, we present an unsplit, linearly-implicit discretization of the incompressible Navier–Stokes equations on a staggered grid along with an efficient solution method for the resulting system of linear equations. Since our scheme is not a fractional-step algorithm, it is straightforward to specify general physical boundary conditions accurately; however, this capability comes at the price of having to solve the time-dependent incompressible Stokes equations at each timestep. To solve this linear system efficiently, we employ a Krylov subspace method preconditioned by the projection method. In our implementation, the subdomain solvers required by the projection preconditioner employ the conjugate gradient method with geometric multigrid preconditioning. The accuracy of the scheme is demonstrated for several problems, including forced and unforced analytic test cases and lid-driven cavity flows. These tests consider a variety of physical boundary conditions with Reynolds numbers ranging from 1 to 30000. The effectiveness of the projection preconditioner is compared to an alternative preconditioning strategy based on an approximation to the Schur complement for the time-dependent incompressible Stokes operator. The projection method is found to be a more efficient preconditioner in most cases considered in the present work.     

不可压N-S方程的基于粘接元的区域分裂解法

首先,简单介绍了基于粘接元的无重叠区域分裂方法.这种方法利用变分原理,非常适合有限元近似.然后,着重讨论了这种区域分裂方法在求解不可压Navier-Stokes方程中的应用,具体包括等价变分公式的建立、通过算子分裂的时间离散、区域分裂情形下广义Stokes问题的共轭梯度迭代求解方法、空间的有限元离散.最后,以数值实验结果验证了这种区域分裂方法应用于不可压Navier-Stokes方程求解时的可靠性.     

一类三维等代数结构面剖分下的代数多重网格算法

对一类等代数结构面的三维非结构网格剖分,针对光滑变系数和各向异性系数的偏微分方程,给出两种非结构代数多重网格算法,数值试验表明算法的有效性和健壮性.     

Efficient algebraic multigrid for migration–diffusion–convection–reaction systems arising in electrochemical simulations

The article discusses components and performance of an algebraic multigrid (AMG) preconditioner for the fully coupled multi-ion transport and reaction model (MITReM) with nonlinear boundary conditions, important for electrochemical modeling. The governing partial differential equations (PDEs) are discretized in space by a combined finite element and residual distribution method. Solution of the discrete system is obtained by means of a Newton-based nonlinear solver, and an AMG-preconditioned BICGSTAB Krylov linear solver. The presented AMG preconditioner is based on so-called point-based classical AMG. The linear solver is compared to a standard direct and several one-level iterative solvers for a range of geometries and chemical systems with scientific and industrial relevance. The results indicate that point-based AMG methods, carefully designed, are an attractive alternative to more commonly employed numerical methods for the simulation of complex electrochemical processes.     

Preconditioning methods for discontinuous Galerkin solutions of the Navier–Stokes equations

A Newton–Krylov method is developed for the solution of the steady compressible Navier–Stokes equations using a discontinuous Galerkin (DG) discretization on unstructured meshes. Steady-state solutions are obtained using a Newton–Krylov approach where the linear system at each iteration is solved using a restarted GMRES algorithm. Several different preconditioners are examined to achieve fast convergence of the GMRES algorithm. An element Line-Jacobi preconditioner is presented which solves a block-tridiagonal system along lines of maximum coupling in the flow. An incomplete block-LU factorization (Block-ILU(0)) is also presented as a preconditioner, where the factorization is performed using a reordering of elements based upon the lines of maximum coupling. This reordering is shown to be superior to standard reordering techniques (Nested Dissection, One-way Dissection, Quotient Minimum Degree, Reverse Cuthill–Mckee) especially for viscous test cases. The Block-ILU(0) factorization is performed in-place and an algorithm is presented for the application of the linearization which reduces both the memory and CPU time over the traditional dual matrix storage format. Additionally, a linear p-multigrid preconditioner is also considered, where Block-Jacobi, Line-Jacobi and Block-ILU(0) are used as smoothers. The linear multigrid preconditioner is shown to significantly improve convergence in term of number of iterations and CPU time compared to a single-level Block-Jacobi or Line-Jacobi preconditioner. Similarly the linear multigrid preconditioner with Block-ILU smoothing is shown to reduce the number of linear iterations to achieve convergence over a single-level Block-ILU(0) preconditioner, though no appreciable improvement in CPU time is shown.     

An Effective Multigrid Preconditioned CG Algorithm for Millimeter Wave Scattering by an Infinite Plane Metallic Grating

An effective multigrid based preconditioned conjugate gradient method is developed to solve electromagnetic large matrix problem for millimeter wave scattering application. By using multigrid technique we restrict the large matrix equation to a relative smaller matrix and which can be solved rapidly. The solution is prolonged as the initial guess for the conjugate gradient (CG) method. Numerical results show that our developed method can reach five times improvement of computational complexity.     

Towards a scalable fully-implicit fully-coupled resistive MHD formulation with stabilized FE methods

This paper explores the development of a scalable, nonlinear, fully-implicit stabilized unstructured finite element (FE) capability for 2D incompressible (reduced) resistive MHD. The discussion considers the implementation of a stabilized FE formulation in context of a fully-implicit time integration and direct-to-steady-state solution capability. The nonlinear solver strategy employs Newton–Krylov methods, which are preconditioned using fully-coupled algebraic multilevel preconditioners. These preconditioners are shown to enable a robust, scalable and efficient solution approach for the large-scale sparse linear systems generated by the Newton linearization. Verification results demonstrate the expected order-of-accuracy for the stabilized FE discretization. The approach is tested on a variety of prototype problems, including both low-Lundquist number (e.g., an MHD Faraday conduction pump and a hydromagnetic Rayleigh–Bernard linear stability calculation) and moderately-high Lundquist number (magnetic island coalescence problem) examples. Initial results that explore the scaling of the solution methods are presented on up to 4096 processors for problems with up to 64M unknowns on a CrayXT3/4. Additionally, a large-scale proof-of-capability calculation for 1 billion unknowns for the MHD Faraday pump problem on 24,000 cores is presented.     

High-performance modeling acoustic and elastic waves using the parallel Dichotomy Algorithm

A high-performance parallel algorithm is proposed for modeling the propagation of acoustic and elastic waves in inhomogeneous media. An initial boundary-value problem is replaced by a series of boundary-value problems for a constant elliptic operator and different right-hand sides via the integral Laguerre transform. It is proposed to solve difference equations by the conjugate gradient method for acoustic equations and by the GMRES(k) method for modeling elastic waves. A preconditioning operator was the Laplace operator that is inverted using the variable separation method. The novelty of the proposed algorithm is using the Dichotomy Algorithm [26], which was designed for solving a series of tridiagonal systems of linear equations, in the context of the preconditioning operator inversion. Via considering analytical solutions, it is shown that modeling wave processes for long instants of time requires high-resolution meshes. The proposed parallel fine-mesh algorithm enabled to solve real application seismic problems in acceptable time and with high accuracy. By solving model problems, it is demonstrated that the considered parallel algorithm possesses high performance and efficiency over a wide range of the number of processors (from 2 to 8192).     

Performance of a parallel algebraic multilevel preconditioner for stabilized finite element semiconductor device modeling

In this study results are presented for the large-scale parallel performance of an algebraic multilevel preconditioner for solution of the drift-diffusion model for semiconductor devices. The preconditioner is the key numerical procedure determining the robustness, efficiency and scalability of the fully-coupled Newton–Krylov based, nonlinear solution method that is employed for this system of equations. The coupled system is comprised of a source term dominated Poisson equation for the electric potential, and two convection–diffusion-reaction type equations for the electron and hole concentration. The governing PDEs are discretized in space by a stabilized finite element method. Solution of the discrete system is obtained through a fully-implicit time integrator, a fully-coupled Newton-based nonlinear solver, and a restarted GMRES Krylov linear system solver. The algebraic multilevel preconditioner is based on an aggressive coarsening graph partitioning of the nonzero block structure of the Jacobian matrix. Representative performance results are presented for various choices of multigrid V-cycles and W-cycles and parameter variations for smoothers based on incomplete factorizations. Parallel scalability results are presented for solution of up to 10⁸${10}^8$ unknowns on 4096 processors of a Cray XT3/4 and an IBM POWER eServer system.     

Analysis of Millimeter Wave Scattering by an Electrically Large Metallic Grating Using Wavelet-Based Algebraic Multigrid Preconditioned CG Method

An effective wavelet based multigrid preconditioned conjugate gradient method is developed to solve electromagnetic large matrix problem for millimeter wave scattering application. By using wavelet transformation we restrict the large matrix equation to a relative smaller matrix and which can be solved rapidly. The solution is prolonged as the new improvement for the conjugate gradient (CG) method. Numerical results show that our developed wavelet based multigrid preconditioned CG method can reach large improvement of computational complexity. Due to the automaticity of wavelet transformation, this method is potential to be a block box solver without physical background.