Search

In this paper we consider a multigrid approach for solving elliptic equations over non‐matching grids with domain decomposition methods. The domain is partitioned into subdomains with different mesh levels that do not match at the interface. The proposed algorithm searches for the global solution over different levels by projecting the residuals on the overlap region. This method is used in conjunction with a domain decomposition solver which only requires, in each iteration step, the solutions of several small local subproblems over finite element blocks. This algorithm is shown to converge to the solution of the corresponding Lagrange multiplier problem for non‐matching grids. The convergence properties of the algorithms are analyzed and numerical examples are presented. When the multigrid and domain decomposition approaches are combined, the method is shown to be reliable and easy to implement. Furthermore the local nature of the solver allows for a straightforward implementation on multiple parallel computers and graphics processing unit (GPU) clusters. [ABSTRACT FROM AUTHOR]

In this paper, a conserved domain decomposition method for solving convection–diffusion equations with variable coefficients is analyzed. The interface fluxes over the subdomains are firstly obtained by the explicit fluxes scheme. Secondly, the interior solutions and fluxes over each subdomains are computed by the modified upwind implicit scheme. Then, the interface fluxes are corrected by the obtained solutions. We prove rigorously that our scheme is mass conservative, unconditionally stable, and of second‐order convergence in spatial step. Numerical examples test the theoretical analysis and efficiencies. Lastly, we extend our scheme to the nonlinear convection–diffusion equations and give the error estimate. [ABSTRACT FROM AUTHOR]

Principal component analysis (PCA) is widely used for dimensionality reduction and unsupervised learning. The reconstruction error is sometimes large even when a large number of eigenmode is used. In this paper, we show that this unexpected error source is the pollution effect of a summation operation in the objective function of the PCA algorithm. The summation operator brings together unrelated parts of the data into the same optimization and the result is the reduction of the accuracy of the overall algorithm. We introduce a domain decomposed PCA that improves the accuracy, and surprisingly also increases the parallelism of the algorithm. To demonstrate the accuracy and parallel efficiency of the proposed algorithm, we consider three applications including a face recognition problem, a brain tumor detection problem using two‐ and three‐dimensional MRI images. [ABSTRACT FROM AUTHOR]

Summary: This paper discusses techniques for computing a few selected eigenvalue–eigenvector pairs of large and sparse symmetric matrices. A recently developed class of techniques to solve this type of problems is based on integrating the matrix resolvent operator along a complex contour that encloses the interval containing the eigenvalues of interest. This paper considers such contour integration techniques from a domain decomposition viewpoint and proposes two schemes. The first scheme can be seen as an extension of domain decomposition linear system solvers in the framework of contour integration methods for eigenvalue problems, such as FEAST. The second scheme focuses on integrating the resolvent operator primarily along the interface region defined by adjacent subdomains. A parallel implementation of the proposed schemes is described, and results on distributed computing environments are reported. These results show that domain decomposition approaches can lead to reduced run times and improved scalability. [ABSTRACT FROM AUTHOR]

In this paper, the unconditional stability and mass‐preserving splitting domain decomposition method (S‐DDM) for solving three‐dimensional parabolic equations is analyzed. At each time step level, three steps (x‐direction, y‐direction, and z‐direction) are proposed to compute the solutions on each sub‐domains. The interface fluxes are first predicted by the semi‐implicit flux schemes. Second, the interior solutions and fluxes are computed by the splitting implicit solution and flux coupled schemes. Last, we recompute the interface fluxes by the explicit schemes. Due to the introduced z‐directional splitting and domain decomposition, the analysis of stability and convergence is scarcely evident and quite difficult. By some mathematical technique and auxiliary lemmas, we prove strictly our scheme meet unconditional stability and give the error estimates in L2‐norm. Numerical experiments are presented to illustrate the theoretical analysis. [ABSTRACT FROM AUTHOR]

