Parallel algorithms for relational coarsest partition problems

Relational Coarsest Partition Problems (RCPPs) play a vital role in verifying concurrent systems. It is known that RCPPs are P-complete and hence it may not be possible to design polylog time parallel algorithms for these problems. In this paper, we present two efficient parallel algorithms for RCPP in which its associated label transition system is assumed to have m transitions and n states. The first algorithm runs in O(n^1+ϵ) time using m/n^ϵ CREW PRAM processors, for any fixed ϵ<1. This algorithm is analogous to and optimal with respect to the sequential algorithm of P.C. Kanellakis and S.A. Smolka (1990). The second algorithm runs in O(n log n) time using m/n CREW PRAM processors. This algorithm is analogous to and nearly optimal with respect to the sequential algorithm of R. Paige and R.E. Tarjan (1987)     

Parallel algorithms for shortest path problems in polygons

Given ann-vertex simple polygon we address the following problems: (i) find the shortest path between two pointss andd insideP, and (ii) compute the shortestpath tree between a single points and each vertex ofP (which implicitly represents all the shortest paths). We show how to solve the first problem inO(logn) time usingO(n) processors, and the more general second problem inO(log² n) time usingO(n) processors, and the more general second problem inO(log² n) time usingO(n) processors for any simple polygonP. We assume the CREW RAM shared memory model of computation in which concurrent reads are allowed, but no two processors should attempt to simultaneously write in the same memory location. The algorithms are based on the divide-and-conquer paradigm and are quite different from the known sequential algorithmsResearch supported by the Faculty of Graduate Studies and Research (McGill University) grant 276-07     

Parallel monotone iterative relaxation methods for a class of two-dimensional discrete boundary value problems

A parallel monotone iterative relaxation method for a class of two-dimensional discrete boundary value problems is established, and the sequence of iterations is shown to converge monotonically either from above or below to a solution of the problem. This monotone convergence results yields a parallel computational algorithm as well as an existence-comparison result for the solutions. To compute the sequence of iterations, the Thomas algorithm can be used in the same fashion as for one-dimensional problem. The existence and comparison results of the upper and lower solutions are given. The local as well as global existence-uniqueness of the solution are obtained. The global convergence of the iterations is investigated, and the influence of the parameters on the rate of convergence of the iterations is analyzed. Numerical results are given to corroborate the analytical results.     

Parallel bioinspired algorithms for NP complete graph problems

It is no longer believed that DNA computing will outperform digital computers when it comes to the computation of intractable problems. In this paper, we emphasise the in silico implementation of DNA-inspired algorithms as the only way to compete with other algorithms for solving NP-complete problems. For this, we provide sticker algorithms for some of the most representative NP-complete graph problems. The simple data structures and bit-vertical operations make them suitable for some parallel architectures. The parallel algorithms might solve either moderate-size problems in an exact manner or, when combined with a heuristic, large problems in polynomial time.     

Parallel adaptive solution of 3D boundary value problems by Hessian recovery

A parallel technique for an adaptive solution of 3D boundary value problems is described. It incorporates a parallel mesh generation and a parallel iterative solution of the corresponding discrete problem. Both generation and solution are problem independent and may be considered as black-boxes.     

Numerical treatment for boundary value problems of Pantograph functional differential equation using computational intelligence algorithms

In this study, stochastic computational techniques are developed for the solution of boundary value problems (BVPs) of second order Pantograph functional differential equation (PFDE) using artificial neural networks(ANNs), simulated annealing (SA), pattern search (PS), genetic algorithms (GAs), active-set algorithm (ASA) and their hybrid combinations. The strength of ANNs is exploited to construct a model for PFDE by defining as unsupervised error to approximate the solution. The accuracy of the model is subjected to find the appropriate design parameters of the networks. These optimal weights of the networks are trained using SA, PS and GAs, used as a tool for viable global search, hybridized with ASA for rapid local convergence. The designed schemes are evaluated by solving a numbers of BVPs for the PFDE and comparing with standard results. The reliability and effectiveness of the proposed solvers are investigated through Monte-Carlo simulations and their statistical analysis.     

Parallel black box \mathcal {H}-LU preconditioning for elliptic boundary value problems

Hierarchical ( $\mathcal {H}$ -) matrices provide a data-sparse way to approximate fully populated matrices. The two basic steps in the construction of an $\mathcal {H}$ -matrix are (a) the hierarchical construction of a matrix block partition, and (b) the blockwise approximation of matrix data by low rank matrices. In the context of finite element discretisations of elliptic boundary value problems, $\mathcal {H}$ -matrices can be used for the construction of preconditioners such as approximate $\mathcal {H}$ -LU factors. In this paper, we develop a new black box approach to construct the necessary partition. This new approach is based on the matrix graph of the sparse stiffness matrix and no longer requires geometric data associated with the indices like the standard clustering algorithms. The black box clustering and a subsequent $\mathcal {H}$ -LU factorisation have been implemented in parallel, and we provide numerical results in which the resulting black box $\mathcal {H}$ -LU factorisation is used as a preconditioner in the iterative solution of the discrete (three-dimensional) convection-diffusion equation.     

