Improved Interface Conditions for 2<Emphasis Type="Italic">D</Emphasis> Domain Decomposition with Corners: Numerical Applications

This article deals with a local improvement of domain decomposition methods for 2-dimensional elliptic problems for which either the geometry or the domain decomposition presents conical singularities. After explaining the main results of the theoretical analysis carried out in Chniti et al. (Calcolo 45, 2008), the numerical experiments presented in this article confirm the optimality properties of the new interface conditions.     

A simple and efficient Union–Find–Delete algorithm

The Union–Find data structure for maintaining disjoint sets is one of the best known and widespread data structures, in particular the version with constant-time Union and efficient Find. Recently, the question of how to handle deletions from the structure in an efficient manner has been taken up, first by Kaplan et al. (2002) [2] and subsequently by Alstrup et al. (2005) [1]. The latter work shows that it is possible to implement deletions in constant time, without affecting adversely the asymptotic complexity of other operations, even when this complexity is calculated as a function of the current size of the set.In this note we present a conceptual and technical simplification of the algorithm, which has the same theoretical efficiency, and is probably more attractive in practice.     

Specifications for decidable hybrid games

We introduce STORMED hybrid games (SHG), a generalization of STORMED hybrid systems, Vladimerou et al. (2008) [33], which have natural specifications that allow rich continuous dynamics and various decidable properties. We solve the control problem for SHG using a reduction to bisimulation on finite game graphs. This generalizes to a greater family of games, which includes o-minimal hybrid games, Bouyer et al. (2006) [6]. We also solve the optimal-cost reachability problem for Weighted SHG and prove decidability of WCTL for Weighted STORMED hybrid systems.     

Fast multilevel augmentation methods for nonlinear boundary value problems

We develop a multilevel augmentation method for solving nonlinear boundary value problems. We first describe the multilevel augmentation method for solving nonlinear operator equations of the second kind which has been proposed in our recent paper Chen et al. (2011) [16], and then apply it to solving the nonlinear two-point boundary value problems of second-order differential equations. The theoretical analysis of convergence order and computational complexity are proposed. Finally numerical experiments are presented to confirm the theoretical estimates and illustrate the efficiency of the method.     

Efficient magnetohydrodynamic simulations on distributed multi-GPU systems using a novel GPU Direct–MPI hybrid approach

Modern graphics processing units (GPUs) have been widely utilized in magnetohydrodynamic (MHD) simulations in recent years. Due to the limited memory of a single GPU, distributed multi-GPU systems are needed to be explored for large-scale MHD simulations. However, the data transfer between GPUs bottlenecks the efficiency of the simulations on such systems. In this paper we propose a novel GPU Direct–MPI hybrid approach to address this problem for overall performance enhancement. Our approach consists of two strategies: (1) We exploit GPU Direct 2.0 to speedup the data transfers between multiple GPUs in a single node and reduce the total number of message passing interface (MPI) communications; (2) We design Compute Unified Device Architecture (CUDA) kernels instead of using memory copy to speedup the fragmented data exchange in the three-dimensional (3D) decomposition. 3D decomposition is usually not preferable for distributed multi-GPU systems due to its low efficiency of the fragmented data exchange. Our approach has made a breakthrough to make 3D decomposition available on distributed multi-GPU systems. As a result, it can reduce the memory usage and computation time of each partition of the computational domain. Experiment results show twice the FLOPS comparing to common 2D decomposition MPI-only implementation method. The proposed approach has been developed in an efficient implementation for MHD simulations on distributed multi-GPU systems, called MGPU–MHD code. The code realizes the GPU parallelization of a total variation diminishing (TVD) algorithm for solving the multidimensional ideal MHD equations, extending our work from single GPU computation (Wong et al., 2011) to multiple GPUs. Numerical tests and performance measurements are conducted on the TSUBAME 2.0 supercomputer at the Tokyo Institute of Technology. Our code achieves 2 TFLOPS in double precision for the problem with 1200³ grid points using 216 GPUs.     

High-resolution compact numerical method for the system of 2D quasi-linear elliptic boundary value problems and the solution of normal derivatives on an irrational domain with engineering applications

In this paper, we present a novel approach to attain fourth-order approximate solution of 2D quasi-linear elliptic partial differential equation on an irrational domain. In this approach, we use nine grid points with dissimilar mesh in a single compact cell. We also discuss appropriate fourth-order numerical methods for the solution of the normal derivatives on a dissimilar mesh. The method has been protracted for solving system of quasi-linear elliptic equations. The convergence analysis is discussed to authenticate the proposed numerical approximation. On engineering applications, we solve various test problems, such as linear convection–diffusion equation, Burgers’equation, Poisson equation in singular form, NS equations, bi- and tri-harmonic equations and quasi-linear elliptic equations to show the efficiency and accuracy of the proposed methods. A comprehensive comparative computational experiment shows the accuracy, reliability and credibility of the proposed computational approach.

     

