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

All-Pairs Shortest Path algorithms for planar graph for GPU-accelerated clusters

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2015年 85卷 91-103页

作者： Djidjev, Hristo Chapuis, Guillaume Andonov, Rumen Thulasidasan, Sunil Lavenier, Dominique Los Alamos Natl Lab Los Alamos NM 87545 USA Los Alamos Natl Lab Informat Sci Grp CCS3 Los Alamos NM USA Los Alamos Natl Lab Computat Sci Div Los Alamos NM USA INRIA IRISA F-35042 Rennes France Univ Rennes 1 F-35042 Rennes France

We present a new approach for solving the All-Pairs Shortest-Path (APSP) problem for planar graphs that exploits the massive on-chip parallelism available in today's Graphics Processing Units (GPUs). We describe two new algorithms based on our approach. Both algorithms use Floyd-Warshall method, have near optimal complexity in terms of the total number of operations, while their matrix-based structure is regular enough to allow for efficient parallel implementation on the GPUs. By applying a divide-and-conquer approach, we are able to make use of multi-node GPU clusters, resulting in more than an order of magnitude speedup over fastest known Dijkstra-based GPU implementation and a two-fold speedup over a parallel Dijkstra-based CPU implementation. (C) 2015 Elsevier Inc. All rights reserved.

关键词： All-pairs shortest path problem Planar graphs GPGPU Parallel computing Floyd-Warshall algorithm Distributed computing algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

Evaluating the quality of online optimization algorithms by discrete event simulation

引用

CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH 2017年第4期25卷 831-858页

作者： Dunke, Fabian Nickel, Stefan Karlsruhe Inst Technol Inst Operat Res Discrete Optimizat & Logist Kaiserstr 12 D-76131 Karlsruhe Germany

A key feature of dynamic problems which offer degrees of freedom to the decision maker is the necessity for a goal-oriented decision making routine which is employed every time the logic of the system requires a decision. In this paper, we look at optimization procedures which appear as subroutines in dynamic problems and show how discrete event simulation can be used to assess the quality of algorithms: after establishing a general link between online optimization and discrete event systems, we address performance measurement in dynamic settings and derive a corresponding tool kit. We then analyze several control strategies using the methodologies discussed previously in two real world examples of discrete event simulation models: a manual order picking system and a pickup and delivery service.

关键词： Online optimization algorithm analysis Discrete event simulation Order picking Pickup and delivery

来源：评论

学校读者我要写书评

暂无评论

acc-Motif: Accelerated Network Motif Detection

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2014年第5期11卷 853-862页

作者： Meira, Luis A. A. Maximo, Vinicius R. Fazenda, Alvaro L. da Conceicao, Arlindo F. Univ Estadual Campinas UNICAMP Sch Technol Campinas SP Brazil Fed Univ Sao Paulo UNIFESP Inst Sci & Technol Sao Jose Dos Campos Brazil

Network motif algorithms have been a topic of research mainly after the 2002-seminal paper from Milo et al. [1], which provided motifs as a way to uncover the basic building blocks of most networks. Motifs have been mainly applied in Bioinformatics, regarding gene regulation networks. Motif detection is based on induced subgraph counting. This paper proposes an algorithm to count subgraphs of size k + 2 based on the set of induced subgraphs of size k. The general technique was applied to detect 3, 4 and 5-sized motifs in directed graphs. Such algorithms have time complexity O(a(G)m), O(m(2)) and O(nm(2)), respectively, where a(G) is the arboricity of G(V, E). The computational experiments in public data sets show that the proposed technique was one order of magnitude faster than Kavosh and FANMOD. When compared to NetMODE, acc-Motif had a slightly improved performance.

关键词： Network motifs algorithm analysis subgraph counting

来源：评论

学校读者我要写书评

暂无评论

A general modeling approach to online optimization with lookahead

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2016年 63卷 134-153页

作者： Dunke, Fabian Nickel, Stefan Karlsruhe Inst Technol Inst Operat Res Karlsruhe Germany