A numerical method for boundary value problems

This paper demonstrates the utility, generality and simplicity of a computational method of solving systems of ordinary differential equations. The central idea of the method revolves around the ability to generate a numerical approximation of the general solution of systems of linear differential equations. The idea of obtaining a numerical approximation to the general solution leads to changes in the traditional approaches for solving boundary value problems. The method is extended to nonlinear boundary value problems and to boundary value problems with a boundary condition given at infinity. The estimation of unknown parameters in a dynamical system is also treated.     

Polynomial time-marching for nonperiodic boundary value problems

A polynomial interpolation time-marching technique can efficiently provide balanced spectral accuracy in both the space and time dimensions for some PDEs. The Newton-form interpolation based on Fejér points has been successfully implemented to march the periodic Fourier pseudospectral solution in time. In this paper, this spectrally accurate time-stepping technique will be extended to solve some typical nonperiodic initial boundary value problems by the Chebyshev collocation spatial approximation. Both homogeneous Neumann and Dirichlet boundary conditions will be incorporated into the time-marching scheme. For the second order wave equation, besides more accurate timemarching, the new scheme numerically has anO(1/N ²) time step size limitation of stability, much larger thanO(1/N ⁴) stability limitation in conventional finitedifference time-stepping, Chebyshev space collocation methods.     

Three-point boundary value problems for difference equations

In this paper, the existence and nonexistence of positive solutions for three-point nonlinear boundary value problems of difference equations are considered.     

Parallel machine scheduling problems using memetic algorithms

In this paper, we investigate how to apply the hybrid genetic algorithms (the memetic algorithms) to solve the parallel machine scheduling problem. There are two essential issues to be dealt with for all kinds of parallel machine scheduling problems: job partition among machines and job sequence within each machine. The basic idea of the proposed method is that (a) use the genetic algorithms to evolve the job partition and then (b) apply a local optimizer to adjust the job permutation to push each chromosome climb to his local optima. Preliminary computational experiments demonstrate that the hybrid genetic algorithm outperforms the genetic algorithms and the conventional heuristics.     

Anti-periodic fractional boundary value problems

We study a class of anti-periodic boundary value problems of fractional differential equations. Some existence and uniqueness results are obtained by applying some standard fixed point principles. Several examples are given to illustrate the results.     

On fuzzy boundary value problems

The statement that a two-point boundary value problem of fuzzy differential equation is equivalent to a fuzzy integral equation was pointed out by Lakshmikantham et al. and O’Regan et al. Recently Bede gave a counterexample to show that this statement does not hold and he also argued that in many cases two-point boundary value problems have no solutions. Under a new structure and certain conditions we show that a two-point boundary value problem is equivalent to a fuzzy integral equation. We also prove the existence of solutions to the two-point boundary value problem. In some sense, this is an amendment to results of Lakshmikantham et al. and O’Regan et al., and it is an answer to one of Bede’s problems.     

Parallel algorithms for bipartite matching problems on distributed memory computers

We present a new parallel algorithm for computing a maximum cardinality matching in a bipartite graph suitable for distributed memory computers.The presented algorithm is based on the Push-Relabel algorithm which is known to be one of the fastest algorithms for the bipartite matching problem. Previous attempts at developing parallel implementations of it have focused on shared memory computers using only a limited number of processors.We first present a straightforward adaptation of these shared memory algorithms to distributed memory computers. However, this is not a viable approach as it requires too much communication. We then develop our new algorithm by modifying the previous approach through a sequence of steps with the main goal being to reduce the amount of communication and to increase load balance. The first goal is achieved by changing the algorithm so that many push and relabel operations can be performed locally between communication rounds and also by selecting augmenting paths that cross processor boundaries infrequently. To achieve good load balance, we limit the speed at which global relabelings traverse the graph. In several experiments on a large number of instances, we study weak and strong scalability of our algorithm using up to 128 processors.The algorithm can also be used to find ?-approximate matchings quickly.     

Parallel best-first search algorithms for planning problems on multi-core processors

The Journal of Supercomputing - The multiplication of computing cores in modern processor units permits revisiting the design of classical algorithms to improve computational performance in complex...     

A boundary value approach for a class of linear singularly perturbed boundary value problems

A new boundary value technique, which is simple to use and easy to implement, is presented for a class of linear singularly perturbed two-point boundary value problems with a boundary layer at one end (left or right) point of the underlying interval. As with other methods, the original problem is partitioned into inner and outer solution of differential equations. The method is distinguished by the following fact: the inner region problem is solved as a two-point boundary layer correction problem and the outer region problem of the differential equation is solved as initial-value problem with initial condition at end point. Some numerical experiments have been included to demonstrate the applicability of the proposed method.     

Parallel algorithms for the iterative solution of sparse least-squares problems

In this paper, we are concerned with a generalized Gauss-Seidel approach to sparse linear least-squares problems. Two algorithms, related to those given by Schechter (1959), for the solution of linear systems are presented and their parallel implementation is discussed. In these procedures, which can be viewed as an alternative ordering of the variables in the SOR methods, the variables are divided into nondisjoint groups. Numerical results, obtained on CRAY X-MP/48, are presented and discussed.