Let S be a set of n points in D-dimensional space, where D is a constant, and let k be an integer between 1 and ((n)(2)). A new and simpler proof is given of Salowe's theorem, i.e., a sequential algorithm is given...
详细信息
Let S be a set of n points in D-dimensional space, where D is a constant, and let k be an integer between 1 and ((n)(2)). A new and simpler proof is given of Salowe's theorem, i.e., a sequential algorithm is given that computes the k closest pairs in the set S in O(n log n + k) time, using O(n + k) space. The algorithm fits in the algebraic decision tree model and is, therefore, optimal. Salowe's algorithm seems difficult to parallelize. A parallel version of our algorithm is given for the CRCW-PRAM model. This version runs in O((log n)(2) log log n) expected parallel time and has an O(n log n log log n + k) time-processor product. Finally, actual running times are given of an implementation of our sequential algorithm.
The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in diverse applications such as computer vision and motion tracking. In the MAP, the objective is to match tuples of object...
详细信息
The multidimensional assignment problem (MAP) is a combinatorial optimization problem arising in diverse applications such as computer vision and motion tracking. In the MAP, the objective is to match tuples of objects with minimum total cost. Randomized parallel algorithms are proposed to solve MAPs appearing in multi-sensor multi-target applications. A parallel construction heuristic is described, together with some variations, as well as a parallel local search heuristic. Experimental results using the proposed algorithms are discussed. (C) 2003 IMACS. Published by Elsevier B.V. All rights reserved.
Program visualisation can help make an algorithm understandable. Program visualisation is especially challenging in the area of parallel computations where many processors are executing simultaneously algorithms for p...
详细信息
ISBN:
(纸本)0818692065
Program visualisation can help make an algorithm understandable. Program visualisation is especially challenging in the area of parallel computations where many processors are executing simultaneously algorithms for parallel machines take advantage of the simultaneous activity of processors to perform operations very quickly?: As a result, these algorithms can be difficult to understand In this paper we describe a visualisation tool developed specifically for explaining algorithms written for single-instruction, multiple-data (SIMD) computers called torus computers. This tool helps its users to visualise the patterns of activities of the processors in the process of a computation.
parallel algorithms for solving a knapsack problem of size n on PRAM and distributed memory machines are presented. The algorithms are work-efficient in the sense that they achieve optimal speedup with regard to the b...
详细信息
parallel algorithms for solving a knapsack problem of size n on PRAM and distributed memory machines are presented. The algorithms are work-efficient in the sense that they achieve optimal speedup with regard to the best known solution to this problem. Moreover, they match the best current time/memory/processors tradeoffs, while requiring less memory and/or processors. Since the PRAM is considered mainly as a theoretical model, and we want to produce practical algorithms for the knapsack problem, its solution in distributed memory machines is also studied. For the first time in literature, work-efficient parallel algorithms on local memory - message passing architectures - are given. Time bounds for solving the problem on linear arrays, meshes, and hypercubes are proved.
We provide optimal parallel solutions to several shortest path and visibility problems set in triangulated simple polygons. Let P be a triangulated simple polygon with n vertices, preprocessed to support shortest path...
详细信息
We provide optimal parallel solutions to several shortest path and visibility problems set in triangulated simple polygons. Let P be a triangulated simple polygon with n vertices, preprocessed to support shortest path queries. We can find the shortest path tree from any point inside P in O(log n) time using O(n/log n) processors. In the same bounds, we can preprocess P for shooting queries (a query can be answered in O(log n) time by a uniprocessor). Given a set S of m points inside P, we can find an implicit representation of the relative convex hull of S in O(log(nm)) time with O(m) processors. If the relative convex hull has k edges, we can explicitly produce these edges in O(log(nm)) time with O(k/log(nm)) processors. All of these algorithms are deterministic and use the CREW PRAM model.
Some of the most widely used algorithms for two-point boundary value ordinary differential equations, namely, finite-difference and collocation methods and standard multiple shooting, proceed by setting up and solving...
详细信息
Some of the most widely used algorithms for two-point boundary value ordinary differential equations, namely, finite-difference and collocation methods and standard multiple shooting, proceed by setting up and solving a structured system of linear equations. It is well known that the linear system can be set up efficiently in parallel;we show here that a structured orthogonal factorization technique can be used to solve this system, and hence the overall problem, in an efficient, parallel, and stable way.
As a super class of tournament digraphs, Bang-Jensen, Huang and Prisner [4] defined an in-tournament digraph (in-toumament for short) and investigated a number of its nice properties. The in-tournament is a directed g...
详细信息
As a super class of tournament digraphs, Bang-Jensen, Huang and Prisner [4] defined an in-tournament digraph (in-toumament for short) and investigated a number of its nice properties. The in-tournament is a directed graph in which the set of in-neighbors of every vertex induces a tournament digraph. In other words, the presence of arcs (x,z) and (y,z) implies that exactly one of (x,y) or (y,z) exists. In this paper, we propose, for in-tournaments, parallel algorithms for examining the existence of a Hamiltonian path and a Hamiltonian cycle and for constructing them, if they exist.
作者：
SAOUDI, ANIVAT, ML.I.P.N
Université Paris XIII Institut Galilée Av. J. B. Clément Villetaneuse 93400 France L.I.T.P
Université Paris VII 2 Place Jusieu Paris Cedex 05 75251 France
This paper presents efficient and optimal parallel algorithms for multidimensional image template matching on CREW PRAM model. For an Nd image and Md window, we present an optimal (resp. efficient) algorithm which run...
详细信息
A convex hull is one of the most fundamental and interesting geometric constructs ill computational geometry. Considerable research effort has focused on developing algorithms, both in serial and in parallel, for comp...
详细信息
A convex hull is one of the most fundamental and interesting geometric constructs ill computational geometry. Considerable research effort has focused on developing algorithms, both in serial and in parallel, for computing convex hulls. In particular, there are few I problems whose parallel algorithms are so thoroughly studied as convex hull problems. In this paper, we review the convex hull parallel algorithms and their paradigm. We provide a summary of results and introduce several interesting topics including typical techniques, output-size sensitive methods, randomized approaches, and robust algorithms for convex hull problems, with which we may see the highlights of the whole research for parallel algorithms, Most of our discussion uses the PRAM (parallel Random Access Machine) computational model. but still we give a glance at the results of the other parallel computational models such as mesh, mesh-of-trees, hypercube, recofigurable array, and models of coarse grained multicomputers like BSP and LogP.
Determinants has been used intensively in a variety of applications through history. It also influenced many fields of mathematics like linear algebra. Finding the determinants of a squared matrix can be done using a ...
详细信息
ISBN:
(纸本)9781479904624
Determinants has been used intensively in a variety of applications through history. It also influenced many fields of mathematics like linear algebra. Finding the determinants of a squared matrix can be done using a variety of methods, including well-known methods of Leibniz formula and Laplace expansion which calculate the determinant of any NxN matrix in O(n!). However, decomposition methods, such as: LU decomposition, Cholesky decomposition and QR decomposition, have replaced the native methods with a significantly reduced complexity of O(n boolean AND 3). In this paper, we introduce two parallel algorithms for Laplace expansion and LU decomposition. Then, we analyze them and compare them with their perspective sequential algorithms in terms of run time, speed-up and efficiency, where new algorithms provided better results. At maximum, in Laplace expansion, it became 129% faster, whereas in LU Decomposition, it became 44% faster.
暂无评论