In present-day parallel computers, the complexity of permuting N data items in shared memory varies, depending on whether large blocks can be used for communication. The Block PRAM model of Aggarwal, Chandra and Snir ...
详细信息
In present-day parallel computers, the complexity of permuting N data items in shared memory varies, depending on whether large blocks can be used for communication. The Block PRAM model of Aggarwal, Chandra and Snir is unique among shared-memory models of parallel computation in modeling this phenomenon. We characterize the Block PRAM complexity of some useful classes of permutations, improving known results.
A new algorithm is presented to improve by a factor of log m the estimates for both parallel and sequential time complexity of division with remainder of two integer polynomials. Under the parallel model, this means B...
详细信息
A new algorithm is presented to improve by a factor of log m the estimates for both parallel and sequential time complexity of division with remainder of two integer polynomials. Under the parallel model, this means Boolean logarithmic time, which is asymptotically optimum. The algorithm exploits the reduction of the problem to integer division; the polynomial remainder and quotient are recovered from integer remainder and quotient via binary segmentation.
Lattice basis reduction is an important problem in geometry of numbers with applications in combinatorial optimization, computer algebra, and cryptography. The well-known sequential LLL algorithm finds a short vector ...
详细信息
Lattice basis reduction is an important problem in geometry of numbers with applications in combinatorial optimization, computer algebra, and cryptography. The well-known sequential LLL algorithm finds a short vector in O(n(4)log B) arithmetic operations on integers having binary length O(nlog B), where n denotes the dimension of the lattice and B denotes the maximum L-2 norm of the initial basis vectors. In this paper a new analysis of the parallel algorithm of Roch and Villard is presented. It is shown that on an n x n mesh it needs O(n 2 log B) arithmetic operations on integers having binary length O(nlog B). This improves the previous analysis and shows that an asymptotical speedup of n(2) is possible using n(2) processors.
We study the parallel implementation of two diagonalization methods for solving dense linear systems: the well known Gauss-Jordan method and a new one introduced by Huard. The number of arithmetic operations performed...
详细信息
We study the parallel implementation of two diagonalization methods for solving dense linear systems: the well known Gauss-Jordan method and a new one introduced by Huard. The number of arithmetic operations performed by the Huard method is the same as for Gaussian elimination, namely 2n3/3, less than for the Jordan method, namelyn3. We introduce parallel versions of these methods, compare their performances and study their complexity. We assume a shared memory computer with a number of processorspof the order ofn, the size of the problem to be solved, We show that the best parallel version for Jordan's method is by rows whereas the best one for Huard's method is by columns. Our main result states that for a small number of processors the parallel Huard method is faster than the parallel Jordan method and slower otherwise. The separation is obtained forp= 0.44n.
An easily implementable recursive parallelization strategy for solving the subset sum problem by the branch-and-bound method is proposed. Two different frontal and balanced variants of this strategy are compared. On a...
详细信息
An easily implementable recursive parallelization strategy for solving the subset sum problem by the branch-and-bound method is proposed. Two different frontal and balanced variants of this strategy are compared. On an example of a particular case of the subset sum problem we show that the balanced variant is more effective than the frontal one. Moreover, we show that, for the considered particular case of the subset sum problem, the balanced variant is also time optimal.
It is not known if planar integer linear programming is P-complete or if it is in NC, and the same can be said about the computation of the remainder sequence of the Euclidean algorithm applied to two integers. Howeve...
详细信息
It is not known if planar integer linear programming is P-complete or if it is in NC, and the same can be said about the computation of the remainder sequence of the Euclidean algorithm applied to two integers. However, both computations are NC equivalent. The latter computational problem was reduced in NC to the former one by Deng [Mathematical Programming: complexity and Application, Ph.D. dissertation, Stanford University, Stanford, CA, 1989;Proc. ACM Symp. on parallel Algorithms and Architectures, 1989, pp. 110-116]. We now prove the converse NC-reduction.
A parallel algorithm for computing the visible portions of a simple polygonal chain with n vertices from a point in the plane is presented. The algorithm runs in O(log n) time using O(n/log n) processors in the EREW-P...
详细信息
A parallel algorithm for computing the visible portions of a simple polygonal chain with n vertices from a point in the plane is presented. The algorithm runs in O(log n) time using O(n/log n) processors in the EREW-PRAM computational model, and hence is asymptotically optimal.
暂无评论