Domain Decomposition Algorithms for Two Dimensional Linear Schrödinger Equation

This paper deals with two domain decomposition methods for two dimensional linear Schrödinger equation, the Schwarz waveform relaxation method and the domain decomposition in space method. After presenting the classical algorithms, we propose a new algorithm for the Schrödinger equation with constant potential and a preconditioned algorithm for the general Schrödinger equation. These algorithms are then studied numerically. The numerical experiments show that the new algorithms can improve the convergence rate and reduce the computation time. Besides of the traditional Robin transmission condition, we also propose to use a newly constructed absorbing condition as the transmission condition.     

A finite element overlapping scheme for turbomachinery flows on parallel platforms

Two- and three-dimensional turbomachinery flows in stationary and rotating compressor cascades are studied by using a one-level inexact explicit Schwarz method, and a cubic eddy viscosity turbulence closure. The message passing paradigm is used for the parallel implementation of the domain decomposition algorithm, allowing the solver portability on different parallel platforms. A convergence accelerator is proposed, based on a condensed cycle structure that merges the additive Schwarz iterations with the fixed point non-linear ones. The use of a stable finite element formulation on higher-order elements Q2-Q1 is addressed as a mean for retaining non-oscillatory and accurate solutions. Furthermore, the elementwise quadratic approximation is used to enable the exact implementation of higher-order integrals arising in the anisotropic turbulence closure adopted. Numerical campaigns are carried out on IBM SP2 and SP3, and CRAY T3E architectures, in order to demonstrate the portability. The accompanying performance improvement is assessed. Finally, the predicting capabilities are discussed with reference to challenging turbomachinery test cases: a transitional linear compressor cascade, and an isolated compressor rotor designed for non-free vortex operation. Convergence speed-up in such configurations is discussed.     

Development of a parallel implicit solver of fluid modeling equations for gas discharges

A parallel fully implicit PETSc-based fluid modeling equations solver for simulating gas discharges is developed. Fluid modeling equations include: the neutral species continuity equation, the charged species continuity equation with drift-diffusion approximation for mass fluxes, the electron energy density equation, and Poisson's equation for electrostatic potential. Except for Poisson's equation, all model equations are discretized by the fully implicit backward Euler method as a time integrator, and finite differences with the Scharfetter–Gummel scheme for mass fluxes on the spatial domain. At each time step, the resulting large sparse algebraic nonlinear system is solved by the Newton–Krylov–Schwarz algorithm. A 2D-GEC RF discharge is used as a benchmark to validate our solver by comparing the numerical results with both the published experimental data and the theoretical prediction. The parallel performance of the solver is investigated.     

Two-Level Space–Time Domain Decomposition Methods for Flow Control Problems

For time-dependent control problems, the class of sub-optimal algorithms is popular and the parallelization is usually applied in the spatial dimension only. In the paper, we develop a class of fully-optimal methods based on space–time domain decomposition methods for some boundary and distributed control of fluid flow and heat transfer problems. In the fully-optimal approach, we focus on the use of an inexact Newton solver for the necessary optimality condition arising from the implicit discretization of the optimization problem and the use of one-level and two-level space–time overlapping Schwarz preconditioners for the Jacobian system. We show that the numerical solution from the fully-optimal approach is generally better than the solution from the sub-optimal approach in terms of meeting the objective of the optimization problem. To demonstrate the robustness and parallel scalability and efficiency of the proposed algorithm, we present some numerical results obtained on a parallel computer with a few thousand processors.     

Development of a parallelized 2D/2D-axisymmetric Navier–Stokes equation solver for all-speed gas flows

A parallelized 2D/2D-axisymmetric pressure-based, extended SIMPLE finite-volume Navier–Stokes equation solver using Cartesians grids has been developed for simulating compressible, viscous, heat conductive and rarefied gas flows at all speeds with conjugate heat transfer. The discretized equations are solved by the parallel Krylov–Schwarz (KS) algorithm, in which the ILU and BiCGStab or GMRES scheme are used as the preconditioner and linear matrix equation solver, respectively. Developed code was validated by comparing previous published simulations wherever available for both low- and high-speed gas flows. Parallel performance for a typical 2D driven cavity problem is tested on the IBM-1350 at NCHC of Taiwan up to 32 processors. Future applications of this code are discussed briefly at the end.     