A vast number of real world problems are coined by an information release over time and the related need for repetitive decision making over time. Optimization problems arising in this context are called online since decisions have to be made although not all data is known. Due to technological advances, algorithms may also resort to a limited preview (lookahead) on future events. We first embed the paradigm of online optimization with lookahead into the theory of optimization and develop a concise understanding of lookahead. We further find that the effect of lookahead can be decomposed into an informational and a processual component. Based on analogies to discrete event systems, we then formulate a generic modeling framework for online optimization with lookahead and derive a classification scheme which facilitates a thorough categorization of different lookahead concepts. After an assessment of performance measurement approaches with relevance to practical needs, we conduct a series of computational experiments which illustrate how the general concept of lookahead applies to specific instantiations and how a knowledge pool on lookahead effects in applications can be built up using the general classification scheme. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Online optimization Lookahead Discrete event system algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

An efficient Montgomery exponentiation algorithm by using signed-digit-recoding and folding techniques

引用

APPLIED MATHEMATICS AND COMPUTATION 2007年第1期185卷 31-44页

作者： Lou, Der-Chyuan Lai, Jui-Chang Wu, Chia-Long Chang, Te-Jen Chinese AF Inst Technol Dept Aviat & Commun Electron Kaohsiung 82047 Taiwan Natl Def Univ Chung Cheng Inst Technol Dept Elect Engn Tao Yuan 33509 Taiwan

The motivation for designing fast modular exponentiation algorithms comes from their applications in computer science. In this paper, a new CSD-EF Montgomery binary exponentiation algorithm is proposed. It is based on the Montgomery algorithm using the canonical-signed-digit (CSD) technique and the exponent-folding (EF) binary exponentiation technique. By using the exponent-folding technique of computing the common parts in the folded substrings, the same common part in the folding substrings can be simply computed once. We can thus improve the efficiency of the binary exponentiation algorithm by decreasing the number of modular multiplications. Moreover, the "signed-digit representation" has less occurrence probability of the nonzero digit than binary number representation. Taking this advantage, we can further effectively decrease the amount of modular multiplications and we can therefore decrease the computational complexity of modular exponentiation. As compared with the Ha-Moon's algorithm 1.261718m multiplications and the Lou-Chang's algorithm 1.375m multiplications, the proposed CSD-EF Montgomery algorithm on average only takes 0.5m multiplications to evaluate modular exponentiation, where m is the bit-length of the exponent. (c) 2006 Elsevier Inc. All rights reserved.

关键词： Montgomery algorithm modular exponentiation exponent-folding technique algorithm analysis canonical-signed-digit recoding

来源：评论

学校读者我要写书评

暂无评论

A Lower Bound for the HBC Transversal Hypergraph Generation

引用

FUNDAMENTA INFORMATICAE 2014年第4期130卷 409-414页

作者： Elbassioni, Khaled Hagen, Matthias Rauf, Imran Masdar Inst Sci & Technol Abu Dhabi U Arab Emirates Bauhaus Univ Weimar D-99423 Weimar Germany Natl Univ Comp & Emerging Sci Karachi Pakistan

The computation of transversal hypergraphs in output-polynomial time is a long standing open question. An Apriori-like level-wise approach (referred to as the HBC-algorithm or MTminer) was published in 2007 by Hebert, Bretto, and Cremilleux [A Data Mining Formalization to Improve Hypergraph Minimal Transversal Computation, Fundamenta Informaticae, 80(4), 2007, 415-433] and was experimentally demonstrated to have very good performance on hypergraphs with small transversals. In this short note extending the paper by Hagen [Lower bounds for three algorithms for transversal hypergraph generation, Discrete Applied Mathematics, 157(7), 2009, 1460-1469], we prove a superpolynomial lower bound for the HBC-algorithm. This lower bound also shows that the originally claimed upper bound on the HBC-algorithm's running time is wrong.

关键词： HBC-algorithm MTminer algorithm analysis lower bound transversal hypergraph generation

来源：评论

学校读者我要写书评

暂无评论

Efficient Monte Carlo clustering in subspaces

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2017年第3期52卷 751-772页

