Markov chain Monte Carlo (MCMC) implementations of Bayesian inference for latent spatial Gaussian models are very computationally intensive, and restrictions on storage and computation time are limiting their applicat...
详细信息
Markov chain Monte Carlo (MCMC) implementations of Bayesian inference for latent spatial Gaussian models are very computationally intensive, and restrictions on storage and computation time are limiting their application to large problems. Here we propose various parallel MCMC algorithms for such models. The algorithms' performance is discussed with respect to a simulation study, which demonstrates the increase in speed with which the algorithms explore the posterior distribution as a function of the number of processors. We also discuss how feasible problem size is increased by use of these algorithms.
Given two finite sets of points in a plane, the polygon separation problem is to construct a separating convex k-gon with smallest k. In this paper, we present a parallel algorithm for the polygon separation problem. ...
详细信息
Given two finite sets of points in a plane, the polygon separation problem is to construct a separating convex k-gon with smallest k. In this paper, we present a parallel algorithm for the polygon separation problem. The algorithm runs in O(log n) time on a CREW PRAM with n processors, where n is the number of points in the two given sets. The algorithm is cost-optimal, since OMEGA(n log n) is a lower-bound for the time needed by any sequential algorithm. We apply this algorithm to the problem of finding a convex polygon, with the minimal number of edges, for which a given convex region is its digital image. The algorithm in this paper constructs one such polygon with possibly two more edges than the minimal one.
In this paper, parallel algorithms suitable for the iterative solution of large sets of linear equations are developed. The algorithms based on the well known Gauss Seidel and SOR methods are presented in both synchro...
详细信息
In this paper, parallel algorithms suitable for the iterative solution of large sets of linear equations are developed. The algorithms based on the well known Gauss Seidel and SOR methods are presented in both synchronous and asynchronous forms. Results obtained using the M.I.M.D. computer at Loughborough University are given, for the model problem of the solution of the Laplace equation within the unit square.
Two current problems in the area of graph theory are the problem of finding a minimal spanning tree (MST) in a connected, weighted, undirected graph and the problem of finding the connected components of an undirected...
详细信息
Two current problems in the area of graph theory are the problem of finding a minimal spanning tree (MST) in a connected, weighted, undirected graph and the problem of finding the connected components of an undirected graph. algorithms have been obtained to solve both problems. However, the run time is significantly greater if these algorithms are implemented in a network where read conflicts are not allowed to occur. A new approach is reported which permits the algorithm to run without read conflicts in little more than the time previously required for running in a network where read conflicts were permitted to occur. The new techniques also can be run using a smaller number of processors.
This paper describes two parallel algorithms to test whether a point is inside a digitized closed curve. The first algorithm assumes the curve is stored in a linear array of processors. The second algorithm assumes th...
详细信息
This paper describes two parallel algorithms to test whether a point is inside a digitized closed curve. The first algorithm assumes the curve is stored in a linear array of processors. The second algorithm assumes the digital image containing the curve is stored in a 2-D array of processors and that a clockwise (or counterclockwise) trace of the curve is available (i.e., each point on the curve has a pointer to the next clockwise point). Both algorithms assume that scan instructions are available on the processor array. The algorithms take constant numbers of scan instructions.
Methods for the parallel computation of a multidimensional hypercomplex discrete Fourier transform (HDFT) are considered. The basic idea consists in the application of the properties of the hypercomplex algebra in whi...
详细信息
Efficient parallel algorithms for computing all possible subset regression models are proposed. The algorithms are based on the dropping columns method that generates a regression tree. The properties of the tree are ...
详细信息
Efficient parallel algorithms for computing all possible subset regression models are proposed. The algorithms are based on the dropping columns method that generates a regression tree. The properties of the tree are exploited in order to provide an efficient load balancing which results in no inter-processor communication. Theoretical measures of complexity suggest linear speedup. The parallel algorithms are extended to deal with the general linear and seemingly unrelated regression models. The case where new variables are added to the regression model is also considered. Experimental results on a shared memory machine are presented and analyzed. (C) 2003 Elsevier Science B.V. All rights reserved.
This paper deals with the numerical solution of three-dimensional equilibrium problems in incompressible finite elasticity on parallel computers. The approximation of the underlying variational problems by appropriate...
详细信息
This paper deals with the numerical solution of three-dimensional equilibrium problems in incompressible finite elasticity on parallel computers. The approximation of the underlying variational problems by appropriate finite-element methods is discussed and an augmented Lagrangian formulation of the resulting discrete systems is given. Starting from this formulation, a combination of a simple gradient method and a block relaxation process is used to obtain an algorithm for the complicated nonlinear problems, which can be implemented on parallel computers in a very efficient way. Several results of numerical experiments on an array processor illustrate the capabilities of the considered methods.
In this paper, parallel algorithms are presented for solving some problems on permutation graphs. The coloring problem is solved in O(log2n) time using O(n3/log n) processors on the CREW PRAM, or O(log n) time using O...
详细信息
In this paper, parallel algorithms are presented for solving some problems on permutation graphs. The coloring problem is solved in O(log2n) time using O(n3/log n) processors on the CREW PRAM, or O(log n) time using O(n3) processors on the CRCW PRAM. The weighted clique problem, the weighted independent set problem, the cliques cover problem, and the maximal layers problem are all solved with the same complexities. We can also show that the longest common subsequence problem belongs to the class NC.
暂无评论