Parallel computation for shallow water flow: A domain decomposition approach

This paper describes a strategy for the parallelization of a finite element code for the numerical simulation of shallow water flow. The numerical scheme adopted for the discretization of the equations in the scalar algorithm is briefly described, with emphasis on the aspects concerning its porting to a parallel architecture. The parallelization strategy is of the domain decomposition type: the implicit computational kernel of the scheme, a Poisson problem, is solved by an additive Schwarz preconditioning technique within conjugate gradient iterations. Both the theoretical and the implementation aspects of the domain decomposition method are described as applied in the present context. Finally, some computational examples are shown and discussed.     

Restricted overlapping balancing domain decomposition methods and restricted coarse problems for the Helmholtz problem

Overlapping balancing domain decomposition methods and their combination with restricted additive Schwarz methods are proposed for the Helmholtz equation. These new methods also extend previous work on non-overlapping balancing domain decomposition methods toward simplifying their coarse problems and local solvers. They also extend restricted Schwarz methods, originally designed to overlapping domain decomposition and Dirichlet local solvers, to the case of non-overlapping domain decomposition and/or Neumann and Sommerfeld local solvers. Finally, we introduce coarse spaces based on partitions of unity and planes waves, and show how oblique projection coarse problems can be designed from restricted additive Schwarz methods. Numerical tests are presented.     

Pseudospectral matrix element methods for flow in complex geometry

A pseudospectral matrix element (PSME) method, which extended the global pseudospectral method to a multi-element scheme, has been applied to the solution of the incompressible, primitive variable, Navier-Stokes equations for complex geometries with rectilinear or curvilinear boundaries. For a simple complex geometry, a direct solution for pressure Poisson equation is feasible, while in a much more complex geometry the pressure solution is accomplished by a new implementation of domain decomposition approach. According to this approach, the computational domain can be divided into a number of overlapping subdomains where the grid points inside the overlapping area may or may not be located at the same place. Each subdomain can be mapped onto a square domain by an algebraic (or isoparametric) mapping, of simpler geometry with patched elements, in which the pressure solution is more easily obtained by an eigenfunction expansion technique for cartesian-type geometries or a direct solver for noncartesian-type geometries with rectilinear (or curvilinear) boundaries. With an iterative Schwarz alternating procedure (SAP) between subdomains, the complete solution is found. The novel feature of this approach are (i) the continuity equation is satisfied everywhere, in the interior (including the inter-element points) and on the boundary; (ii) reducing the global storage size to local (subdomain) storage locations for which parallel computation is easily implemented; (iii) producing the desired grid points without solving any grid-generating equations is easy; and (iv) consistent mass conservation holds at geometrical singular points despite their discontinuous slope (i.e., singular vorticity). Numerical examples of flow over a triangular and parabolic bump as well as flow in a bifurcation with a daughter branch entering the main channel at angles 45° and 90° are presented in this paper.     

A parallel fully coupled implicit domain decomposition method for numerical simulation of microfluidic mixing in 3D

A parallel fully coupled implicit fluid solver based on a Newton–Krylov–Schwarz algorithm is developed on top of the Portable, Extensible Toolkit for Scientific computation for the simulation of microfluidic mixing described by the three-dimensional unsteady incompressible Navier–Stokes equations. The popularly used fractional step method, originally designed for high Reynolds number flows, requires some modification of the inviscid-type pressure boundary condition in order to reduce the divergence error near the wall. On the other hand, the fully coupled approach works well without any special treatment of the boundary condition for low Reynolds number microchannel flows. A key component of the algorithm is an additive Schwarz preconditioner, which is used to accelerate the convergence of a linear Krylov-type solver for the saddle-point-type Jacobian systems. As a test case, we carefully study a three-dimensional passive serpentine micromixer and report the parallel performance of the algorithm obtained on a parallel machine with more than one hundred processors.     

A Fast Domain Decomposition High Order Poisson Solver

