Schwarz waveform relaxation methods for parabolic equations in space-frequency domain

Some Schwarz waveform relaxation algorithms based on frequency domain analysis for parabolic equations are proposed and analyzed. In this paper we mainly study an overlapping process with Dirichlet transmission conditions and a non-overlapping process with Robin transmission conditions. The convergence conditions for these algorithms are also obtained by our frequency domain analysis. Numerical experiments are given to illustrate effectiveness of the algorithms.     

A class of parallel two-level nonlinear Schwarz preconditioned inexact Newton algorithms

We propose and test a new class of two-level nonlinear additive Schwarz preconditioned inexact Newton algorithms (ASPIN). The two-level ASPIN combines a local nonlinear additive Schwarz preconditioner and a global linear coarse preconditioner. This approach is more attractive than the two-level method introduced in [X.-C. Cai, D.E. Keyes, L. Marcinkowski, Nonlinear additive Schwarz preconditioners and applications in computational fluid dynamics, Int. J. Numer. Methods Fluids, 40 (2002), 1463-1470], which is nonlinear on both levels. Since the coarse part of the global function evaluation requires only the solution of a linear coarse system rather than a nonlinear coarse system derived from the discretization of original partial differential equations, the overall computational cost is reduced considerably. Our parallel numerical results based on an incompressible lid-driven flow problem show that the new two-level ASPIN is quite scalable with respect to the number of processors and the fine mesh size when the coarse mesh size is fine enough, and in addition the convergence is not sensitive to the Reynolds numbers.     

A parallel polynomial Jacobi–Davidson approach for dissipative acoustic eigenvalue problems

We consider a rational algebraic large sparse eigenvalue problem arising in the discretization of the finite element method for the dissipative acoustic model in the pressure formulation. The presence of nonlinearity due to the frequency-dependent impedance poses a challenge in developing an efficient numerical algorithm for solving such eigenvalue problems. In this article, we reformulate the rational eigenvalue problem as a cubic eigenvalue problem and then solve the resulting cubic eigenvalue problem by a parallel restricted additive Schwarz preconditioned Jacobi–Davidson algorithm (ASPJD). To validate the ASPJD-based eigensolver, we numerically demonstrate the optimal convergence rate of our discretization scheme and show that ASPJD converges successfully to all target eigenvalues. The extraneous root introduced by the problem reformulation does not cause any observed side effect that produces an undesirable oscillatory convergence behavior. By performing intensive numerical experiments, we identify an efficient correction-equation solver, an effective algorithmic parameter setting, and an optimal mesh partitioning. Furthermore, the numerical results suggest that the ASPJD-based eigensolver with an optimal mesh partitioning results in superlinear scalability on a distributed and parallel computing cluster scaling up to 192 processors.     

Convergence analysis of Schwarz methods without overlap for the Helmholtz equation

In this paper, the continuous and discrete optimal transmission conditions for the Schwarz algorithm without overlap for the Helmholtz equation are studied. Since such transmission conditions lead to non-local operators, they are approximated through two different approaches. The first approach, called optimized, consists of an approximation of the optimal continuous transmission conditions with partial differential operators, which are then optimized for efficiency. The second approach, called approximated, is based on pure algebraic operations performed on the optimal discrete transmission conditions. After demonstrating the optimal convergence properties of the Schwarz algorithm new numerical investigations are performed on a wide range of unstructured meshes and arbitrary mesh partitioning with cross points. Numerical results illustrate for the first time the effectiveness, robustness and comparative performance of the optimized and approximated Schwarz methods on a model problem and on industrial problems.     

A parallel multilevel preconditioned iterative pressure Poisson solver for the large-eddy simulation of turbulent flow inside a duct

Turbulent Poiseuille flows inside the square duct are simulated by the large-eddy simulation based on the multilevel Schwarz preconditioned conjugate gradient pressure Poisson solver, which was developed on top of the Portable, Extensible Toolkit for Scientific Computation (PESTc). The impact of the five different matrix reordering techniques for an incomplete LU (ILU) decomposition as a subdomain solver on the overall performance of Schwarz-type preconditioners for the solution of the pressure Poisson equation are studied. The numerical results indicate that ILU of two-level fill-ins with the reverse Cuthill–McKee matrix ordering technique produces the best performance. Further investigation on the parallel performance of different multilevel methods was also conducted for two different problem sizes. It was observed that the computational cost saturates at around six-level for both the problem sizes explored. Also, though the one-level method is better for small problem size, for the larger problem size, the six-level method performs best in terms of scalability and compute time; hence, the benefit of a multilevel method is more obviously.     

