检索结果-内蒙古大学图书馆

parallel algorithms FOR FINDING A SUBOPTIMAL FUNDAMENTAL-CYCLE SET IN A GRAPH

parallel COMPUTING 1993年第9期19卷 961-971页

作者： CZECH, ZJ KONOPKA, M MAJEWSKI, BS POLISH ACAD SCI INST COMP SCIPL-44100 GLIWICEPOLAND UNIV QUEENSLAND KEY CTR SOFTWARE TECHNOLDEPT COMP SCIST LUCIAQLD 4072AUSTRALIA

An NP-complete problem of finding a fundamental-cycle set of a graph G with minimum total length is considered. Two parallel algorithms of O(n2/p + n log n log p) and O(m + n2/p + n log(n/p) + n log p) costs to find a suboptimal solution to this problem are presented (p is a number of processors, n is a number of vertices, and m is a number of edges of G). The algorithms partition an edge and vertex set of G among processors, respectively, and use a new heuristic method to solve the problem. A message-based tree-connected MIMD computer is assumed as a model of parallel computations. The algorithms were implemented for a binary tree of 15 transputers, and the experiments were conducted on a wide range of random graphs. The results show that the vertex set partition algorithm with inferior theoretical cost gives better speedups and finds the fundamental-cycle sets of shorter total lengths as compared to the edge set partition algorithm.

关键词： design and analysis of parallel algorithms COMPLEXITY OF parallel COMPUTATIONS DISTRIBUTED MEMORY ARCHITECTURES TRANSPUTER-BASED SYSTEMS

来源：评论

学校读者我要写书评

暂无评论

The exact complexity of projective image matching

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2016年第8期82卷 1360-1387页

作者： Rosenke, Christian Univ Rostock Inst Comp Sci Albert Einstein Str 22 D-18051 Rostock Germany

Projective image matching is an important image processing task. Given digital images A and B, the challenge is to find a projective transformation f for A such that it most closely resembles B. Previous research led to a polynomial time algorithm that elaborately searches the so-called dictionary D(A) of all projective transformations of A using a preprocessed data structure. This paper shows that projective image matching is even TC0-complete by applying a much simpler parallel way of browsing D(A). This reveals further insight into the problem's structural properties and relates it to fundamental computer operations like integer multiplication and division. (C) 2016 Elsevier Inc. All rights reserved.

关键词： Digital image matching Projective transformations Discretization of function spaces Computational geometry design and analysis of parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

BOUNDS ON parallel COMPUTATION OF MULTIVARIATE POLYNOMIALS

BOUNDS ON PARALLEL COMPUTATION OF MULTIVARIATE POLYNOMIALS

引用

ISRAEL SYMP ON THE THEORY OF COMPUTING AND SYSTEMS

作者： SADE, I AVERBUCH, A Department of Computer Science School of Mathematical Sciences Tel Aviv University Tel Aviv 69978 Israel

We consider the problem of fast parallel evaluation of multivariate polynomials over a field F. We define “maximal-degree” (maxdeg) of a multivariate polynomial f as maxi degxi(f(xi,⋯,xn)) i=1,⋯, n. The first lower ... 详细信息

ISBN: (纸本)3540555536

We consider the problem of fast parallel evaluation of multivariate polynomials over a field F. We define “maximal-degree” (max_deg) of a multivariate polynomial f as max_i deg_xi(f(x_i,⋯,x_n)) i=1,⋯, n. The first lower bound result states that if a circut G evaluates a multivariate polynomial f, where its nodes are capable of performing (+,*), then the depth(G) is not less than log₂[max_deg(f)]. This result is a generalization of Kung’s[K] results for a univariate polynomial which is log₂ [deg f]. In the second part, we consider the circuit G which evaluates an arbitrary polynomial f in n variables with max_deg(f)≜d_p>1. We present two algorithms that achieve better performance than the classical results of Hyafil[H] and Valiant et al. [VSBR] for most classes of multivariate polynomials. For the class of” dense” polynomials the results are closed to the theorethical bound log C, where C is the sequential *** algorithms generalize Munro-Paterson[MP] method for the univariate case. It should be noticed that the bound obtained by Hyafil[H] and Valiant, Skyum, Berkowitz and Rackoff[VSBR] is not sufficiently tight for the worst-sequential case (dense multivariate polynomials) and their bound can be reduced by the factor of log d while the number of required processors is only O(C). The best improvement is achieved in a case of a”dense” multivariate polynomial. A polynomial is dense if the computation necessitates Ω(dⁿ_p) sequential steps. The simple algorithm requires only n log d_p+O(n√log d_p) parallel steps The second algorithm has parallel complexity, measured by the depth of the circuit, depth(G) ≤ n(log d_p+β)+log n+√log d_p where β ≤ √log d_p. If C=Ω(dⁿ_p) then it is less than log C+√n log C where C is the number of sequential steps, and it requires only O(C) pr

