Search

This article presents a parallel finite element discretization scheme for solving numerically the steady natural convection equations, where a fully overlapping domain decomposition technique is used for parallelization. In this scheme, each processor computes independently a local solution in its subdomain using a mesh that covers the entire domain. It has a small mesh size h around the subdomain and a large mesh size H away from the subdomain. The discretization scheme is easy to implement based on existing serial software. It can yield an optimal convergence rate for the approximate solutions with suitable algorithmic parameters. Compared with the standard finite element method, the scheme is able to obtain an approximate solution of comparable accuracy with considerable reduction in computational time. Theoretical and numerical results show the promise of the scheme, where numerical simulation results for some benchmark problems such as the buoyancy-driven square cavity flow, right-angled triangular cavity flow and sinusoidal hot cylinder flow are provided. [ABSTRACT FROM AUTHOR]

In this paper, we develop a new splitting characteristic finite difference scheme for solving the time-fractional mobile-immobile nonlinear advection–diffusion equation by combining non-overlapping block-divided domain decomposition method, the operator splitting technique and the characteristic finite difference method. Over each sub-domain, the solutions and fluxes along x-direction in the interiors of sub-domains are computed by the implicit characteristic finite difference method while the intermediate fluxes on the interfaces of sub-domains are computed by local multi-point weighted average from the approximate solutions at characteristic tracking points which are solved by the quadratic interpolation. Secondly, the solutions and fluxes along y direction in the interiors of sub-domains are computed lastly by the implicit characteristic difference method while the time fractional derivative is approximated by L1-format and the intermediate fluxes on the interfaces of sub-domains are computed by local multi-point weighted average from the approximate solutions at characteristic tracking points are solved by the quadratic interpolation. Applying Brouwer fixed point theorem, we prove strictly the existence and uniqueness of the proposed scheme. The conditional stability and convergence with O Δ t + Δ t 2 - α + h 2 + H 5 2 of the proposed scheme are given as well. Numerical experiments verify the theoretical results. [ABSTRACT FROM AUTHOR]

We construct and analyze a multiscale finite element method for an elliptic distributed optimal control problem with pointwise control constraints, where the state equation has rough coefficients. We show that the performance of the multiscale finite element method is similar to the performance of standard finite element methods for smooth problems and present corroborating numerical results. [ABSTRACT FROM AUTHOR]

This paper is concerned with the numerical solution of compressible fluid flow in a fractured porous medium. The fracture represents a fast pathway (i.e., with high permeability) and is modeled as a hypersurface embedded in the porous medium. We aim to develop fast-convergent and accurate global-in-time domain decomposition (DD) methods for such a reduced fracture model, in which smaller time step sizes in the fracture can be coupled with larger time step sizes in the subdomains. Using the pressure continuity equation and the tangential PDEs in the fracture-interface as transmission conditions, three different DD formulations are derived; each method leads to a space-time interface problem which is solved iteratively and globally in time. Efficient preconditioners are designed to accelerate the convergence of the iterative methods while preserving the accuracy in time with nonconforming grids. Numerical results for two-dimensional problems with non-immersed and partially immersed fractures are presented to show the improved performance of the proposed methods. [ABSTRACT FROM AUTHOR]

An improved neural networks method based on domain decomposition is proposed to solve partial differential equations, which is an extension of the physics informed neural networks (PINNs). Although recent research has shown that PINNs perform effectively in solving partial differential equations, they still have difficulties in solving large-scale complex problems, due to using a single neural network and gradient pathology. In this paper, the proposed approach aims at implementing calculations on sub-domains and improving the expressiveness of neural networks to mitigate gradient pathology. By investigations, it is shown that, although the neural networks structure and the loss function are complicated, the proposed method outperforms the classical PINNs with respect to training effectiveness, computational accuracy, and computational cost. [ABSTRACT FROM AUTHOR]

We investigate multiscale finite element methods for an elliptic distributed optimal control problem with rough coefficients. They are based on the (local) orthogonal decomposition methodology of Målqvist and Peterseim. [ABSTRACT FROM AUTHOR]

A space reduction method for structural operator equations is proposed in this paper. It turns out that many interface problems derived by applying the idea of domain decomposition can be categorized into this framework. A seemingly simple algebraic technique is proposed to reduce the complexity of operator equations. The connection between this technique and the integral equation method is revealed. Under mild conditions, we prove that the reduced operator equation by space reduction is well-posed, and its solution is the same as that of the original one. As two applications, we apply the proposed method to solve a planar triangular lattice problem and an exterior problem of modified Helmholtz equation with FEM discretization. The numerical evidence validates the effectiveness. [ABSTRACT FROM AUTHOR]