We present a fast high-order Poisson solver for implementation on parallel computers. The method uses deferred correction, such that high-order accuracy is obtained by solving a sequence of systems with a narrow stencil on the left-hand side. These systems are solved by a domain decomposition method. The method is direct in the sense that for any given order of accuracy, the number of arithmetic operations is fixed. Numerical experiments show that these high-order solvers easily outperform standard second-order ones. The very fast algorithm in combination with the coarser grid allowed for by the high-order method, also makes it quite possible to compete with adaptive methods and irregular grids for problems with solutions containing widely different scales.     

A parallel multigrid solver for incompressible flows on computing architectures with accelerators

An efficient parallel multigrid pressure correction algorithm is proposed for the solution of the incompressible Navier–Stokes equations on computing architectures with acceleration devices. The pressure correction procedure is based on the numerical solution of a Poisson-type problem, which is discretized using a fourth-order finite difference compact scheme. Since this is the most time-consuming part of the solver, we propose a parallel pressure correction algorithm using an iterative method based on a block cyclic reduction solution method combined with a multigrid technique. The grid points are numbered with respect to the red–black ordering scheme for the parallel Gauss–Seidel smoother. These parallelization techniques allow the execution of the entire simulation computations on the acceleration device, minimizing memory communication costs. The realization is developed using the OpenACC API, and the numerical method is demonstrated for the solution of two classical incompressible flow test problems. The first is the two-dimensional lid-driven cavity problem over equal mesh sizes while the other is the Stokes boundary layer, which is a decent benchmark problem for unequal mesh spacing. The effect of several multigrid components on modern and legacy acceleration architectures is examined. Eventually the performance investigation demonstrates that the proposed parallel multigrid solver achieves an acceleration of more than 10\(\times \) over the sequential solver and more than 4\(\times \) over multi-core CPU only realizations for all tested accelerators.     

二维Helmholtz方程外问题基于自然边界归化的重叠型区域分解算法

１．引 言 设是平面光滑闭曲线,是以为边界的外部区域,考虑二维Ｈｅｌｍｈｏｌｔｚ方程外Ｎｅｕｍａｎｎ问题并在无穷远处满足Ｓｏｍｍｅｒｆｅｌｄ辐射条件其中是区域的边界的外法线方向,即指向由包围的内部区域．κ在许多情况下（例如约化波动方程）是实数,在另一些情况下则是纯虚数．本文仅讨论κ为纯虚数的情况,且不失一般性,可设Ｉｍ（ｋ）＞０． 用某些数值方法求解线性抛物型方程或线性双曲型方程的初边值问题时,可能导致求解Ｈｅｌｍｈｏｌｔｚ方程的外问题．例如,用自然边界元法求解线性抛物型方程的初边值问题时就导致求…     

A Hierarchical 3-D Poisson Modified Fourier Solver by Domain Decomposition

We present a Domain Decomposition non-iterative solver for the Poisson equation in a 3-D rectangular box. The solution domain is divided into mostly parallelepiped subdomains. In each subdomain a particular solution of the non-homogeneous equation is first computed by a fast spectral method. This method is based on the application of the discrete Fourier transform accompanied by a subtraction technique. For high accuracy the subdomain boundary conditions must be compatible with the specified inhomogeneous right hand side at the edges of all the interfaces. In the following steps the partial solutions are hierarchically matched. At each step pairs of adjacent subdomains are merged into larger units. In this paper we present the matching algorithm for two boxes which is a basis of the domain decomposition scheme. The hierarchical approach is convenient for parallelization and minimizes the global communication. The algorithm requires O(N ³:log:N) operations, where N is the number of grid points in each direction.     

一般稀疏线性方程组的因子组合型并行预条件研究

基于因子组合给出一般稀疏线性方程组的一种新并行预条件。在该方案中,应用基于邻接图的重叠区域分解,形成一串相互重叠的子区域。对每个子区域,可以采用任何不完全LU分解。之后,利用全局三角因子与全局下三角因子的乘积作为全局的并行预条件,其中全局三角因子利用限制加性Schwarz思想对每个局部上三角因子的逆进行组合得到。分析表明,提出的预条件优于经典加性Schwarz和限制加性Schwarz,且能保持对称正定性。对混凝土细观数值模拟中线性方程组的实验再次表明,新方案优于经典加性Schwarz。     