关键词： Complexity of parallel computation Dense polynomial design and analysis of parallel algorithms Maximal-degree Multivariate polynomials

来源：评论

学校读者我要写书评

暂无评论

Affine Image Matching Is Uniform TC⁰-Complete

Affine Image Matching Is Uniform TC<SUP>0</SUP>-Complete

引用

21st Annual Symposium on Combinatorial Pattern Matching

作者： Hundt, Christian Univ Rostock Inst Informat D-2500 Rostock 1 Germany

ISBN: (纸本)9783642135088

Affine image matching is a computational problem to determine for two given images A and B how much an affine transformated A can resemble B. The research in combinatorial pattern matching led to a polynomial time algorithm which solves this problem by a sophisticated search in the set D(A) of all affine transformations of A. This paper shows that polynomial time is not the lowest complexity class containing this problem by providing its TC0-completeness. This result means not only that there are extremely efficient parallel solutions but also reveals further insight into the structural properties of image matching. The completeness in TC0 relates affine image matching to a number of most basic problems in computer science, like integer multiplication and division.

关键词： digital image matching combinatorial pattern matching design and analysis of parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A work-optimal deterministic algorithm for the certified write-all problem with a nontrivial number of asynchronous processors

引用

SIAM JOURNAL ON COMPUTING 2005年第4期34卷 993-1024页

作者： Malewicz, G Univ Alabama Dept Comp Sci Tuscaloosa AL 35487 USA Argonne Natl Lab Div Math & Comp Sci Argonne IL 60439 USA MIT Supercomp Technol Grp Cambridge MA 02139 USA Univ Connecticut Storrs CT 06269 USA

Martel [ C. Martel, A. Park, and R. Subramonian, SIAM J. Comput., 21 ( 1992), pp. 1070 - 1099] posed a question for developing a work-optimal deterministic asynchronous algorithm for the fundamental load-balancing and synchronization problem called Certified Write-All (CWA). In this problem, introduced in a slightly different form by Kanellakis and Shvartsman in a PODC' 89 paper [ P. C. Kanellakis and A. A. Shvartsman, Distributed Computing, 5 ( 1992), pp. 201 247], p processors must update n memory cells and only then signal the completion of the updates. It is known that solutions to this problem can be used to simulate synchronous parallel programs on asynchronous systems with worst-case guarantees for the overhead of a simulation. Such simulations are interesting because they may increase productivity in parallel computing since synchronous parallel programs are easier to reason about than are asynchronous ones. This paper presents the first solution to the question of Martel, Park, and Subramonian. Specifically, we show a deterministic asynchronous algorithm for the CWA problem. Our algorithm has the work complexity of O( n + p(4) log n). This work complexity is asymptotically optimal for a nontrivial number of processors p <= ( n/ log n)(1/4). In contrast, all known deterministic algorithms require superlinear in n work when p = n(1/r) for any fixed r >= 1. Our algorithm generalizes the collision principle introduced by Buss et al. [ J. Buss, P. C. Kanellakis, P. L. Ragde, and A. A. Shvartsman, J. algorithms, 20 ( 1996), pp. 45 - 86] in 1996, which has not been previously generalized despite various attempts. Each processor maintains a collection of intervals of {1, 2,..., n}. Any processor iteratively selects an interval and works from its tip toward the other tip until it finishes the work or collides with another processor. Collisions are detected effectively using a special Read-Modify-Write operation. In any case, the processor transforms its collection a

关键词： design and analysis of parallel algorithms deterministic algorithms asynchrony certified write-all

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：