We present in this paper an efficient parallelization approach of the finite element domain decomposition method (FEM‐DDM) for solving large‐scale 3D scattering problems with over ten billion unknowns. In this parallel FEM‐DDM, the whole solution domain is decomposed in a two‐level hierarchical way to minimize the inter process communication. A communication‐avoided block diagonal symmetric Gauss‐Seidel (BD‐SGS) preconditioner is specially designed to accelerate the iterative solution of the interface problem from FEM‐DDM and reduce the CPU time, as well as the peak memory. Besides, a communication strategy is carefully designed to make computation and communication overlapped via nonblocking sending and receiving to further improve the parallel scalability. Numerical examples are presented to demonstrate the accuracy, scalability, and capability of the proposed parallel FEM‐DDM algorithm. The solutions of scattering by a practical aircraft model with a three‐layer antenna radome on its nose section is presented, which are discretized with more than ten billion unknowns. To the best of our knowledge, this is the largest number of unknowns solved by parallel FEM‐DDM in computational electromagnetics to date, for this type of simulation. [ABSTRACT FROM AUTHOR]

In this paper, we propose a composite Laguerre spectral method for the nonlinear Fokker-Planck equations modelling the relaxation of fermion and boson gases. A composite Laguerre spectral scheme is constructed. Its convergence is proved. Numerical results show the efficiency of this approach and coincide well with theoretical analysis. Some results on the Laguerre approximation and techniques used in this paper are also applicable to other nonlinear problems on the whole line. Copyright © 2016 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

A nonlinear coupled mathematical system of two‐phase seepage flow displacement is discussed in this paper including an elliptic equation for the pressure and a convection‐dominated diffusion equation for the saturation. In fact, the boundary of an underground region where the fluid flows through is nonstationary. So a moving boundary should be considered. The saturation equation is convection‐dominated, therefore the method of upwind finite difference is introduced for the accurate computation. The upwind approximation could eliminate numerical oscillation and strong stability is shown. Since the computational work of saturation is larger than the pressure, the authors apply a parallel method, decomposing the whole domain into several nonoverlapping subdomains, to simplify the computation. A domain decomposition method coupled with upwind differences is presented for the saturation. The pressure equation is discretized by a five‐point center finite difference method. By using a transformation and defining new inner products and norms, error estimates in l2 norm is discussed. Finally, two experimental tests are given to illustrate the efficiency and accuracy of the parallel algorithm. [ABSTRACT FROM AUTHOR]

The accurate prediction of transmural stresses in arterial walls requires on the one hand robust and efficient numerical schemes for the solution of boundary value problems including fluid-structure interactions and on the other hand the use of a material model for the vessel wall that is able to capture the relevant features of the material behavior. One of the main contributions of this paper is the application of a highly nonlinear, polyconvex anisotropic structural model for the solid in the context of fluid-structure interaction, together with a suitable discretization. Additionally, the influence of viscoelasticity is investigated. The fluid-structure interaction problem is solved using a monolithic approach; that is, the nonlinear system is solved (after time and space discretizations) as a whole without splitting among its components. The linearized block systems are solved iteratively using parallel domain decomposition preconditioners. A simple - but nonsymmetric - curved geometry is proposed that is demonstrated to be suitable as a benchmark testbed for fluid-structure interaction simulations in biomechanics where nonlinear structural models are used. Based on the curved benchmark geometry, the influence of different material models, spatial discretizations, and meshes of varying refinement is investigated. It turns out that often-used standard displacement elements with linear shape functions are not sufficient to provide good approximations of the arterial wall stresses, whereas for standard displacement elements or F-bar formulations with quadratic shape functions, suitable results are obtained. For the time discretization, a second-order backward differentiation formula scheme is used. It is shown that the curved geometry enables the analysis of non-rotationally symmetric distributions of the mechanical fields. For instance, the maximal shear stresses in the fluid-structure interface are found to be higher in the inner curve that corresponds to clinical observations indicating a high plaque nucleation probability at such locations. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