Preconditioners for Schwarz relaxation methods applied to differential algebraic equations

In this paper, the authors investigate the ability of Schwarz relaxation (SR) methods to deal with large systems of differential algebraic equations (DAEs) and assess their respective efficiency. Since the number of iterations required to achieve convergence of the classical SR method is strongly related to the number of subdomains and the time step size, two new preconditioning techniques are here developed. A preconditioner based on a correction using the algebraic equations is first introduced and leads to a number of iterations independent on the number of subdomains. A second preconditioner based on a correction using the Schur complement matrix makes the convergence independent on both the number of subdomains and the integration step size. Application on European electricity network is presented to outline the performance, efficiency, and robustness of the proposed preconditioning techniques for the solution of DAEs.     

Optimized Schwarz methods without overlap for highly heterogeneous media

In this paper an original variant of the Schwarz domain decomposition method is introduced for heterogeneous media. This method uses new optimized interface conditions specially designed to take into account the heterogeneity between the sub-domains on each sides of the interfaces. Numerical experiments illustrate the dependency of the proposed method with respect to several parameters, and confirm the robustness and efficiency of this method based on such optimized interface conditions. Several mesh partitions taking into account multiple cross points are considered in these experiments.     

A parallel micro evolutionary algorithm for heterogeneous computing and grid scheduling

This work presents a novel parallel micro evolutionary algorithm for scheduling tasks in distributed heterogeneous computing and grid environments. The scheduling problem in heterogeneous environments is NP-hard, so a significant effort has been made in order to develop an efficient method to provide good schedules in reduced execution times. The parallel micro evolutionary algorithm is implemented using MALLBA, a general-purpose library for combinatorial optimization. Efficient numerical results are reported in the experimental analysis performed on both well-known problem instances and large instances that model medium-sized grid environments. The comparative study of traditional methods and evolutionary algorithms shows that the parallel micro evolutionary algorithm achieves a high problem solving efficacy, outperforming previous results already reported in the related literature, and also showing a good scalability behavior when facing high dimension problem instances.     

Two-Level Non-Overlapping Schwarz Preconditioners for a Discontinuous Galerkin Approximation of the Biharmonic Equation

We present some two-level non-overlapping additive and multiplicative Schwarz methods for a discontinuous Galerkin method for solving the biharmonic equation. We show that the condition numbers of the preconditioned systems are of the order O( H ³/h ³) for the non-overlapping Schwarz methods, where h and H stand for the fine mesh size and the coarse mesh size, respectively. The analysis requires establishing an interpolation result for Sobolev norms and Poincaré–Friedrichs type inequalities for totally discontinuous piecewise polynomial functions. It also requires showing some approximation properties of the multilevel hierarchy of discontinuous Galerkin finite element spaces.This revised version was published online in July 2005 with corrected volume and issue numbers.     

A performance-based parallel loop scheduling on grid environments

The effectiveness of loop self-scheduling schemes has been shown on traditional multiprocessors in the past and computing clusters in the recent years. However, parallel loop scheduling has not been widely applied to computing grids, which are characterized by heterogeneous resources and dynamic environments. In this paper, a performance-based approach, taking the two characteristics above into consideration, is proposed to schedule parallel loop iterations on grid environments. Furthermore, we use a parameter, SWR, to estimate the proportion of the workload which can be scheduled statically, thus alleviating the effect of irregular workloads. Experimental results on a grid testbed show that the proposed approach can reduce the completion time for applications with regular or irregular workloads. Consequently, we claim that parallel loop scheduling can benefit applications on grid environments.     

An overlapping Schwarz method for virtual element discretizations in two dimensions

A new coarse space for domain decomposition methods is presented for nodal elliptic problems in two dimensions. The coarse space is derived from the novel virtual element methods and therefore can accommodate quite irregular polygonal subdomains. It has the advantage with respect to previous studies that no discrete harmonic extensions are required. The virtual element method allows us to handle polygonal meshes and the algorithm can then be used as a preconditioner for linear systems that arise from a discretization with such triangulations. A bound is obtained for the condition number of the preconditioned system by using a two-level overlapping Schwarz algorithm, but the coarse space can also be used for different substructuring methods. This bound is independent of jumps in the coefficient across the interface between the subdomains. Numerical experiments that verify the result are shown, including some with triangular, square, hexagonal and irregular elements and with irregular subdomains obtained by a mesh partitioner.     

A parallel finite element procedure for contact-impact problems