Algorithmic applications of XPCR

An emerging trend in DNA computing consists of the algorithmic analysis of new molecular biology technologies, and in general of more effective tools to tackle computational biology problems. An algorithmic understanding of the interaction between DNA molecules becomes the focus of some research which was initially addressed to solve mathematical problems by processing data within biomolecules. In this paper a novel mechanism of DNA recombination is discussed, that turned out to be a good implementation key to develop new procedures for DNA manipulation (Franco et al., DNA extraction by cross pairing PCR, 2005; Franco et al., DNA recombination by XPCR, 2006; Manca and Franco, Math Biosci 211:282–298, 2008). It is called XPCR as it is a variant of the polymerase chain reaction (PCR), which was a revolution in molecular biology as a technique for cyclic amplification of DNA segments. A few DNA algorithms are proposed, that were experimentally proven in different contexts, such as, mutagenesis (Franco, Biomolecular computing—combinatorial algorithms and laboratory experiments, 2006), multiple concatenation, gene driven DNA extraction (Franco et al., DNA extraction by cross pairing PCR, 2005), and generation of DNA libraries (Franco et al., DNA recombination by XPCR, 2006), and some related ongoing work is outlined.     

Soft sets and soft rings

Molodtsov (1999) introduced the concept of soft sets in [1]. Then, Maji et al. (2003) defined some operations on soft sets in [2]. Akta? and Ça?man (2007) defined the notion of soft groups in [3]. Finally, soft semirings are defined by Feng et al. (2008) in [5]. In this paper, we have introduced initial concepts of soft rings.     

On stability in distribution of stochastic differential delay equations with Markovian switching

This paper provides a new sufficient condition for stability in distribution of stochastic differential delay equations with Markovian switching (SDDEs). It can be considered as an improvement to the result given by Yuan C. et al. in [6].     

Multiobjective mixed symmetric duality involving cones

A pair of multiobjective mixed symmetric dual programs is formulated over arbitrary cones. Weak, strong, converse and self-duality theorems are proved for these programs under K-preinvexity and K-pseudoinvexity assumptions. This mixed symmetric dual formulation unifies the symmetric dual formulations of Suneja et al. (2002) [14] and Khurana (2005) [15].     

Partial order reduction for state/event LTL with application to component-interaction automata

Software systems assembled from a large number of autonomous components become an interesting target for formal verification due to the issue of correct interplay in component interaction. State/event LTL (Chaki et al. (2004, 2005) [1] and [2]) incorporates both states and events to express important properties of component-based software systems.The main contribution of this paper is a partial order reduction technique for verification of state/event LTL properties. The core of the partial order reduction is a novel notion of stuttering equivalence which we call state/event stuttering equivalence. The positive attribute of the equivalence is that it can be resolved with existing methods for partial order reduction. State/event LTL properties are, in general, not preserved under state/event stuttering equivalence. To this end we define a new logic, called weak state/event LTL, which is invariant under the new equivalence.To bring some evidence of the method’s efficiency, we present some of the results obtained by employing the partial order reduction technique within our tool for verification of component-based systems modelled using the formalism of component-interaction automata (Brim et al. (2005) [3]).     

Bounds for the generalized repetition threshold

The notion of the repetition threshold, which is the object of Dejean’s conjecture (1972), was generalized by Ilie et al. (2005) [8] to include the lengths of the avoided words. We give a lower and an upper bound on this generalized repetition threshold.     

On the security of cryptosystem using automorphism groups

A public key cryptosystem using the discrete logarithm problem (DLP) in inner automorphism groups was proposed by Paeng et al. [Advances in Cryptology-Crypto, 2001, pp. 470-485; Preprint, 2001]. We show that there are subexponential time algorithms to solve the DLP in inner automorphism groups of suggested non-abelian groups.     

Further results of recursive evaluation for compound distribution with the severity distribution of mixed type

Yang et al. [J.P. Yang, S.H. Cheng, Q. Wu, Recursive equations for compound distribution with the severity distribution of the mixed type, Science in China Series A 48 (2005) 594-609] investigated a recursive procedure for a kind of compound distributions with the number of claims belonging to (a,b)-family and the severity distribution of the mixed type. In this paper, we extend their results by assuming that the claim number belongs to a larger class. As applications, the excess-of-loss reinsurance treaty is discussed and concrete examples are considered in some detail.     

