摘要:

We describe a new strategy to solve geometric problems that trades off time × processors in hypercubic networks. LetNbe the size of the input. Using a hypercube of sizeN1+1/κproposeO(κlog N)time solutions for the ECDF searching, closest points, and convex hull problems. Such a strategy, based on the sparse enumeration sort, is of practical interest, since it provides time-optimal parallel algorithms that arc simple and have small constants related to their running times.

ISSN:1063-7192    

DOI:10.1080/10637199408915462

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

In this paper we present a new algorithm for calculating the eigenvalues of a real matrix. The algorithm is based on the orthogonal decomposition of a square dense matrix by theQZmethod proposed in [1]. A comparison with theQRalgorithm confirm the new algorithm to be computationally superior.

ISSN:1063-7192    

DOI:10.1080/10637199408915463

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

We consider a parallel algorithm for minimum weight perfect matching on complete bipartite graphs induced by two disjoint sets of points on the plane. The algorithm is designed for the EREW PRAM or EREW RPRAM model of parallel computation with p (a function of n) processors. For points on the Euclidean plane, the algorithm executes in O(n3/p2+ n2logn+n2.5logn/p) time for p < equation pending We achieve a perfect speedup algorithm when p equation pending

ISSN:1063-7192    

DOI:10.1080/10637199408915464

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

In this paper we propose a block Lanczos algorithm suitable for MIMD distributed memory message passing architectures. It is based on an efficient parallelizaiion of basic linear algebra operations, such as matrix-matrix, sparse matrix-matrix, and dense QR factorization. We assume an unidirectional ring as connection topology and a block column wrap-around matrices distribution. We have chosen this approach to improve load-balancing, to eliminate the intersection of messages and to decrease communication

ISSN:1063-7192    

DOI:10.1080/10637199408915465

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

Hashing techniques have long been used to efficiently store and locate data indexed by key. Recently, parallel hashing algorithms have been developed that allow table insertion of many keys in a few parallel steps/The analyses of these algorithms have focused on the expected number of steps required, ignoring the- issue of work complexity. As a result, these algorithms have not been work efficient. In this paper, represent a parallel hashing algorithm that is shown to be work efficient because it performs no more work than its serial counterpart. An analysis of its behavior shows that it performsS=O(logn) expected parallel steps and W - O(n) expected work

ISSN:1063-7192    

DOI:10.1080/10637199408915466

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

Folding transformations on processor arrays as introduced in [1] result in smaller processor arrays, more work for the processing elements, a decrease in I/O time, pipelineable implementations and circular data flow. Some implementations of folding transformations have been considered by Megson and Evans in [2], Choffrut and Culik in [3], Yaacoby and Cappello [4] and by the authors in [1, 5-7]

ISSN:1063-7192    

DOI:10.1080/10637199408915467

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

Clusters of computers can be used together to provide a powerful computing resource. Large Monte Carlo simulations, such as those used to model particle growth, are computationally intensive and take considerable time to execute on conventional workstations. By spreading the work of the simulation across a cluster of computers, the elapsed execution time can be greatly reduced. Thus a user has apparently the performance of a supercomputer by using the spare cycles on other workstations.

ISSN:1063-7192    

DOI:10.1080/10637199408915468

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

We design a cost-optimal algorithm for managing a parallel heap on an exclusive-read exclusive-write (EREW), parallel random access machine (PRAM) model. We also analyze the time and space complexities of our algorithm, which efficiently employs p processors in the range 1 ≤p≤n, where n is the maximum number of items in the parallel heap. It is assumed that a delete-think-insert cycle is repeatedly performed, and each processor requires an arbitrary but the same amount of time (called the think time) for processing an item which in turn generates at most two new items. The use of a global data structure for each level of the heap helps reduce the working memory space required. The time complexity for deleting p items of the highest priority from the parallel heap is O(logp), while that for inserting at most 2pnew items is O(logn). With or without incorporating the think time, the speedup of our algorithm is shown to be linear, i.e. O(p). Hence this algorithm is an improvement in time over the one proposed by Deo and Prasad [5, 6].

ISSN:1063-7192    

DOI:10.1080/10637199408915469

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

The interior point method (IPM) is now well established as a competitive technique for solving very large scale linear programming problems. The leading variant of the interior point method is the primal dual—predictor corrector algorithm due to Mehrotra. The main computational steps of this algorithm are the repeated calculation and solution of a large sparse positive definite system of equations

ISSN:1063-7192    

DOI:10.1080/10637199408915470

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor

摘要:

We report the results of angular parallelization studies of aSnelectron transport algorithm on a Cray Y-MP 8/864. Three different algorithmic approaches, varying from ordered to chaotic, have been implemented with focus on relative speedup, data locality and process synchronization. In general, chaoticity favors parallelism and the state of maximum concurrency is the state of best performance.

ISSN:1063-7192    

DOI:10.1080/10637199408915471

出版商:Taylor & Francis Group    

年代:1994

数据来源: Taylor