Domain decomposition methods for the neutron diffusion problem

The neutronic simulation of a nuclear reactor core is performed using the neutron transport equation, and leads to an eigenvalue problem in the steady-state case. Among the deterministic resolution methods, simplified transport (S_PN$S{P}_N$) or diffusion approximations are often used. The MINOS solver developed at CEA Saclay uses a mixed dual finite element method for the resolution of these problems, and has shown his efficiency. In order to take into account the heterogeneities of the geometry, a very fine mesh is generally required, and leads to expensive calculations for industrial applications. In order to take advantage of parallel computers, and to reduce the computing time and the local memory requirement, we propose here two domain decomposition methods based on the MINOS solver. The first approach is a component mode synthesis method on overlapping subdomains: several eigenmodes solutions of a local problem on each subdomain are taken as basis functions used for the resolution of the global problem on the whole domain. The second approach is an iterative method based on a non-overlapping domain decomposition with Robin interface conditions. At each iteration, we solve the problem on each subdomain with the interface conditions given by the solutions on the adjacent subdomains estimated at the previous iteration. Numerical results on parallel computers are presented for the diffusion model on realistic 2D and 3D cores.     

A Fast Spectral Subtractional Solver for Elliptic Equations

The paper presents a fast subtractional spectral algorithm for the solution of the Poisson equation and the Helmholtz equation which does not require an extension of the original domain. It takes O(N ² log N) operations, where N is the number of collocation points in each direction. The method is based on the eigenfunction expansion of the right hand side with integration and the successive solution of the corresponding homogeneous equation using Modified Fourier Method. Both the right hand side and the boundary conditions are not assumed to have any periodicity properties. This algorithm is used as a preconditioner for the iterative solution of elliptic equations with non-constant coefficients. The procedure enjoys the following properties: fast convergence and high accuracy even when the computation employs a small number of collocation points. We also apply the basic solver to the solution of the Poisson equation in complex geometries.     

Multiple search direction conjugate gradient method I: methods and their propositions

