Parallel algorithms for boundary value problems

In the present paper we discuss a general approach to solve boundary value problems numerically in a parallel environment. The basic algorithm consists of two steps: the local step, where all the P available processors work in parallel, and the global step, where one processor solves a tridiagonal linear system of the order P. The main advantages of this approach are twofold: First, this suggested approach is very flexible, especially in the local step, and thus the algorithm can be used with any number of processors and with any of the SIMD or MIMD machines. Second, the communication complexity is very small and thus can be used as easily with shared memory machines. Several examples uing this strategy are discussed.     

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 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 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.     

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...     

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.     

Learning automata-based partitioning algorithms for stochastic grouping problems with non-equal partition sizes

Pattern Analysis and Applications - It is very fascinating that the principles of Artificial Intelligence, that were proposed many decades ago, have remained to be the foundations of many of the...     

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 algorithms for arrangements

We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds ofO (logn log^* n) time andn ²/logn processors. We generalize this to obtain anO (logn log^* n)-time algorithm usingn ^d /logn processors for solving the problem ind dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrangement ofn lines on-line, in which each insertion is done in optimalO (logn) time usingn/logn processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.This work was supported by the National Science Foundation, under Grants CCR-8657562 and CCR-8858799, NSF/DARPA under Grant CCR-8907960, and Digital Equipment Corporation. A preliminary version of this paper appeared at the Second Annual ACM Symposium on Parallel Algorithms and Architectures [3].     

VLSI algorithms and architecture for relational operations

The use of a special purpose VLSI chip for relational operations is proposed The chip is structured like a tree with processors at the nodes, called TOP (Tree of Processors). Each node is capable of storing a data element and of performing elementary operations on elements. A table ofn tuples ofk elements each (e. g., a relation defined as in data base theory) is stored inn subtrees of at leastk nodes each, at the lowest levels of TOP. The upper portion of TOP is used for routing and bookkeeping purposes. A number of elementary operations are defined for the nodes, and high level operations on tables are performed as combinations of the former ones. In particular, some operations for data input/output and update are discussed, and the basic operations of UNION, DIFFERENCE, PROJECTION, PRODUCT, SELECTION, and JOIN, defined in relational algebra, are studied for TOP realization. Even the most complex operations are executed inO (kn) steps, that is the size of data. This result is optimal in our system, where we assume that data are transmitted to TOP's through channels of constan bandwidth. Dedicated to Professor S. Faedo on his 70th birthday This research has been partially supported by Ministero della Pubblica Istruzione of Italy.     

Low-complexity fuzzy relational clustering algorithms for Webmining

This paper presents new algorithms-fuzzy c-medoids (FCMdd) and robust fuzzy c-medoids (RFCMdd)-for fuzzy clustering of relational data. The objective functions are based on selecting c representative objects (medoids) from the data set in such a way that the total fuzzy dissimilarity within each cluster is minimized. A comparison of FCMdd with the well-known relational fuzzy c-means algorithm (RFCM) shows that FCMdd is more efficient. We present several applications of these algorithms to Web mining, including Web document clustering, snippet clustering, and Web access log analysis     

关系决策系统的分布约简

基于分辨矩阵和最近已提出的快速算法,对关系系统的约简算法和关系决策系统的分布约简算法进行了研究。证明当决策属性具有自反性时,关系决策系统的分布约简实际上就是关系系统的约简,与决策属性无关。此外,区间值模糊序关系决策系统可视为关系决策系统的一个特例,用提出的关系决策系统的分布约简算法即可获得区间值模糊序关系决策系统的全部约简结果,从而简化了原来的约简算法。     

Parallel join for IBGF partitioned relational databases

This study is concerned with a parallel join operation where the subject relations are partitioned according to an interpolation based grid file (IBGF) scheme. The partitioned relations and directories are distributed over a set of independently accessible external storage units, together with the partitioning control data. The join algorithms executed by a mesh type parallel computing system allow handling of uniform as well as nonuniformly partitioned relations. Each processor locates and retrieves the data partitions it is to join at each step of the join process, in synchronisation with other processors. The approach is found to be feasible as the speedup and efficiency results found by simulation are consistent with theoretical bounds. The algorithms are tuned to join-key distributions, so that effective load balancing is achieved during the actual join. © 1997 John Wiley & Sons, Ltd.     

Parallel algorithms for tree traversals

Three commonly used traversal methods for binary trees (forsets) are pre-order, in-order and post-order. It is well known that sequential algorithms for these traversals takes order O(N) time where N is the total number of nodes. This paper establishes a one-to-one correspondence between the set of nodes that possess right sibling and the set of leaf nodes for any forest. For the case of pre-order traversal, this result is shown to provide an alternate characterization that leads to a simple and elegant parallel algorithm of time complexity O(log N) with or without read-conflicts on an N processor SIMD shared memory model, where N is the total number of nodes in a forest.     

Parallel algorithms for line generation

A new, parallel approach for generating Bresenham-type lines is developed. Coordinate pairs which approximate straight lines on a square grid are derived from line equations. These pairs serve as a basis for the development of four new parallel algorithms. One of the algorithms uses the fact that straight time generation is equivalent to a vector prefix sums calculation. The algorithms execute on a binary tree of processors. Each node in the tree performs a simple calculation that involves only additions and shifts. All four algorithms have time complexityO(log₂ n) wheren in the form 2 ^m denotes the number of points generated andn-1 is the number of processors in the tree. This compares toO(n) for Bresenham's algorithm executed on a sequential processor. Pipelining can be used to achieve a constant time per line generation as long as line length is less thann.     

Parallel algorithms for corner stitching

Corner stitching is the underlying data structure that is used to represent rectangular objects in interactive VLSI layout editing systems such as Magic and Tailor. In this paper we develop efficient algorithms for basic corner stitching operations under the message-passing paradigm. These algorithms were implemented using C and PVM on a distributed network composed of SUN workstations. Experimental results show that significant speed-ups were obtained. © 1998 John Wiley & Sons, Ltd.