We analyze the convergence of the one-level overlapping domain decomposition preconditioner SORAS (Symmetrized Optimized Restricted Additive Schwarz) applied to a generic linear system whose matrix is not necessarily symmetric/self-adjoint nor positive definite. By generalizing the theory for the Helmholtz equation developed in Graham et al. (SIAM J Numer Anal 58(5):2515–2543, 2020. ), we identify a list of assumptions and estimates that are sufficient to obtain an upper bound on the norm of the preconditioned matrix, and a lower bound on the distance of its field of values from the origin. We stress that our theory is general in the sense that it is not specific to one particular boundary value problem. Moreover, it does not rely on a coarse mesh whose elements are sufficiently small. As an illustration of this framework, we prove new estimates for overlapping domain decomposition methods with Robin-type transmission conditions for the heterogeneous reaction–convection–diffusion equation (to prove the stability assumption for this equation we consider the case of a coercive bilinear form, which is non-symmetric, though). [ABSTRACT FROM AUTHOR]

We study a decoupling iterative algorithm based on domain decomposition for the time-dependent nonlinear Stokes–Darcy model, in which different time steps can be used in the flow region and in the porous medium. The coupled system is formulated as a space-time interface problem based on the interface condition for mass conservation. The nonlinear interface problem is then solved by a nested iteration approach which involves, at each Newton iteration, the solution of a linearized interface problem and, at each Krylov iteration, parallel solution of time-dependent linearized Stokes and Darcy problems. Consequently, local discretizations in time (and in space) can be used to efficiently handle multiphysics systems of coupled equations evolving at different temporal scales. Numerical results with nonconforming time grids are presented to illustrate the performance of the proposed method. [ABSTRACT FROM AUTHOR]

The development of modern computing architectures with ever-increasing amounts of parallelism has allowed for the solution of previously intractable problems across a variety of scientific disciplines. Despite these advances, multiscale computing problems continue to pose an incredible challenge to modern architectures because they require resolving scales that often vary by orders of magnitude in both space and time. Such complications have led us to consider alternative discretizations for partial differential equations (PDEs) which use expansions involving integral operators to approximate spatial derivatives (Christlieb et al. in J Comput Phys 379:214–236, 2019; Christlieb et al. J Sci Comput 82:52(3):1–29, 2020; Christlieb et al. J Comput Phys 415:1–25, 2020). These constructions use explicit information within the integral terms, but treat boundary data implicitly, which contributes to the overall speed of the method. This approach is provably unconditionally stable for linear problems and stability has been demonstrated experimentally for nonlinear problems. Additionally, it is matrix-free in the sense that it is not necessary to invert linear systems and iteration is not required for nonlinear terms. Moreover, the scheme employs a fast summation algorithm that yields a method with a computational complexity of O (N) , where N is the number of mesh points along a coordinate direction. While much work has been done to explore the theory behind these methods, their practicality in large scale computing environments is a largely unexplored topic. In this work, we explore the performance of these methods by developing a domain decomposition algorithm suitable for distributed memory systems along with shared memory algorithms. As a first pass, we derive an artificial Courant–Friedrichs–Lewy condition that enforces a nearest-neighbor (N-N) communication pattern and briefly discuss possible generalizations. We also analyze several approaches for implementing the parallel algorithms by optimizing predominant loop structures and maximizing data reuse. Using a hybrid design that employs MPI and Kokkos (Edwards and Trott in J Parallel Distrib Comput 74:3202–3216, 2014) for the distributed and shared memory components of the algorithms, respectively, we show that our methods are efficient and can sustain an update rate > 1 × 10 8 DOF/node/s. We provide results that demonstrate the scalability and versatility of our algorithms using several different PDE test problems, including a nonlinear example, which employs an adaptive time-stepping rule. [ABSTRACT FROM AUTHOR]

Richards’ equation is used to describe water flow in porous media. It is strongly nonlinear, which makes the approximation of its solution a challenging task. In this study, we aim to linearize Richards’ equation using the exponential Gardner models of hydraulic conductivity and moisture content variables. Then, we propose a new formulation of radial basis function partition of unity method (RBFPUM) based on d-rectangular patches as local subdomains in order to approximate the solution of the linearized Richards’ equation. In particular, the multivariate weights are expressed as a product of one dimensional Wendland compactly supported radial basis functions. With small values of the shape parameter contained in the Gaussian radial basis function, safe computations of the solution will be achieved by adopting RBF-QR algorithm (Forenberg et al. in SIAM J Sci Comput 33(2):869–892, 2011). Hence, an efficient numerical solution can be obtained not only in terms of safe computations but also in terms of accuracy, as we will see in the numerical examples. In order to deal with layered soils, another method is proposed for the 2D and the 3D cases. It is based on the domain decomposition principle coupled with RBFPUM by using d-rectangular patches and the RBF-QR algorithm. The matching conditions, i.e. the continuity of mass fluxes and pressure head, are imposed at the interface between zones via the Steklov–Poincaré equation. The efficiency of the proposed method will be examined via some examples. [ABSTRACT FROM AUTHOR]