By using the natural boundary reduction an overlapping domain decomposition method is designed to solve some exterior two-dimensional time-dependent parabolic problems. The governing equation is first discretized in time, leading to a sequence of boundary value problems with respect to time step in an unbounded domain. Then artificial boundaries are introduced. For each time level, an overlapping domain decomposition method, which is based on the natural boundary reduction, is constructed to solve the exterior elliptic boundary value problem on a two-dimensional domain. It is shown that the algorithm is equivalent to Schwarz alternating method. The convergence of this algorithm is given. The contraction factor for the exterior circular domain is also discussed. In the end of this paper, some numerical examples are presented, which illustrate the feasibility and the effectiveness of the proposed methods in this paper. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper introduces a robust preconditioner for general sparse matrices based on low-rank approximations of the Schur complement in a Domain Decomposition framework. In this 'Schur Low Rank' preconditioning approach, the coefficient matrix is first decoupled by a graph partitioner, and then a low-rank correction is exploited to compute an approximate inverse of the Schur complement associated with the interface unknowns. The method avoids explicit formation of the Schur complement. We show the feasibility of this strategy for a model problem and conduct a detailed spectral analysis for the relation between the low-rank correction and the quality of the preconditioner. We first introduce the SLR preconditioner for symmetric positive definite matrices and symmetric indefinite matrices if the interface matrices are symmetric positive definite. Extensions to general symmetric indefinite matrices as well as to nonsymmetric matrices are also discussed. Numerical experiments on general matrices illustrate the robustness and efficiency of the proposed approach. [ABSTRACT FROM AUTHOR]

This special issue contains papers from the Thirteenth Copper Mountain Conference on Multigrid Methods, held in the Colorado Rocky Mountains on March 19–23, 2007, co-chaired by Van Henson and Joel Dendy. The papers address a variety of applications and cover a breadth of topics, ranging from theory to high-performance computing. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

SUMMARY Arterial walls in the healthy physiological regime are characterized by quasi-incompressible, anisotropic, hyperelastic material behavior. Polyconvex material functions representing such materials typically incorporate a penalty function to account for the incompressibility. Unfortunately, the penalty will affect the conditioning of the stiffness matrices. For high penalty parameters, the performance of iterative solvers will degrade, and when direct solvers are used, the quality of the solutions will deteriorate. In this paper, an augmented Lagrange approach is used to cope with the quasi-incompressibility condition. Here, the penalty parameter can be chosen much smaller, and as a consequence, the arising linear systems of equations have better properties. An improved convergence is then observed for the finite element tearing and interconnecting-dual primal domain decomposition method, which is used as an iterative solver. Numerical results for an arterial geometry obtained from ultrasound imaging are presented. Copyright © 2012 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Estimations for the values on interface lines are necessary in a domain decomposition method. However, the accuracy of the estimations is of the first order for most of unconditionally stable domain decomposition schemes. In this paper, a second order of accuracy for the estimations on interface lines is presented. With the new scheme, the optimal number of decomposed subdomains has been observed and proposed. Moreover when the SOR iterative method is used, the optimal over-relaxation parameter is also studied. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

