A parallel additive Schwarz preconditioned Jacobi–Davidson algorithm for polynomial eigenvalue problems in quantum dot simulation

We develop a parallel Jacobi–Davidson approach for finding a partial set of eigenpairs of large sparse polynomial eigenvalue problems with application in quantum dot simulation. A Jacobi–Davidson eigenvalue solver is implemented based on the Portable, Extensible Toolkit for Scientific Computation (PETSc). The eigensolver thus inherits PETSc’s efficient and various parallel operations, linear solvers, preconditioning schemes, and easy usages. The parallel eigenvalue solver is then used to solve higher degree polynomial eigenvalue problems arising in numerical simulations of three dimensional quantum dots governed by Schrödinger’s equations. We find that the parallel restricted additive Schwarz preconditioner in conjunction with a parallel Krylov subspace method (e.g. GMRES) can solve the correction equations, the most costly step in the Jacobi–Davidson algorithm, very efficiently in parallel. Besides, the overall performance is quite satisfactory. We have observed near perfect superlinear speedup by using up to 320 processors. The parallel eigensolver can find all target interior eigenpairs of a quintic polynomial eigenvalue problem with more than 32 million variables within 12 minutes by using 272 Intel 3.0 GHz processors.     

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.     

A Schur complement formulation for solving free-boundary,Stefan problems of phase change

A Schur complement formulation that utilizes a linear iterative solver is derived to solve a free-boundary, Stefan problem describing steady-state phase change via the Isotherm–Newton approach, which employs Newton’s method to simultaneously and efficiently solve for both interface and field equations. This formulation is tested alongside more traditional solution strategies that employ direct or iterative linear solvers on the entire Jacobian matrix for a two-dimensional sample problem that discretizes the field equations using a Galerkin finite-element method and employs a deforming-grid approach to represent the melt–solid interface. All methods demonstrate quadratic convergence for sufficiently accurate Newton solves, but the two approaches utilizing linear iterative solvers show better scaling of computational effort with problem size. Of these two approaches, the Schur formulation proves to be more robust, converging with significantly smaller Krylov subspaces than those required to solve the global system of equations. Further improvement of performance are made through approximations and preconditioning of the Schur complement problem. Hence, the new Schur formulation shows promise as an affordable, robust, and scalable method to solve free-boundary, Stefan problems. Such models are employed to study a wide array of applications, including casting, welding, glass forming, planetary mantle and glacier dynamics, thermal energy storage, food processing, cryosurgery, metallurgical solidification, and crystal growth.     

Preconditioning based on Calderon’s formulae for periodic fast multipole methods for Helmholtz’ equation

Solution of periodic boundary value problems is of interest in various branches of science and engineering such as optics, electromagnetics and mechanics. In our previous studies we have developed a periodic fast multipole method (FMM) as a fast solver of wave problems in periodic domains. It has been found, however, that the convergence of the iterative solvers for linear equations slows down when the solutions show anomalies related to the periodicity of the problems. In this paper, we propose preconditioning schemes based on Calderon’s formulae to accelerate convergence of iterative solvers in the periodic FMM for Helmholtz’ equations. The proposed preconditioners can be implemented more easily than conventional ones. We present several numerical examples to test the performance of the proposed preconditioners. We show that the effectiveness of these preconditioners is definite even near anomalies.     

3D FEM–BEM-coupling method to solve magnetostatic Maxwell equations

3D magnetostatic Maxwell equations are solved using the direct Johnson–Nédélec FEM–BEM coupling method and a reduced scalar potential approach. The occurring BEM matrices are calculated analytically and approximated by H-matrices using the ACA+ algorithm. In addition a proper preconditioning method is suggested that allows to solve large-scale problems using iterative solvers.     

Development of a Stokes flow solver robust to large viscosity jumps using a Schur complement approach with mixed precision arithmetic

