This paper presents a very simple and efficient method for the determination of all cliques of symmetric graphs based on a divide-and-conquer strategy. The given graph is continually broken up into smaller and smaller...
详细信息
This paper presents a very simple and efficient method for the determination of all cliques of symmetric graphs based on a divide-and-conquer strategy. The given graph is continually broken up into smaller and smaller subgraphs in such a way that the cliques can be obtained directly from these subgraphs. This method also leads itself naturally to parallel processing.
In this paper we present a parallel algorithm for the symmetric algebraic eigenvalue problem. The algorithm is based upon a divide and conquer scheme suggested by Cuppen for computing the eigensystem of a symmetric tr...
详细信息
In this paper we present a parallel algorithm for the symmetric algebraic eigenvalue problem. The algorithm is based upon a divide and conquer scheme suggested by Cuppen for computing the eigensystem of a symmetric tridiagonal matrix. We extend this idea to obtain a parallel algorithm that retains a number of active parallel processes that is greater than or equal to the initial number throughout the course of the computation. We give a new deflation technique which together with a robust root finding technique will assure computation of an eigensystem to full accuracy in the residuals and in the orthogonality of eigenvectors. A brief analysis of the numerical properties and sensitivity to round off error is presented to indicate where numerical difficulties may occur. The algorithm is able to exploit parallelism at all levels of the computation and is well suited to a variety of architectures.
The Buneman variant of the block cyclic reduction algorithm begins as a highly parallel algorithm, but collapses with each reduction to a very serial one. Using partial fraction expansions of rational matrix functions...
详细信息
The Buneman variant of the block cyclic reduction algorithm begins as a highly parallel algorithm, but collapses with each reduction to a very serial one. Using partial fraction expansions of rational matrix functions, it is shown how to regain the parallelism. The resulting algorithm using $n^2 $ processors runs in $O(\log ^2 n)$ time.
The solution of large scale integer linear programming models is generally dependent, in some way, upon the branch and bound technique, which can be quite time consuming. This paper describes a parallel branch and bou...
详细信息
The solution of large scale integer linear programming models is generally dependent, in some way, upon the branch and bound technique, which can be quite time consuming. This paper describes a parallel branch and bound algorithm which achieves super linear efficiency in solving integer linear programming models on a multiprocessor computer. The algorithm is used to solve the Haldi and IBM test problems as well as a system design model. [ABSTRACT FROM AUTHOR]
A CRCW PRAM (concurrent-read concurrent-write parallel random access memory) is a machine that is made up of a finite number of processors operating syncronously on common, shared memory cells. Simultaneous reading a...
详细信息
A CRCW PRAM (concurrent-read concurrent-write parallel random access memory) is a machine that is made up of a finite number of processors operating syncronously on common, shared memory cells. Simultaneous reading and simultaneous writing of each memory cell by arbitrary sets of processors is allowed. The literature on parallel computing describes a number of algorithms whose space requirements exceed their time-processor product. An investigation generalizes an idea by Cole and Vishkin (1987) and combines it with a well-known trick for avoiding initialization of memory areas. It is shown that, in the CRCW PRAM model of computation, such anomalies can always be kept within bounds.
We give a parallel implementation of merge sort on a CREW PRAM that uses n processors and O(logn)O(logn)O(\log n) time; the constant in the running time
We give a parallel implementation of merge sort on a CREW PRAM that uses n processors and O(logn) time; the constant in the running time
The theoretical models of computation commonly used to design and analyze algorithms, whether sequential or parallel, usually assume that the word size is fixed and that the entire word is available at once. The purpo...
详细信息
The theoretical models of computation commonly used to design and analyze algorithms, whether sequential or parallel, usually assume that the word size is fixed and that the entire word is available at once. The purpose of this paper is to describe a number of architectures that are specifically designed to handle those situations where the conventional assumptions do not hold, i.e. where words can be arbitrarily long and/or their digits arrive serially. Four problems are considered: computing the sum of n k-bit integers, multiplying two k -bit integers, finding the partial sums of an array of n k -bit integers. Our solutions to these problems are all based on the concept of “on-the-fly” use of the input and intermediate result bits. For each architecture we present, the product of the solution time and the number of logical gates used is an improvement over that of any previously known circuit for the given problem that uses more than a constant number of processors.
We give a parallel method for triangulating a simple polygon by two (parallel) calls to the trapezoidal map computation. The method is simpler and more elegant than previous methods. Along the way we obtain an interes...
详细信息
We give a parallel method for triangulating a simple polygon by two (parallel) calls to the trapezoidal map computation. The method is simpler and more elegant than previous methods. Along the way we obtain an interesting partition of one-sided monotone polygons. Using the best-known trapezoidal map algorithm, ours run in timeO(logn) usingO(n) CREW PRAM processors.
A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the firstn/logn processor,O(logn)-time deterministic EREW PRAM algorithm for expression tree evaluation. ...
详细信息
A new general parallel algorithmic technique for computations on trees is presented. In particular, it provides the firstn/logn processor,O(logn)-time deterministic EREW PRAM algorithm for expression tree evaluation. The technique solves many other tree problems within the same complexity bounds.
The efficient use of MIMD computers calls for a careful choice of adequate algorithms as for an implementation taking into account the particular architecture. To demonstrate these facts, a parallel algorithm to find ...
详细信息
The efficient use of MIMD computers calls for a careful choice of adequate algorithms as for an implementation taking into account the particular architecture. To demonstrate these facts, a parallel algorithm to find an approximate solution to the Euclidean Traveling Salesman Problem (ETSP) is presented. The algorithm is a parallelization of Karp's partitioning algorithm. It is a divide-and-conquer method for solving the ETSP approximately. Since the successor vertex to any vertex in the tour is usually a nearby vertex, the problem can be ‘geographically’ partitioned into subproblems which then can be solved independently. The resulting subtours can be combined into a single tour which is an approximate solution to the ETSP. The algorithm is implemented on a CRAY X-MP with two and four processors, and results using macrotasking and microtasking are presented.
暂无评论