When solving parabolic partial differential equations using finite difference non-overlapping domain decomposition methods, one often uses the stripwise decomposition of spatial domain and it can be extended to the rectangular decomposition without further analysis. In this paper, we analyze the rectangular decomposition when the modified implicit prediction (MIP) algorithm is used. We show that the performance of the rectangular decomposition and the stripwise decomposition is different. We compare spectral radius, maximum error, efficiency, and total operations of the rectangular and the stripwise decompositions. We investigate the accuracy of the interface of the rectangular decomposition and the effects of the correction phase of the rectangular decomposition. Numerical experiments have been done in both two and three spatial dimensions and show that the rectangular decomposition is not better than the stripwise decomposition. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, a new numerical scheme based on non-overlapping domain decompositions and integrated Chebyshev approximations for solving elliptic differential equations (DEs) is presented. The distinguishing feature of the present scheme is that it achieves a Cp continuous solution across the interfaces (p is the order of the DE). Several test problems are employed to verify the method. The obtained results indicate that the achievement of higher-order smoothness leads to a significant improvement in accuracy. Copyright © 2007 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper provides a proof of the robustness of the overlapping domain decomposition preconditioners for the linear finite element approximation of second-order elliptic boundary value problems with strongly discontinuous coefficients. By analyzing the eigenvalue distribution of the domain decomposition preconditioned system, we prove that only a small number of eigenvalues may deteriorate with respect to the discontinuous jump or mesh size, and all the other eigenvalues are bounded below and above nearly uniformly with respect to the jump and mesh size. As a result, we prove that the convergence rate of the preconditioned conjugate gradient methods is nearly uniform with respect to the large jump and mesh size. Copyright © 2008 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, we present a novel domain decomposition finite-difference time domain technique for solving large electromagnetic radiation and scattering problems. In this method the computational domain is divided into manageable, moderate-sized subdomains with overlapping regions. PML layers are used for terminating the subdomains to absorb the outgoing waves. The tangential electric fields are stored on an interface plane to be used as a boundary condition to generate the field in the adjacent subdomain. These computations are applied in a serial manner to solve a problem that is too large to be solved in one step because of limitations in the available computational resources. © 2006 Wiley Periodicals, Inc. Microwave Opt Technol Lett 48: 2399–2405, 2006; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/mop.21962 [ABSTRACT FROM AUTHOR]

In this paper, we consider domain decomposition preconditioners for a system of linear algebraic equations arising from the p-version of the FEM. We analyse several multi-level preconditioners for the Dirichlet problems in the sub-domains in two and three dimensions. It is proved that the condition number of the preconditioned system is bounded by a constant independent of the polynomial degree. Relations between the p-version of the FEM and the h-version are helpful in the interpretations of the results. Copyright © 2006 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper presents an application of the additive Schwarz method to large scale Poisson problems on parallel computers. Domain decomposition in rectangular blocks with matching grids on a structured rectangular mesh has been used together with a stepwise approximation to approximate sloping sides and complicated geometric features. A seven-point stencil based on central difference scheme has been used for the discretization of the Laplacian for both interior and boundary grid points, and this results in a symmetric linear algebraic system for any type of boundary conditions. The preconditioned conjugate gradient method has been used as an accelerator for the additive Schwarz method, and three different methods have been assessed for the solution of subdomain problems. Numerical experiments have been performed to determine the most suitable set of subdomain solvers and the optimal accuracy of subdomain solutions; to assess the effect of different decompositions of the problem domain; and to evaluate the parallel performance of the additive Schwarz preconditioner. Application to a practical problem involving complicated geometry is presented which establishes the efficiency and robustness of the method. Copyright © 2004 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper, a method is presented for analyzing very large finite arrays of tapered-slot antenna elements. The Toeplitz matrix property of regularly spaced arrays, combined with a parametrically truncated coupling radius, generates fixed matrix storage based on the coupling radius rather than array size, thus allowing very large problem analysis. © 2003 Wiley Periodicals, Inc. Microwave Opt Technol Lett 38: 323–328, 2003; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/mop.11050 [ABSTRACT FROM AUTHOR]