We develop an iterative solution technique for solving Stokes flow problems with smooth and discontinuous viscosity structures using a three dimensional, staggered grid finite difference discretization. Two preconditioned iterative methodologies are applied to the saddle point arising from the discrete Stokes problem. They consist of a velocity–pressure coupled approach (FC) and a decoupled, Schur complement approach (SC). Within both of these methods, we utilize either the scaled BFBt, or an identity matrix scaled by the local cell viscosity (LV) to define a preconditioner for the Schur complement. Additionally, we propose to use a mixed precision Krylov kernel to improve the convergence by reducing round-off error. In this approach, standard double precision is used during the application of the preconditioner, whilst higher precision arithmetic is used to define the matrix vector product, dot products and norms required by the Krylov method. In our Krylov kernel, we utilize quad precision arithmetic which is emulated via the double–double precision method. We consider several simplified geodynamic problems with a viscosity contrast to demonstrate the robustness and scalability of our solution methods. Through a careful choice of stopping conditions, we are able to quantitatively compare the residuals between the SC and FC approaches. We examine the trade-off relationship between the number of outer iterations required for convergence, and the computational cost per iteration, for the each solution methods. We find that it is advantageous to use the FC approach utilizing relaxed tolerances for solution of the sub-problems, combined with the LV preconditioner. We also observed that in general, the SC approach is more robust than FC and that BFBt is more robust than LV when used in our numerical experimental. In addition, our mixed precision method produces improved convergence rates of Arnoldi type Krylov subspace methods without a drastic increasing the computational time. The usage of a high precision Krylov kernel is found to be useful for the solver associated with the velocity sub-problem.     

预处理JFNK方法求解非平衡辐射扩散方程组

分别采用四种半隐式离散方法构造预处理.针对一维辐射扩散方程组,采用预处理的Jacobian-free Newton-Krylov(PJFNK)求解.数值结果表明预处理方法能够很好地改进JFNK方法的收敛行为.     

A taxonomy and comparison of parallel block multi-level preconditioners for the incompressible Navier–Stokes equations

In recent years, considerable effort has been placed on developing efficient and robust solution algorithms for the incompressible Navier–Stokes equations based on preconditioned Krylov methods. These include physics-based methods, such as SIMPLE, and purely algebraic preconditioners based on the approximation of the Schur complement. All these techniques can be represented as approximate block factorization (ABF) type preconditioners. The goal is to decompose the application of the preconditioner into simplified sub-systems in which scalable multi-level type solvers can be applied. In this paper we develop a taxonomy of these ideas based on an adaptation of a generalized approximate factorization of the Navier–Stokes system first presented in [A. Quarteroni, F. Saleri, A. Veneziani, Factorization methods for the numerical approximation of Navier–Stokes equations, Computational Methods in Applied Mechanical Engineering 188 (2000) 505–526]. This taxonomy illuminates the similarities and differences among these preconditioners and the central role played by efficient approximation of certain Schur complement operators. We then present a parallel computational study that examines the performance of these methods and compares them to an additive Schwarz domain decomposition (DD) algorithm. Results are presented for two and three-dimensional steady state problems for enclosed domains and inflow/outflow systems on both structured and unstructured meshes. The numerical experiments are performed using MPSalsa, a stabilized finite element code.     

A spectral FC solver for the compressible Navier–Stokes equations in general domains I: Explicit time-stepping

We present a Fourier continuation (FC) algorithm for the solution of the fully nonlinear compressible Navier–Stokes equations in general spatial domains. The new scheme is based on the recently introduced accelerated FC method, which enables use of highly accurate Fourier expansions as the main building block of general-domain PDE solvers. Previous FC-based PDE solvers are restricted to linear scalar equations with constant coefficients. The FC methodology presented in this text thus constitutes a significant generalization of the previous FC schemes, as it yields general-domain FC solvers for nonlinear systems of PDEs. While not restricted to periodic boundary conditions and therefore applicable to general boundary value problems on arbitrary domains, the proposed algorithm inherits many of the highly desirable properties arising from rapidly convergent Fourier expansions, including high-order convergence, essentially spectrally accurate dispersion relations, and much milder CFL constraints than those imposed by polynomial-based spectral methods—since, for example, the spectral radius of the FC first derivative grows linearly with the number of spatial discretization points. We demonstrate the accuracy and optimal parallel efficiency of the algorithm in a variety of scientific and engineering contexts relevant to fluid-dynamics and nonlinear acoustics.     

A Fast High Order Iterative Solver for the Electromagnetic Scattering by Open Cavities Filled with the Inhomogeneous Media