A cross-layer optimization based integrated routing and grooming algorithm for green multi-granularity transport networks

With the development of IP networks and intelligent optical switch networks, the backbone network tends to be a multi-granularity transport one. In a multi-granularity transport network (MTN), due to the rapid growth of various applications, the scale and complexity of network devices are significantly enhanced. Meanwhile, to deal with bursty IP traffic, the network devices need to provide continuous services along with excessive power consumption. It has attracted wide attention from both academic and industrial communities to build a power-efficient MTN. In this paper, we design an effective node structure for MTN. Considering the power savings on both IP and optical transport layers, we propose a mathematical model to achieve a cross-layer optimization objective for power-efficient MTN. Since this optimization problem is NP-hard (Hasan et al. (2010)  [11]) and heuristic or intelligent optimization algorithms have been successfully applied to solve such kinds of problems in many engineering domains (Huang et al. (2011)  [13], Li et al. (2011)  [17] and Dong et al. (2011)  [5]), a G  reen integrated R$R$outing and Grooming algorithm based on Biogeography-Based Optimization (Simon (2008)  [23]) (GRG_BBO) is also presented. The simulation results demonstrate that, compared with the other BBO based and state-of-the-art power saving approaches, GRG_BBO improves the power savings at a rate between 2%–15% whilst the high-level multi-user QoS (Quality of Services) satisfaction degree (MQSD) is guaranteed. GRG_BBO is therefore an effective technique to build a power-efficient MTN.     

An optimal algorithm for reporting visible rectangles

We consider the following problem as defined by Grove et al. [Internat. J. Comput. Geom. Appl. 9 (1999) 207-217]: Given a set of n isothetic rectangles in 3D space determine the subset of rectangles, that are not completely hidden. We present an optimal algorithm for this problem that runs in O(nlogn) time and O(n) space. Our result is an improvement over the one of Grove et al. by a logarithmic factor in storage and is achieved by using a different approach. An analogous approach gives non-trivial solutions for other kinds of objects too.     

Multilevel augmentation algorithms based on fast collocation methods for solving ill-posed integral equations

This paper continues the theme of the recent work Chen et al. (2008) [18], in which fast collocation methods are introduced for solving ill-posed Fredholm integral equations of the first kind. We develop in this paper multilevel augmentation algorithms, which lead to fast solutions of the discrete equations resulting from fast collocation methods. Regularization parameter choice strategies are given for proposed methods. The theoretical analysis and numerical experiments illustrate the accuracy and efficiency of the algorithm.     

Convergence theorems by a new iteration process for a finite family of nonself asymptotically nonexpansive mappings with errors in Banach spaces

In this paper, we study a new iteration process for a finite family of nonself asymptotically nonexpansive mappings with errors in Banach spaces. We prove some weak and strong convergence theorems for this new iteration process. The results of this paper improve and extend the corresponding results of Chidume et al. (2003) [10], Osilike and Aniagbosor (2000) [3], Schu (1991) [4], Takahashi and Kim (1998) [9], Tian et al. (2007) [18], Wang (2006) [11], Yang (2007) [17] and others.     

The development of the Trefftzian methodology for engineering design analysis

This paper reviews the developments in the Trefftzian Methodology, which have been undertaken by the authors at the University of Sheffield during the past fifteen years and the application of these developments to engineering design analysis. Initially, in the late 1970s, this work concentrated on the Direct Boundary Element Method (DBEM) and the Indirect Boundary Element Method (IBEM). Unfortunately these methods, as they are normally formulated, give rise to singular integrals, which require special mathematical treatment, when the source and field points coincide on the boundary of the component being analysed. These singular integrals can however be eliminated by placing the source boundary outside the domain of the problem being analysed so that the field and source points never coincide. This technique is known as either the Regular Direct Boundary Element Method (RDBEM) or the Regular Indirect Boundary Element Method (RIBEM) In a further development of the RIBEM, based on the Trefftz Method, the continuous distribution of sources is replaced with sources distributed at discrete points on the source boundary. This modified Trefftz Method eliminates the integrations in the solution procedure, it provides a series solution in terms of the fundamental solution of the problem being analysed and is referred to as the Indirect Discrete Boundary Method (IDBM). The emergence of the IDBM provided the opportunity to develop a combined Boundary Element Finite Element technique which enables these methods to be used simultaneously in a single calculation, thereby exploiting their strengths and minimising their weaknesses. A number of case studies will be discussed in the paper to illustrate the developments in the Trefftzian Methodology and its application to engineering design analysis.