Schwarz iterations for the efficient solution of screen problems with boundary elements

This paper investigates two domain decomposition algorithms for the numerical solution of boundary integral equations of the first kind. The schemes are based on theh-type boundary element Galerkin method to which the multiplicative and the additive Schwarz methods are applied. As for twodimensional problems, the rates of convergence of both methods are shown to be independent of the number of unknowns. Numerical results for standard model problems arising from Laplaces' equation with Dirichlet or Neumann boundary conditions in both two and three dimensions are discussed. A multidomain decomposition strategy is indicated by means of a screen problem in three dimensions, so as to obtain satisfactory experimental convergence rates.     

Parallel frequency filtering

The frequency filtering method is a robust and efficient ILU-like solver for large sparse systems (cf. [9,10]). Combining this method with the so-called Schur-complement DD method, we obtain a fast parallel solver. In this context, frequency filtering can be applied as solver inside the subdomains as well as for the treatment of the arising Schur complements. Especially for those, the method is well suited since it is highly parallelizable by recursively applying the same decomposition as to the original system. In this paper, an implementation of the frequency filtering domain decomposition (FFDD) method on a multiprocessor system will be presented and the numerical results of some variants thereof be discussed. The scaling behaviour of the algorithm for an increasing number of processors is almost optimal.     

A finite volume method parallelization for the simulation of free surface shallow water flows

We construct a parallel algorithm, suitable for distributed memory architectures, of an explicit shock-capturing finite volume method for solving the two-dimensional shallow water equations. The finite volume method is based on the very popular approximate Riemann solver of Roe and is extended to second order spatial accuracy by an appropriate TVD technique. The parallel code is applied to distributed memory architectures using domain decomposition techniques and we investigate its performance on a grid computer and on a Distributed Shared Memory supercomputer. The effectiveness of the parallel algorithm is considered for specific benchmark test cases. The performance of the realization measured in terms of execution time and speedup factors reveals the efficiency of the implementation.     

非结构网格上求解中子输运方程的并行流水线Sn扫描算法

间断有限元离散纵标方法(Sn)是广泛应用于求解高维非定常中子输运方程的数值方法,它涉及几何网格空间、速度相空间和中子能群的离散,计算量很大．该文基于非结构网格,提出了基于区域分解的并行流水线Sn扫描算法,通过设计具有不同内在并行度和通信面体比的区域分解方法和队列插入算法,对两个不同物理模型,分别使用两台并行机的92个和256个CPU,获得72倍和78倍以上的加速．可扩展性能分析表明,算法的性能非常依赖于并行机的点对点通信延迟．     

Improved filtering for weighted circuit constraints

We study the weighted circuit constraint in the context of constraint programming. It appears as a substructure in many practical applications, particularly routing problems. We propose a domain filtering algorithm for the weighted circuit constraint that is based on the 1-tree relaxation of Held and Karp. In addition, we study domain filtering based on an additive bounding procedure that combines the 1-tree relaxation with the assignment problem relaxation. Experimental results on Traveling Salesman Problem instances demonstrate that our filtering algorithms can dramatically reduce the problem size. In particular, the search tree size and solving time can be reduced by several orders of magnitude, compared to existing constraint programming approaches. Moreover, for medium-size problem instances, our method is competitive with the state-of-the-art special-purpose TSP solver Concorde.     

The Influence of Interface Conditions on Convergence of Krylov-Schwarz Domain Decomposition for the Advection-Diffusion Equation

Several variants of Schwarz domain decomposition, which differ in the choice of interface conditions, are studied in a finite volume context. Krylov subspace acceleration, GMRES in this paper, is used to accelerate convergence. Using a detailed investigation of the systems involved, we can minimize the memory requirements of GMRES acceleration. It is shown how Krylov subspace acceleration can be easily built on top of an already implemented Schwarz domain decomposition iteration, which makes Krylov-Schwarz algorithms easy to use in practice. The convergence rate is investigated both theoretically and experimentally. It is observed that the Krylov subspace accelerated algorithm is quite insensitive to the type of interface conditions employed.