The scattering of the open cavity filled with the inhomogeneous media is studied. The problem is discretized with a fourth order finite difference scheme and the immersed interface method, resulting in a linear system of equations with the high order accurate solutions in the whole computational domain. To solve the system of equations, we design an efficient iterative solver, which is based on the fast Fourier transformation, and provides an ideal preconditioner for Krylov subspace method. Numerical experiments demonstrate the capability of the proposed fast high order iterative solver.     

A low-dissipation and time-accurate method for compressible multi-component flow with variable specific heat ratios

A low-dissipation method for calculating multi-component gas dynamics flows with variable specific heat ratio that is capable of accurately simulating flows which contain both high- and low-Mach number features is proposed. The technique combines features from the double-flux multi-component model, nonlinear error-controlled WENO, adaptive TVD slope limiters, rotated Riemann solvers, and adaptive mesh refinement to obtain a method that is both robust and accurate. Success of the technique is demonstrated using an extensive series of numerical experiments including premixed deflagrations, Chapman–Jouget detonations, re-shocked Richtmyer–Meshkov instability, shock-wave and hydrogen gas column interaction, and multi-dimensional detonations. This technique is relatively straight-forward to implement using an existing compressible Navier–Stokes solver based on Godunov’s method.     

Implementation of the Jacobian-free Newton–Krylov method for solving the first-order ice sheet momentum balance

We have implemented the Jacobian-free Newton–Krylov (JFNK) method for solving the first-order ice sheet momentum equation in order to improve the numerical performance of the Glimmer-Community Ice Sheet Model (Glimmer-CISM), the land ice component of the Community Earth System Model (CESM). Our JFNK implementation is based on significant re-use of existing code. For example, our physics-based preconditioner uses the original Picard linear solver in Glimmer-CISM. For several test cases spanning a range of geometries and boundary conditions, our JFNK implementation is 1.8–3.6 times more efficient than the standard Picard solver in Glimmer-CISM. Importantly, this computational gain of JFNK over the Picard solver increases when refining the grid. Global convergence of the JFNK solver has been significantly improved by rescaling the equation for the basal boundary condition and through the use of an inexact Newton method. While a diverse set of test cases show that our JFNK implementation is usually robust, for some problems it may fail to converge with increasing resolution (as does the Picard solver). Globalization through parameter continuation did not remedy this problem and future work to improve robustness will explore a combination of Picard and JFNK and the use of homotopy methods.     

Multigrid algorithms for high-order discontinuous Galerkin discretizations of the compressible Navier–Stokes equations

Multigrid algorithms are developed for systems arising from high-order discontinuous Galerkin discretizations of the compressible Navier–Stokes equations on unstructured meshes. The algorithms are based on coupling both p- and h-multigrid (ph-multigrid) methods which are used in nonlinear or linear forms, and either directly as solvers or as preconditioners to a Newton–Krylov method.The performance of the algorithms are examined in solving the laminar flow over an airfoil configuration. It is shown that the choice of the cycling strategy is crucial in achieving efficient and scalable solvers. For the multigrid solvers, while the order-independent convergence rate is obtained with a proper cycle type, the mesh-independent performance is achieved only if the coarsest problem is solved to a sufficient accuracy. On the other hand, the multigrid preconditioned Newton–GMRES solver appears to be insensitive to this condition and mesh-independent convergence is achieved under the desirable condition that the coarsest problem is solved using a fixed number of multigrid cycles regardless of the size of the problem.It is concluded that the Newton–GMRES solver with the multigrid preconditioning yields the most efficient and robust algorithm among those studied.     

Fast iterative solvers for buoyancy driven flow problems

We outline a new class of robust and efficient methods for solving the Navier–Stokes equations with a Boussinesq model for buoyancy driven flow. We describe a general solution strategy that has two basic building blocks: an implicit time integrator using a stabilized trapezoid rule with an explicit Adams–Bashforth method for error control, and a robust Krylov subspace solver for the spatially discretized system. We present numerical experiments illustrating the efficiency of the chosen preconditioning schemes with respect to the discretization parameters.     

An Iterative Two-Grid Method of a Finite Element PML Approximation for the Two Dimensional Maxwell Problem