In this paper, we consider a primal-dual domain decomposition method for total variation regularized problems appearing in mathematical image processing. The model problem is transformed into an equivalent constrained minimization problem by tearing-and-interconnecting domain decomposition. Then, the continuity constraints on the subdomain interfaces are treated by introducing Lagrange multipliers. The resulting saddle point problem is solved by the first order primal-dual algorithm. We apply the proposed method to image denoising, inpainting, and segmentation problems with either L 2 -fidelity or L 1 -fidelity. Numerical results show that the proposed method outperforms the existing state-of-the-art methods. [ABSTRACT FROM AUTHOR]

In this work, we propose efficient and accurate numerical algorithms based on difference potentials method for numerical solution of chemotaxis systems and related models in 3D. The developed algorithms handle 3D irregular geometry with the use of only Cartesian meshes and employ Fast Poisson Solvers. In addition, to further enhance computational efficiency of the methods, we design a difference-potentials-based domain decomposition approach which allows mesh adaptivity and easy parallelization of the algorithm in space. Extensive numerical experiments are presented to illustrate the accuracy, efficiency and robustness of the developed numerical algorithms. [ABSTRACT FROM AUTHOR]

Nowadays, as large scale images become available, the necessity of parallel algorithms for image processing has been arisen. In this paper, we propose domain decomposition methods as parallel solvers for solving total variation minimization problems with L1 fidelity term. The image domain is decomposed into rectangular subdomains, where the local total variation problems are solved. We introduce the notion of dual conversion, which generalizes the framework of Chambolle-Pock primal-dual algorithm (J Math Imaging Vis 40:120-145, 2011). By the dual conversion, the TV-L1 model is transformed into an equivalent saddle point problem which has a natural parallel structure. The primal problem of the resulting saddle point problem is decoupled in the sense that each local problem can be solved independently. Convergence analysis of the proposed algorithms is provided. We apply the proposed algorithms for image denoising, inpainting, and deblurring problems. Our numerical results ensure that the proposed algorithms have good performance as parallel solvers. [ABSTRACT FROM AUTHOR]

The use of implicit methods for numerical time integration typically generates very large systems of equations, often too large to fit in memory. To address this it is necessary to investigate ways to reduce the sizes of the involved linear systems. We describe a domain decomposition approach for the advection-diffusion equation, based on the Summation-by-Parts technique in both time and space. The domain is partitioned into non-overlapping subdomains. A linear system consisting only of interface components is isolated by solving independent subdomain-sized problems. The full solution is then computed in terms of the interface components. The Summation-by-Parts technique provides a solid theoretical framework in which we can mimic the continuous energy method, allowing us to prove both stability and invertibility of the scheme. In a numerical study we show that single-domain implementations of Summation-by-Parts based time integration can be improved upon significantly. Using our proposed method we are able to compute solutions for grid resolutions that cannot be handled efficiently using a single-domain formulation. An order of magnitude speed-up is observed, both compared to a single-domain formulation and to explicit Runge-Kutta time integration. [ABSTRACT FROM AUTHOR]

L1 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 L1 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 L1 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 L1 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 L1 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. [ABSTRACT FROM AUTHOR]

We analyse a class of nonoverlapping domain decomposition preconditioners for nonsymmetric linear systems arising from discontinuous Galerkin finite element approximations of fully nonlinear Hamilton-Jacobi-Bellman (HJB) partial differential equations. These nonsymmetric linear systems are uniformly bounded and coercive with respect to a related symmetric bilinear form, that is associated to a matrix $$\mathbf {A}$$ . In this work, we construct a nonoverlapping domain decomposition preconditioner $$\mathbf {P}$$ , that is based on $$\mathbf {A}$$ , and we then show that the effectiveness of the preconditioner for solving the nonsymmetric problems can be studied in terms of the condition number $$\kappa (\mathbf {P}^{-1}\mathbf {A})$$ . In particular, we establish the bound $$\kappa (\mathbf {P}^{-1}\mathbf {A})\lesssim 1+ p^6 H^3 /q^3 h^3$$ , where H and h are respectively the coarse and fine mesh sizes, and q and p are respectively the coarse and fine mesh polynomial degrees. This represents the first such result for this class of methods that explicitly accounts for the dependence of the condition number on q; our analysis is founded upon an original optimal order approximation result between fine and coarse discontinuous finite element spaces. Numerical experiments demonstrate the sharpness of this bound. Although the preconditioners are not robust with respect to the polynomial degree, our bounds quantify the effect of the coarse and fine space polynomial degrees. Furthermore, we show computationally that these methods are effective in practical applications to nonsymmetric, fully nonlinear HJB equations under h-refinement for moderate polynomial degrees. [ABSTRACT FROM AUTHOR]