This paper extends the relationship between the author's operator trigonometry and convergence rates and other properties of important iterative methods. A new interesting trigonometric preconditioning lemma is given. The general relationship between domain decomposition methods and the operator trigonometry is established. A new basic conceptual link between sparse approximate inverse algorithms and the operator trigonometry is observed. A new underlying fundamental inherent trigonometry of the classical successive over-relaxation scheme is exposed. Some improved trigonometric interpretations of minimum residual schemes are mentioned. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Additive Schwarz preconditioned GMRES is a powerful method for solving large sparse linear systems of equations on parallel computers. The algorithm is often implemented in the Euclidean norm, or the discrete l2 norm, however, the optimal convergence result is available only in the energy norm (or the equivalent Sobolev H1 norm). Very little progress has been made in the theoretical understanding of the l2 behaviour of this very successful algorithm. To add to the difficulty in developing a full l2 theory, in this note, we construct explicit examples and show that the optimal convergence of additive Schwarz preconditioned GMRES in l2 cannot be obtained using the existing GMRES theory. More precisely speaking, we show that the symmetric part of the preconditioned matrix, which plays a role in the Eisenstat–Elman–Schultz theory, has at least one negative eigenvalue, and we show that the condition number of the best possible eigenmatrix that diagonalizes the preconditioned matrix, key to the Saad–Schultz theory, is bounded from both above and below by constants multiplied by h-1/2. Here h is the finite element mesh size. The results presented in this paper are mostly negative, but we believe that the techniques used in our proofs may have wide applications in the further development of the l2 convergence theory and in other areas of domain decomposition methods. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Domain decomposition methods for Laplace's equation are investigated in the present paper. An optimization approach is adopted to satisfy the Dirichlet and/or Neumann interface conditions. The adjoint variable method is used to find the sensitivity of the objective function of optimization. The boundary element method is utilized for the discretization of the primary and adjoint problems. Two example problems are studied with the proposed solution method. Comparisons are also provided by using two other techniques, namely the Uzawa and Schwarz methods, already available in the literature. It is also suggested that a parallel implementation of the method could be performed leading to computational efficiency. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

In this paper an efficient method is developed for decomposition of finite element meshes. The present method is based on concepts from algebraic graph theory and consists of an efficient algorithm to calculate the Fiedler vector of the Laplacian matrix of a graph. The problem of finding the second eigenvalue of the Laplacian matrix is converted into that of evaluating the maximal eigenvalue of the complementary Laplacian matrix. The corresponding eigenvector is constructed by a simple iterative method and applied to graph partitioning. An appropriate transformation maps the graph partitioning into that of domain decomposition of the corresponding finite element mesh. Copyright © 2000 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper shows the ability of a domain decomposition method with a Neumann-Neumann preconditioner to solve industrial and biomechanical problems. For a mid-size biomedical simulation involving soft tissues the results obtained by using this algorithm are comapred to those obtained by more classical methods. The present algorithm thus appears to be more reliable than standard iterative methods and more efficient than a direct method. Copyright © 1999 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Domain decomposition methods for finite element problems using a partition based on the underlying finite element mesh have been extensively studied, in this paper, we discuss algebraic extensions of the class of overlapping domain decomposition algorithms for general sparse matrices. The subproblems are created with an overlapping partition of the graph corresponding to the sparsity structure of the matrix. These algebraic domain decomposition methods are especially useful for unstructured mesh problems. We also discuss some difficulties encountered in the algebraic extension, particularly the issues related to the coarse solver. [ABSTRACT FROM AUTHOR]

In this paper a method for fast computations with the inverse to weakly singular, hypersingular and double layer potential boundary integral operators associated with the Laplacian on Lipschitz domains is proposed and analyzed. It is based on the representation formulae suggested for above-mentioned boundary operators in terms of the Poincaré­Stcklov interface mappings generated by the special decompositions of the interior and exterior domains. Computations with the discrete counterparts of these formulae can he efficiently performed by iterative substructuring algorithms provided some asymptotically optimal techniques for treatment of interface operators on subdomain boundaries. For both two- and three-dimensional cases the computation cost and memory needs arc of the order O(N IogP N) and O(N log2 N), respectively, with 1 ≤ p ≤ 3, where N is the number of degrees of freedom on the boundary under consideration (some kinds of polygons and polyhedra). The proposed algorithms are well suited for serial and parallel computations. [ABSTRACT FROM AUTHOR]