In this paper, we propose an iterative two-grid method for the edge finite element discretizations (a saddle-point system) of Perfectly Matched Layer (PML) equations to the Maxwell scattering problem in two dimensions. Firstly, we use a fine space to solve a discrete saddle-point system of $H(grad)$ variational problems, denoted by auxiliary system 1. Secondly, we use a coarse space to solve the original saddle-point system. Then, we use a fine space again to solve a discrete$\boldsymbol{H}(curl)$-elliptic variational problems, denoted by auxiliary system 2. Furthermore, we develop a regularization diagonal block preconditioner for auxiliary system 1 and use $H$-$X$ preconditioner for auxiliary system 2. Hence we essentially transform the original problem in a fine space to a corresponding (but much smaller) problem on a coarse space, due to the fact that the above two preconditioners are efficient and stable. Compared with some existing iterative methods for solving saddle-point systems, such as PMinres, numerical experiments show the competitive performance of our iterative two-grid method.     

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.     

A particle–particle hybrid method for kinetic and continuum equations

We present a coupling procedure for two different types of particle methods for the Boltzmann and the Navier–Stokes equations. A variant of the DSMC method is applied to simulate the Boltzmann equation, whereas a meshfree Lagrangian particle method, similar to the SPH method, is used for simulations of the Navier–Stokes equations. An automatic domain decomposition approach is used with the help of a continuum breakdown criterion. We apply adaptive spatial and time meshes. The classical Sod’s 1D shock tube problem is solved for a large range of Knudsen numbers. Results from Boltzmann, Navier–Stokes and hybrid solvers are compared. The CPU time for the hybrid solver is 3–4 times faster than for the Boltzmann solver.     

地球外核热对流运动的区域分解多重网格并行数值模拟

旋转球层中热对流运动的数值模拟是地球发电机模型的重要组成部分,对研究地球发电机作用机理具有重要意义.本文设计一个基于国产超级计算平台并行性能良好的地球外核热对流运动并行数值模型.时间积分方案采用与Crank-Nicolson格式和二阶Adams-Bashford公式相结合的近似分解分步法,空间离散基于立方球网格的二阶精度有限体积格式.所得到的两个大规模稀疏线性代数方程组采用带预处理的Krylov子空间迭代法进行求解.为加速迭代求解过程及提高并行性能,迭代过程采用区域分解多重网格的多层限制型加法Schwarz预处理子,减少了求解程序的计算时间,提高了数值模型的并行性能,模型被很好地扩展到上万处理器核数.数值模拟结果与基准模型算例0的参考值吻合得很好.     

Iterative diagonalization in augmented plane wave based methods in electronic structure calculations

Due to the increased computer power and advanced algorithms, quantum mechanical calculations based on Density Functional Theory are more and more widely used to solve real materials science problems. In this context large nonlinear generalized eigenvalue problems must be solved repeatedly to calculate the electronic ground state of a solid or molecule. Due to the nonlinear nature of this problem, an iterative solution of the eigenvalue problem can be more efficient provided it does not disturb the convergence of the self-consistent-field problem. The blocked Davidson method is one of the widely used and efficient schemes for that purpose, but its performance depends critically on the preconditioning, i.e. the procedure to improve the search space for an accurate solution. For more diagonally dominated problems, which appear typically for plane wave based pseudopotential calculations, the inverse of the diagonal of (H ? ES) is used. However, for the more efficient “augmented plane wave + local-orbitals” basis set this preconditioning is not sufficient due to large off-diagonal terms caused by the local orbitals. We propose a new preconditioner based on the inverse of (H ? λS) and demonstrate its efficiency for real applications using both, a sequential and a parallel implementation of this algorithm into our WIEN2k code.     

A Solver for Helmholtz System Generated by the Discretization of Wave Shape Functions

An interesting discretization method for Helmholtz equations was introduced in B. Després [1]. This method is based on the ultra weak variational formulation (UWVF) and the wave shape functions, which are exact solutions of the governing Helmholtz equation. In this paper we are concerned with fast solver for the system generated by the method in [1]. We propose a new preconditioner for such system, which can be viewed as a combination between a coarse solver and the block diagonal preconditioner introduced in [13]. In our numerical experiments, this preconditioner is applied to solve both two-dimensional and three-dimensional Helmholtz equations, and the numerical results illustrate that the new preconditioner is much more efficient than the original block diagonal preconditioner.