In this article, we proposed a new CG-type method based on domain decomposition method, which is called multiple search direction conjugate gradient (MSD-CG) method. In each iteration, it uses a search direction in each subdomain. Instead of making all search directions conjugate to each other, as in the block CG method [O'Leary, D. P. (1980). The block conjugate gradient algorithm and related methods. Lin. Alg. Appl., 29, 293–322.], we require that they are nonzero in corresponding subdomains only. The GIPF-CG method, an approximate version of the MSD-CG method, only requires communication between neighboring subdomains and eliminate global inner product entirely. This method is therefore well suited for massively parallel computation. We give some propositions and a preconditioned version of the MSD-CG method.     

A Nonoverlapping Domain Decomposition Method for Legendre Spectral Collocation Problems

We consider the Dirichlet boundary value problem for Poisson’s equation in an L-shaped region or a rectangle with a cross-point. In both cases, we approximate the Dirichlet problem using Legendre spectral collocation, that is, polynomial collocation at the Legendre–Gauss nodes. The L-shaped region is partitioned into three nonoverlapping rectangular subregions with two interfaces and the rectangle with the cross-point is partitioned into four rectangular subregions with four interfaces. In each rectangular subregion, the approximate solution is a polynomial tensor product that satisfies Poisson’s equation at the collocation points. The approximate solution is continuous on the entire domain and its normal derivatives are continuous at the collocation points on the interfaces, but continuity of the normal derivatives across the interfaces is not guaranteed. At the cross point, we require continuity of the normal derivative in the vertical direction. The solution of the collocation problem is first reduced to finding the approximate solution on the interfaces. The discrete Steklov–Poincaré operator corresponding to the interfaces is self-adjoint and positive definite with respect to the discrete inner product associated with the collocation points on the interfaces. The approximate solution on the interfaces is computed using the preconditioned conjugate gradient method. A preconditioner is obtained from the discrete Steklov–Poincaré operators corresponding to pairs of the adjacent rectangular subregions. Once the solution of the discrete Steklov–Poincaré equation is obtained, the collocation solution in each rectangular subregion is computed using a matrix decomposition method. The total cost of the algorithm is O(N ³), where the number of unknowns is proportional to N ².      

Doubling the Degree of Precision Without Doubling the Grid When Solving a Differential Equation with a Pseudo-Spectral Collocation Method

In the conventional pseudo-spectral collocation method to solve an ordinary first order differential equation, the derivative is obtained from Lagrange interpolation and has degree of precision N for a grid of (N+1) points. In the present, novel method Hermite interpolation is used as point of departure. From this the second order derivative is obtained with degree of precision (2N+1) for the same grid as above. The associated theorem constitutes the main result of this paper. Based on that theorem a method in put forward in which the differential equation and the differentiated differential equation are simultaneously collocated. In this method every grid point counts for two. The double collocation leads to a solution accuracy which is superior to the precision obtained with the conventional method for the same grid. This superiority is demonstrated by 3 examples, 2 linear problems and a non-linear one. In the examples it is shown that the accuracy obtained with the present method is comparable to the solution accuracy of the standard method with twice the number of grid points. However, the condition number of the present method grows like N ³ as compared to N ² in the standard method.     

A spatial domain decomposition approach to distributed H ∞ observer design of a linear unstable parabolic distributed parameter system with spatially discrete sensors

This paper discusses the design problem of distributed H_∞ Luenberger-type partial differential equation (PDE) observer for state estimation of a linear unstable parabolic distributed parameter system (DPS) with external disturbance and measurement disturbance. Both pointwise measurement in space and local piecewise uniform measurement in space are considered; that is, sensors are only active at some specified points or applied at part thereof of the spatial domain. The spatial domain is decomposed into multiple subdomains according to the location of the sensors such that only one sensor is located at each subdomain. By using Lyapunov technique, Wirtinger's inequality at each subdomain, and integration by parts, a Lyapunov-based design of Luenberger-type PDE observer is developed such that the resulting estimation error system is exponentially stable with an H_∞ performance constraint, and presented in terms of standard linear matrix inequalities (LMIs). For the case of local piecewise uniform measurement in space, the first mean value theorem for integrals is utilised in the observer design development. Moreover, the problem of optimal H_∞ observer design is also addressed in the sense of minimising the attenuation level. Numerical simulation results are presented to show the satisfactory performance of the proposed design method.     

蚁群算法求解连续空间优化问题的一种方法

针对蚁群算法不太适合求解连续性优化问题的缺陷,提出用蚁群算法求解连续空间优化问题的一种方法.该方法将解空间划分成若干子域,在蚁群算法的每一次迭代中,首先根据信息量求出解所在的子域,然后在该子域内已有的解中确定解的具体值.以非线性规划问题为例所进行的计算结果表明,该方法比使用模拟退火算法、遗传算法具有更好的收敛速度.     

Spectral multidomain technique with Local Fourier Basis

A novel domain decomposition method for spectrally accurate solutions of PDEs is presented. A Local Fourier Basis technique is adapted for the construction of the elemental solutions in subdomains.C ¹ continuity is achieved on the interfaces by a matching procedure using the analytical homogeneous solutions of a one dimensional equation. The method can be applied to the solution of elliptic problems of the Poisson or Helmholtz type as well as to time discretized parabolic problems in one or more dimensions. The accuracy is tested for several stiff problems with steep solutions.The present domain decomposition approach is particularly suitable for parallel implementations, in particular, on MIMD type parallel machines.This research is supported partly by a grant from the French-Israeli Binational Foundation for 1991–1992.     

Parallel hybrid particle/finite volume algorithm for transported PDF methods employing sub-time stepping

A previously presented hybrid finite volume/particle method for the solution of the joint-velocity-frequency-composition probability density function (JPDF) transport equation in complex 3D geometries is extended for parallel computing. The parallelization strategy is based on domain decomposition. The finite volume method (FVM) and the particle method (PM) are parallelized separately and the algorithm is fully synchronous. For the FVM a standard method based on transferring data in ghost cells is used. Moreover, a subdomain interior decomposition algorithm to efficiently solve the implicit time integration for hyperbolic systems is described. The parallelization of the PM is more complicated due to the use of a sub-time stepping algorithm for the particle trajectory integration. Hereby, each particle obeys its local CFL criterion, and the covered distances per global time step can vary significantly. Therefore, an efficient algorithm which deals with this issue and has minimum communication effort was devised and implemented. Numerical tests to validate the parallel vs. the serial algorithm are presented, where also the effectiveness of the subdomain interior decomposition for the implicit time integration was investigated. A 3D dump-combustor configuration test case with about 2.5 × 10⁵ cells was used to demonstrate the good performance of the parallel algorithm. The hybrid algorithm scales well and the maximum speedup on 60 processors for this configuration was 50 (≈80% parallel efficiency).     

Domain decomposition algorithm based on the group explicit formula for the heat equation

A finite difference domain decomposition algorithm (DDA) for solving the heat equation in parallel is presented. In this procedure, interface values between subdomains are calculated by the group explicit formula, whereas interior values of subdomains are determined by the classical implicit scheme. The stability and convergence for this DDA are proved. The stability bound of the procedure is derived to be eight times that of the classical explicit scheme. Though the truncation error at the interface is O(τ?+?h), L ²-error is proved to be O(τ?+?h ²). Numerical examples confirm the second-order convergence and indicate that the stability condition is sharp. A comparison of the numerical errors of this procedure with other known methods is also included.     

Iterative methods for model reduction by domain decomposition

It is proposed a method to reduce the computational effort to solve a partial differential equation on a given domain. The main idea is to split the domain of interest in two subdomains, and to use different approximation methods in each of the two subdomains. In particular, in one subdomain we discretize the governing equations by a canonical scheme, whereas in the other one we solve a reduced order model of the original problem. Different approaches to couple the low-order model to the usual discretization are presented. The effectiveness of these approaches is tested on numerical examples pertinent to non-linear model problems including Laplace equation with non-linear boundary conditions and compressible Euler equations.     

A Domain Decomposition Fourier Continuation Method for Enhanced $$L_1$$ Regularization Using Sparsity of Edges in Reconstructing Fourier Data

\(L_1\) regularization is widely used in various applications for sparsifying transform. In Wasserman et al. (J Sci Comput 65(2):533–552, 2015) the reconstruction of Fourier data with \(L_1\) minimization using sparsity of edges was proposed—the sparse PA method. With the sparse PA method, the given Fourier data are reconstructed on a uniform grid through the convex optimization based on the \(L_1\) regularization of the jump function. In this paper, based on the method proposed by Wasserman et al. (J Sci Comput 65(2):533–552, 2015) we propose to use the domain decomposition method to further enhance the quality of the sparse PA method. The main motivation of this paper is to minimize the global effect of strong edges in \(L_1\) regularization that the reconstructed function near weak edges does not benefit from the sparse PA method. For this, we split the given domain into several subdomains and apply \(L_1\) regularization in each subdomain separately. The split function is not necessarily periodic, so we adopt the Fourier continuation method in each subdomain to find the Fourier coefficients defined in the subdomain that are consistent to the given global Fourier data. The numerical results show that the proposed domain decomposition method yields sharp reconstructions near both strong and weak edges. The proposed method is suitable when the reconstruction is required only locally.     

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.     

Nodal Superconvergence of SDFEM for Singularly Perturbed Problems

In this paper, we analyze the streamline diffusion finite element method for one dimensional singularly perturbed convection-diffusion-reaction problems. Local error estimates on a subdomain where the solution is smooth are established. We prove that for a special group of exact solutions, the nodal error converges at a superconvergence rate of order (ln ε ⁻¹/N)^2k (or (ln N/N)^2k ) on a Shishkin mesh. Here ε is the singular perturbation parameter and 2N denotes the number of mesh elements. Numerical results illustrating the sharpness of our theoretical findings are displayed.     

Polynomial collocation using a domain decomposition solution to parabolic PDE's via the penalty method and explicit/implicit time marching

A domain decomposition method is examined to solve a time-dependent parabolic equation. The method employs an orthogonal polynomial collocation technique on multiple subdomains. The subdomain interfaces are approximated with the aid of a penalty method. The time discretization is implemented in an explicit/implicit finite difference method. The subdomain interface is approximated using an explicit Dufort-Frankel method, while the interior of each subdomain is approximated using an implicit backwards Euler's method. The principal advantage to the method is the direct implementation on a distributed computing system with a minimum of interprocessor communication. Theoretical results are given for Legendre polynomials, while computational results are given for Chebyshev polynomials. Results are given for both a single processor computer and a distributed computing system.     

Bregmanized Domain Decomposition for Image Restoration

Computational problems of large-scale data are gaining attention recently due to better hardware and hence, higher dimensionality of images and data sets acquired in applications. In the last couple of years non-smooth minimization problems such as total variation minimization became increasingly important for the solution of these tasks. While being favorable due to the improved enhancement of images compared to smooth imaging approaches, non-smooth minimization problems typically scale badly with the dimension of the data. Hence, for large imaging problems solved by total variation minimization domain decomposition algorithms have been proposed, aiming to split one large problem into N>1 smaller problems which can be solved on parallel CPUs. The N subproblems constitute constrained minimization problems, where the constraint enforces the support of the minimizer to be the respective subdomain. In this paper we discuss a fast computational algorithm to solve domain decomposition for total variation minimization. In particular, we accelerate the computation of the subproblems by nested Bregman iterations. We propose a Bregmanized Operator Splitting–Split Bregman (BOS-SB) algorithm, which enforces the restriction onto the respective subdomain by a Bregman iteration that is subsequently solved by a Split Bregman strategy. The computational performance of this new approach is discussed for its application to image inpainting and image deblurring. It turns out that the proposed new solution technique is up to three times faster than the iterative algorithm currently used in domain decomposition methods for total variation minimization.     

A conservative and monotone mixed-hybridized finite element approximation of transport problems in heterogeneous domains

In this article, we discuss the numerical approximation of transport phenomena occurring at material interfaces between physical subdomains with heterogenous properties. The model in each subdomain consists of a partial differential equation with diffusive, convective and reactive terms, the coupling between each subdomain being realized through an interface transmission condition of Robin type. The numerical approximation of the problem in the two-dimensional case is carried out through a dual mixed-hybridized finite element method with numerical quadrature of the mass flux matrix. The resulting method is a conservative finite volume scheme over triangular grids, for which a discrete maximum principle is proved under the assumption that the mesh is of Delaunay type in the interior of the domain and of weakly acute type along the domain external boundary and internal interface. The stability, accuracy and robustness of the proposed method are validated on several numerical examples motivated by applications in biology, electrophysiology and neuroelectronics.     

Parallel algorithms for finding polynomial Roots on OTIS-torus

We present two parallel algorithms for finding all the roots of an N-degree polynomial equation on an efficient model of Optoelectronic Transpose Interconnection System (OTIS), called OTIS-2D torus. The parallel algorithms are based on the iterative schemes of Durand–Kerner and Ehrlich methods. We show that the algorithm for the Durand–Kerner method requires (N ^0.75+0.5N ^0.25−1) electronic moves + 2(N ^0.5−1) OTIS moves using N processors. The parallel algorithm for Ehrlich method is shown to run in (N ^0.75+0.5N ^0.25−1) electronic moves + 2(N ^0.5−1) OTIS moves with the same number of processors. The algorithms have lower AT cost than the algorithms presented in Jana (Parallel Comput 32:301–312, 2006). The scalability of the algorithms is also discussed.     

An accurate algorithm for computing the eigenvalues of a polygonal membrane

For a polygonal domain Ω, we consider the eigenvalue problem Δu + λu = 0 in Ω, u = 0 on the boundary of Ω. Ω is decomposed into subdomains Ω₁, Ω₂,...; on each $\text{Ω}{}_{\mathrm{i}}$, u is approximated by a linear combination of functions which satisfy the equation Δu + Δu = 0 and continuity conditions are imposed at the boundaries of the subdomains. We propose a non-conventional method based on the use of a Rayleigh quotient. We present numerical examples and a proof of the exponential convergence of the algorithm.     

A load balancing package on distributed memory systems and its application to particle-particle particle-mesh (P3M) methods

We present a tool, Bisect, for balanced decomposition of spatial domains. In addition to applying a nested bisection algorithm to determine the boundaries of each subdomain, Bisect replicates a user specified zone along the boundaries of the subdomain in order to minimize future interactions between subdomains. Results of running the tool on the Cray T3D system using both shared memory operations and MPI communications are reported and discussed. In addition, Bisect is used in a parallel implementation of a particle-particle/particle-mesh (P3M) simulation program on the Cray T3D system. The performance of the P3M program with different load-balancing criteria is evaluated and compared. The results show that the use of the Bisect package balances the load efficiently and minimizes communication on the T3D massively parallel system.