This paper presents a general method to associate the operator splitting for the Peaceman-Rachford procedure with a decomposition of the domain in problems arising from finite element discretization of partial differential equations. The algorithm is provably convergent without any symmetry requirement. Moreover, this method possesses the significant advantage of making the linear systems of the Peaceman-Rachford iteration block diagonal and therefore perfectly appropriate for parallel processing. Not only is sparsity not affected but a reduction of the bandwidth occurs. In fact, for appropriate choices of nonconforming finite element spaces, this method makes directly possible elementwise processing. This option remains available in general for higher-dimensional problems by applying the splitting algorithm recursively. Practical implementation requires nothing more than the standard finite element assembly procedure and some bookkeeping to relate a few different orderings of the nodes. In addition to all these attractive features, the method is rapidly convergent and remains highly competitive even when used on a serial machine. [ABSTRACT FROM AUTHOR]

Computational fluid dynamics (CFD) is increasingly used to study blood flows in patient‐specific arteries for understanding certain cardiovascular diseases. The techniques work quite well for relatively simple problems but need improvements when the problems become harder when (a) the geometry becomes complex (eg, a few branches to a full pulmonary artery), (b) the model becomes more complex (eg, fluid‐only to coupled fluid‐structure interaction), (c) both the fluid and wall models become highly nonlinear, and (d) the computer on which we run the simulation is a supercomputer with tens of thousands of processor cores. To push the limit of CFD in all four fronts, in this paper, we develop and study a highly parallel algorithm for solving a monolithically coupled fluid‐structure system for the modeling of the interaction of the blood flow and the arterial wall. As a case study, we consider a patient‐specific, full size pulmonary artery obtained from computed tomography (CT) images, with an artificially added layer of wall with a fixed thickness. The fluid is modeled with a system of incompressible Navier‐Stokes equations, and the wall is modeled by a geometrically nonlinear elasticity equation. As far as we know, this is the first time the unsteady blood flow in a full pulmonary artery is simulated without assuming a rigid wall. The proposed numerical algorithm and software scale well beyond 10 000 processor cores on a supercomputer for solving the fluid‐structure interaction problem discretized with a stabilized finite element method in space and an implicit scheme in time involving hundreds of millions of unknowns. [ABSTRACT FROM AUTHOR]

Summary: Domain decomposition methods can be solved in various ways. In this paper, domain decomposition in strips is used. It is demonstrated that a special version of the Schwarz alternating iteration method coupled with coarse–fine‐mesh stabilization leads to a very efficient solver, which is easy to implement and has a behavior nearly independent of mesh and problem parameters. The novelty of the method is the use of alternating iterations between odd‐ and even‐numbered subdomains and the replacement of the commonly used coarse‐mesh stabilization method with coarse–fine‐mesh stabilization. [ABSTRACT FROM AUTHOR]

Abstract: Simulation of blood flows in the pulmonary artery provides some insight into certain diseases by examining the relationship between some continuum metrics, eg, the wall shear stress acting on the vascular endothelium, which responds to flow‐induced mechanical forces by releasing vasodilators/constrictors. V. Kheyfets, in his previous work, studies numerically a patient‐specific pulmonary circulation to show that decreasing wall shear stress is correlated with increasing pulmonary vascular impedance. In this paper, we develop a scalable parallel algorithm based on domain decomposition methods to investigate an unsteady model with patient‐specific pulsatile waveforms as the inlet boundary condition. The unsteady model offers tremendously more information about the dynamic behavior of the flow field, but computationally speaking, the simulation is a lot more expensive since a problem which is similar to the steady‐state problem has to be solved many times, and therefore, the traditional sequential approach is not suitable anymore. We show computationally that simulations using the proposed parallel approach with up to 10 000 processor cores can be obtained with much reduced compute time. This makes the technology potentially usable for the routine study of the dynamic behavior of blood flows in the pulmonary artery, in particular, the changes of the blood flows and the wall shear stress in the spatial and temporal dimensions. [ABSTRACT FROM AUTHOR]