An efficient parallel finite element procedure for contact-impact problems is presented within the framework of explicit finite element analysis with thepenalty method. The procedure concerned includes a parallel Belytschko-Lin-Tsay shell element generation algorithm and a parallel contact-impact algorithm based on the master-slave slideline algorithm. An element-wise domain decomposition strategy and a communication minimization strategy are featured to achieve almost perfect load balancing among processors and to show scalability of the parallel performance. Throughout this work, a prototype code, named GT-PARADYN, is developed on the IBM SP2 to implement the procedure presented, under message-passing paradigm. Some examples are provided to demonstrate the timing results of the algorithms, discussing the accuracy and efficiency of the code.     

Additive Schwarz preconditioners for the h-p version boundary-element approximation to the hypersingular operator in three dimensions

We study different preconditioners for the h-p version of the Galerkin boundary-element method when used to solve hypersingular integral equations of the first kind on a surface in ?³. These integral equations result from Neumann problems for the Laplace and Lamé equations in the exterior of the surface. The preconditioners are of additive Schwarz type (non-overlapping and overlapping). In all cases, we prove that the condition numbers grow at most logarithmically with the degrees of freedom.     

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.     

A modified Chebyshev pseudospectral DD algorithm for the GBH equation

In this paper, a Chebyshev spectral collocation domain decomposition (DD) semi-discretization by using a grid mapping, derived by Kosloff and Tal-Ezer in space is applied to the numerical solution of the generalized Burger’s-Huxley (GBH) equation. To reduce roundoff error in computing derivatives we use the above mentioned grid mapping. In this work, we compose the Chebyshev spectral collocation domain decomposition and Kosloff and Tal-Ezer grid mapping, elaborately. Firstly, the theory of application of the Chebyshev spectral collocation method with grid mapping and DD on the GBH equation is presented. This method yields a system of ordinary differential algebraic equations (DAEs). Secondly, we use a fourth order Runge-Kutta formula for the numerical integration of the system of DAEs. Application of this modified method to the GBH equation show that this method (M-DD) is faster and more accurate than the standard Chebyshev spectral collocation DD (S-DD) method.     

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.     

Optimized Schwarz method without overlap for the gravitational potential equation on cluster of graphics processing unit

Many engineering and scientific problems need to solve boundary value problems for partial differential equations or systems of them. For most cases, to obtain the solution with desired precision and in acceptable time, the only practical way is to harness the power of parallel processing. In this paper, we present some effective applications of parallel processing based on hybrid CPU/GPU domain decomposition method. Within the family of domain decomposition methods, the so-called optimized Schwarz methods have proven to have good convergence behaviour compared to classical Schwarz methods. The price for this feature is the need to transfer more physical information between subdomain interfaces. For solving large systems of linear algebraic equations resulting from the finite element discretization of the subproblem for each subdomain, Krylov method is often a good choice. Since the overall efficiency of such methods depends on effective calculation of sparse matrix–vector product, approaches that use graphics processing unit (GPU) instead of central processing unit (CPU) for such task look very promising. In this paper, we discuss effective implementation of algebraic operations for iterative Krylov methods on GPU. In order to ensure good performance for the non-overlapping Schwarz method, we propose to use optimized conditions obtained by a stochastic technique based on the covariance matrix adaptation evolution strategy. The performance, robustness, and accuracy of the proposed approach are demonstrated for the solution of the gravitational potential equation for the data acquired from the geological survey of Chicxulub crater.     

Differential quadrature domain decomposition method for a class of parabolic equations

In this paper the differential quadrature method (DQM) and the domain decomposition method (DDM) are combined to form the differential quadrature domain decomposition method (DQDDM), in which the boundary reduction technique (BRM) is adopted. The DQDDM is applied to a class of parabolic equations, which have discontinuity in the coefficients of the equation, or weak discontinuity in the initial value condition. Two numerical examples belonging to this class are computed. It is found that the application of this method to the above mentioned problems is seen to lead to accurate results with relatively small computational effort.     

Service-oriented middleware for distributed data mining on the grid

Distribution of data and computation allows for solving larger problems and executing applications that are distributed in nature. The grid is a distributed computing infrastructure that enables coordinated resource sharing within dynamic organizations consisting of individuals, institutions, and resources. The grid extends the distributed and parallel computing paradigms allowing for resource negotiation and dynamical allocation, heterogeneity, open protocols, and services. Grid environments can be used both for compute-intensive tasks and data intensive applications by exploiting their resources, services, and data access mechanisms. Data mining algorithms and knowledge discovery processes are both compute and data intensive, therefore the grid can offer a computing and data management infrastructure for supporting decentralized and parallel data analysis. This paper discusses how grid computing can be used to support distributed data mining. Research activities in grid-based data mining and some challenges in this area are presented along with some promising future directions for developing grid-based distributed data mining.