作者： Olson, Clark F. Hunn, David C. Lyons, Henry J. Univ Washington Sch Sci Technol Engn & Math Bothell WA 98011 USA Microsoft Corp Redmond WA 98052 USA

Clustering of high-dimensional data is an important problem in many application areas, including image classification, genetic analysis, and collaborative filtering. However, it is common for clusters to form in different subsets of the dimensions. We present a randomized algorithm for subspace and projected clustering that is both simple and efficient. The complexity of the algorithm is linear in the number of data points and low-order polynomial in the number of dimensions. We present the results of a thorough evaluation of the algorithm using the OpenSubspace framework. Our algorithm outperforms competing subspace and projected clustering algorithms on both synthetic and real-world data sets.

关键词： Subspace clustering Projected clustering Monte Carlo algorithm algorithm analysis Classification

来源：评论

学校读者我要写书评

暂无评论

Matrix transpose on meshes with buses

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2016年 96卷 194-201页

作者： Bekesi, Jozsef Galambos, Gabor Univ Szeged Dept Appl Informat Gyula Juhasz Fac Educ Szeged Hungary

In this paper we analyze the matrix transpose problem for 2- and 3-dimensional mesh architectures with row and column buses. First we consider the 2-dimensional problem, and we give a lower bound of approximately 0.45n for the number of steps required by any matrix transpose algorithm on an n x n mesh with buses. Next we present an algorithm which solves this problem in less than 0.5n + 9 steps. Finally, we prove that the given lower bound remains valid for the 3-dimensional case as well. (C) 2016 Elsevier Inc. All rights reserved.

关键词： algorithm analysis Mesh architecture Matrix transpose

来源：评论

学校读者我要写书评

暂无评论

A Low-Rank Approximation for MDPs via Moment Coupling

引用

OPERATIONS RESEARCH 2024年第3期72卷 1255-1277页

作者： Zhang, Amy B. Z. Gurvich, Itai Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA Northwestern Univ Kellogg Sch Management Evanston IL 60208 USA

We introduce a framework to approximate Markov decision processes (MDPs) that stands on two pillars: (i) state aggregation, as the algorithmic infrastructure, and (ii) central-limit-theorem-type approximations, as the mathematical underpinning of optimality guarantees. The theory is grounded in recent work by Braverman et al. (2020) that relates the solution of the Bellman equation to that of a partial differential equation (PDE) where, in the spirit of the central limit theorem, the transition matrix is reduced to its local first and second moments. Solving the PDE is not required by our method. Instead, we construct a "sister" (controlled) Markov chain whose two local transition moments are approximately identical with those of the focal chain. Because of this moment matching, the original chain and its sister are coupled through the PDE, a coupling that facilitates optimality guarantees. Embedded into standard soft aggregation algorithms, moment matching provides a disciplined mechanism to tune the aggregation and disaggregation probabilities. Computational gains arise from the reduction of the effective state space from N to N12+e is as one might intuitively expect from approximations grounded in the central limit theorem.

关键词： Markov processes approximate dynamic programming state aggregation parameter design algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

A windowing approach to detecting line segments using Hough transform

引用

PATTERN RECOGNITION 1996年第2期29卷 255-265页

作者： Zhang, YF Webber, R UNIV WESTERN ONTARIO DEPT COMP SCILONDONON N6A 5B9CANADA

A new approach for using the Hough transform to detect line segments is presented. This approach is efficient in both space and time. Strategies combining the features of the intersection point [Ben-Tzvi, Leavers and Sandler, Proc. 5th Intl. Conf. Image Anal. 152-159 (1990);Xu, Oja and Kultannen, Pattern Recognition Lett. 11, 331-338 (1990)] and dual plane [Conker, Comput. Vis. Graphics Image Process. 43, 115-132 (1988)] methods are used to calculate the Hough transform. A dense set of small overlapping windows are used to restrict the pairs of image pixels that are evaluated. Experimental results indicate that this method reduces the time and space requirements significantly.

关键词： feature detection Hough transform parallel image processing algorithm analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：