We present some two-level non-overlapping and overlapping additive Schwarz methods for discontinuous Galerkin methods for the biharmonic equation. It is shown that the condition numbers of the preconditioned systems are of the order $$O\left( \left( \frac{H}{h}\right) ^3\right) $$ for the non-overlapping method, and of the order $$O\left( \frac{H}{h}+\left( \frac{H}{\delta }\right) ^3\right) $$ for the overlapping method, where h and H stand for the fine and coarse mesh sizes respectively, and $$\delta $$ denotes the size of the overlaps between subdomains. In particular, emphasis is placed on studying the influence of the penalty parameters and the choice of the coarse mesh bilinear form on the condition numbers. Numerical experiments are provided to gauge the efficiency of the methods and to validate the theory. [ABSTRACT FROM AUTHOR]

In this paper, a least-squares spectral element method for parabolic initial value problem for two space dimension on parallel computers is presented. The theory is also valid for three dimension. This method gives exponential accuracy in both space and time. The method is based on minimization of residuals in terms of the partial differential equation and initial condition, in different Sobolev norms, and a term which measures the jump in the function and its derivatives across inter-element boundaries in appropriate fractional Sobolev norms. Rigorous error estimates for this method are given. Some specific numerical examples are solved to show the efficiency of this method. [ABSTRACT FROM AUTHOR]

Due to the advance of image capturing devices, huge size of images are available in our daily life. As a consequence the processing of large scale image data is highly demanded. Since the total variation (TV) is kind of de facto standard in image processing, we consider block decomposition methods for TV based variational models to handle large scale images. Unfortunately, TV is non-separable and non-smooth and it thus is challenging to solve TV based variational models in a block decomposition. In this paper, we introduce a primal-dual stitching (PDS) method to efficiently process the TV based variational models in the block decomposition framework. To characterize TV in the block decomposition framework, we only focus on the proximal map of TV function. Empirically, we have observed that the proposed PDS based block decomposition framework outperforms other state-of-art methods such as Bregman operator splitting based approach in terms of computational speed. [ABSTRACT FROM AUTHOR]

This paper deals with the efficient and accurate computation of extracellular potentials in a simplified model of myocardial tissue. The electrical activity of the heart is characterized by a narrow wavefront spreading through the myocardium. To increase the accuracy of the computation, a non-conforming non-overlapping domain decomposition based on the mortar method is used, allowing adaptivity in the regions closed to the wavefront. The benefits of the adaptive grid refinement process are illustrated by numerical results that show how the method works and its efficiency if compared to the classical conforming Finite Element Method. [ABSTRACT FROM AUTHOR]

High order implicit methods are constructed for the solution of first order hyperbolic systems of PDE. The methods are based on the deferred correction principle in both space and time, and require only p/2 stages at each timestep for achieving accuracy of order p. Furthermore, they are suitable for applying domain decomposition techniques for implementation on parallel computers. [ABSTRACT FROM AUTHOR]

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( N3:log: N) operations, where N is the number of grid points in each direction. [ABSTRACT FROM AUTHOR]

A pseudospectral method for the solution of incompressible flow problems based on an iterative solver involving an implicit treatment of linearized convective terms is presented. The method is designed for moderately complex geometries by means of a multi-domain approach. Key components are a Chebyshev collocation discretization, a special pressure-correction scheme and a restarted GMRES method with a preconditioner derived from a fast direct solver. The performance of the method with respect to the multi-domain functionality is investigated and compared to finite-volume approaches. [ABSTRACT FROM AUTHOR]

We consider the Poisson equation with Dirichlet boundary conditions, in a domain Ω\ $$\bar B$$ , where Ω⊂ ℝ n, and B is a collection of smooth open subsets (typically balls). The objective is to split the initial problem into two parts: a problem set in the whole domain Ω, for which fast solvers can be used, and local subproblems set in narrow domains around the connected components of B, which can be solved in a fully parallel way. We shall present here a method based on a multi-domain formulation of the initial problem, which leads to a fixed point algorithm. The convergence of the algorithm is established, under some conditions on a relaxation parameter θ. The dependence of the convergence interval for θ upon the geometry is investigated. Some 2D computations based on a finite element discretization of both global and local problems are presented. [ABSTRACT FROM AUTHOR]

In this paper we examine the conditioning of the matrices resulting from certain conforming pseudospectral approximations. In particular, we consider non-conforming domain decompositions in rectangular domains and the solution of fourth order problems. We investigate the way in which the poor conditioning of these matrices affects the performance, in terms of accuracy, of various direct methods of solution of the resulting systems. We also show how a simple iterative refinement procedure can improve the accuracy of the results obtained with a capacitance technique. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]