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

Shared-memory parallel Maximal Clique Enumeration from Static and Dynamic Graphs

ACM TRANSACTIONS ON parallel COMPUTING 2020年第1期7卷 1–28页

作者： Das, Apurba Sanei-Mehri, Seyed-Vahid Tirthapura, Srikanta Iowa State Univ Ames IA 50011 USA

Maximal Clique Enumeration (MCE) is a fundamental graph mining problem and is useful as a primitive in identifying dense structures in a graph. Due to the high computational cost of MCE, parallel methods are imperative for dealing with large graphs. We present shared-memory parallel algorithms for MCE, with the following properties: (1) the parallel algorithms are provably work-efficient relative to a state-of-the-art sequential algorithm, (2) the algorithms have a provably small parallel depth, showing they can scale to a large number of processors, and (3) our implementations on a multicore machine show good speedup and scaling behavior with increasing number of cores and are substantially faster than prior shared-memory parallel algorithms for MCE;for instance, on certain input graphs, while prior works either ran out of memory or did not complete in five hours, our implementation finished within a minute using 32 cores. We also present work-efficient parallel algorithms for maintaining the set of all maximal cliques in a dynamic graph that is changing through the addition of edges.

关键词： parallel algorithm maximal clique enumeration dynamic graph batch parallel algorithm work depth analysis scalable graph processing

来源：评论

学校读者我要写书评

暂无评论

parallel algorithm for Solving the System of Simultaneous Linear Equations by Jacobi Method on Extended Fibonacci Cubes

Parallel Algorithm for Solving the System of Simultaneous Li...

引用

3rd IEEE International Advance Computing Conference (IACC)

作者： Tripathy, Alok Ranjan Ray, B. N. B. Coll Engn Bhubaneswar Dept Comp Sci & Engn Bhubaneswar 751024 Orissa India Utkal Univ Dept Comp Sci & Applicat Bhubaneswar 751004 Orissa India

ISBN: (纸本)9781467345286

This work suggests parallel algorithms for solving a sparse system of N - linear equations in N - unknowns by Jacobi method on Extended Fibonacci Cube EFC1(n) [3]. Where n is the degree of EFC1(n) and N is the number of processors of EFC1(n). Two parallel versions of the algorithm are discussed. The single pass of the first algorithm involves 2 (N - 1) data communications in N steps. Whereas the second algorithm achieves the same number of data communications in N/2 + logN steps. Further each pass of both algorithms have 3N/2 + 1 additions, N/2 - 1 subtractions, N - 1 multiplications and N divisions.

关键词： Jacobi Method Hamiltonian cycle Extended Fibonacci Cube parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

Convergence theorem for system of pseudomonotone equilibrium and split common fixed point problems in Hilbert spaces

引用

BOLLETTINO DELLA UNIONE MATEMATICA ITALIANA 2021年第2期14卷 403-428页

作者： Jolaoso, Lateef Olakunle Lukumon, Gafari Abiodun Aphane, Maggie Sefako Makgatho Hlth Sci Univ Dept Math & Appl Math POB 94 ZA-0204 Pretoria South Africa Univ KwaZulu Natal Sch Math Stat & Comp Sci Durban South Africa

We consider a system of pseudomonotone equilibrium problem and split common fixed point problem in the framework of real Hilbert spaces. We propose a modified extragradient method with line searching technique for approximating a common element in the sets of solutions of the two nonlinear problems. The convergence result is proved without prior knowledge of the Lipschitz-like constants of the equilibrium bifunctions and the norm of the bounded linear operator of the split common fixed point problem. We further provide some application and numerical example to show the importance of the obtained results in the paper.

关键词： Equilibrum problem Pseudomonotone equilibrium parallel algorithm Split common fixed point Demimetric mappings numerical method

来源：评论

学校读者我要写书评

暂无评论

A Set Automaton to Locate All Pattern Matches in a Term 1

引用

18th International Colloquium on Theoretical Aspects of Computing (ICTAC)

作者： Erkens, Rick Groote, Jan Friso Eindhoven Univ Technol Math & Comp Sci Eindhoven Netherlands

ISBN: (数字)9783030853150

ISBN: (纸本)9783030853150;9783030853143

Term pattern matching is the problem of finding all pattern matches in a subject term, given a set of patterns. Finding efficient algorithms for this problem is an important direction for research [21]. We present a new set automaton solution for the term pattern matching problem that is based on match set derivatives where each function symbol in the subject pattern is visited exactly once. The algorithm allows for various traversal patterns over the subject term and is particularly suited to search the subject term in parallel.

关键词： Pattern matching Set automaton parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

parallel rotor/stator interaction methods and steady/unsteady flow simulations of multi-row axial compressors

引用

AEROSPACE SCIENCE AND TECHNOLOGY 2021年 116卷 106859-106859页

作者： Liu, An Ju, Yaping Zhang, Chuhua Xi An Jiao Tong Univ Sch Energy & Power Engn Dept Fluid Machinery & Engn Xian Shaanxi Peoples R China Xi An Jiao Tong Univ State Key Lab Strength & Vibrat Mech Struct Xian Shaanxi Peoples R China

Rotor/stator interaction plays a crucial role in predicting the aerodynamic performance of high-speed multi-row axial compressor. Although mixing plane method has been widely used in steady simulations of multi-row single passage flows, the exchange of spanwise non-matched profiles of flow variable between adjacent blade rows is still unknown. Besides, quite little work was devoted to sliding mesh method for unsteady simulations of multi-row full-annulus compressor flows. In this work, mixing plane method and sliding mesh method were developed and presented, respectively, in the environment of parallel computer platforms. Particular attentions were paid to the accurate exchange of spanwise non-matched profiles of fluxes in mixing plane method, and the fast search algorithms of spanwise and circumferential non-matched meshes in sliding mesh method. The developed parallel rotor/stator interaction methods were validated with two multi-row high-speed axial compressors, i.e. NASA Stage 35 and first three stages of NASA 74A, both of which were calculated with steady flow simulation of one blade passage per row and unsteady flow simulation of full-annulus passages per row. Results highlighted that both the developed mixing plane method and sliding mesh method were able to predict the aerodynamic performance curve accurately and satisfy the interface flux conservation tightly. The flow wake and shock wave were observed to transfer continuously across rotor/stator interface with sliding mesh method in the unsteady full-annulus simulation. This work is valuable for the further development of advanced aerodynamic design and accurate performance prediction of multi-row axial compressors. (c) 2021 Elsevier Masson SAS. All rights reserved.

关键词： Rotor/stator interaction Mixing plane method Sliding mesh method parallel algorithm Multi-row axial compressor Aerodynamic performance

来源：评论

学校读者我要写书评

暂无评论

Edmonds' Blossom algorithm Analysis in a Medical Emergency Management System 9

Edmonds' Blossom Algorithm Analysis in a Medical Emergency M...

引用

9th IEEE International Conference on e-Health and Bioengineering (EHB)

作者： Dragomir-Loga, Gabriel Cristian Pop, Marius Tech Univ Cluj Napoca Comp Sci Dept Cluj Napoca Romania

ISBN: (纸本)9781665440004

This paper research is focused on the use of a matching algorithm, from graph theory, over an emergency medical system. The application architecture is divided across multiple modules, communicating between them in real time: ambulance level module, hospital level modules, central module (medical center, in charge of deciding the hospital/s compatible to the accident), traffic center module (in charge of deciding the route towards the chosen hospital). The experimental results, for both implementation approaches, sequential and parallel, have proven that for Blossom algorithm, a more scalable solution regarding the number of simultaneous accidents, is represented by the parallel implementation.

关键词： matching algorithm healthcare-system parallel algorithm emergency-management-system

来源：评论

学校读者我要写书评

暂无评论

The enhanced sampling in parallel finite-time dynamics method with replica exchange

引用

COMPUTER PHYSICS COMMUNICATIONS 2021年 263卷 107911-107911页

作者： Xu, Chudong Lu, Shengdong Kong, Yongfeng Xiong, Wanjie South China Agr Univ Coll Elect Engn Guangzhou 510640 Guangdong Peoples R China

The finite-time dynamical method is an effective tool studying phase transition in many-body systems. We design a parallel version of this method based on replica exchange whose probability is deduced from Langevin equation. The configuration swaps between different replicas enhance the importance sampling in parallel and control the fluctuation, leading to the conspicuous improvement for the simulation efficiency. The computational performance with configuration exchange is above 3 times as high as the calculation effect without the exchange on five current CPU cores. In addition, this parallel algorithm is used to simulate the two- and three-dimensional Ising model and obtain compatible exponents with that from theoretical solutions and numerical simulations from references, verifying the reliability of the scheme. (C) 2021 Elsevier B.V. All rights reserved.

关键词： parallel algorithm Replica exchange The finite-time dynamics method Monte Carlo simulation

来源：评论

学校读者我要写书评

暂无评论

parallel approximation for partial set cover

引用

APPLIED MATHEMATICS AND COMPUTATION 2021年 408卷 126358-126358页

作者： Ran, Yingli Zhang, Ying Zhang, Zhao Zhejiang Normal Univ Coll Math & Comp Sci Jinhua 321004 Zhejiang Peoples R China

In a minimum partial set cover problem (MinPSC), given a ground set E with n elements, a collection S of subsets of E with vertical bar S vertical bar = m, a cost function c : S -> R+, and an integer k <= n, the goal of MinPSC is to find a minimum cost sub-collection of S that covers at least k elements of E. In this paper, we design a parallel algorithm for MinPSC which yields a solution with approximation ratio at most f/1-2 epsilon in O(1/epsilon log mn/epsilon) rounds, where f is the maximum number of sets containing a common element, and 0 < epsilon < 1/2 is a constant. We also design a parallel algorithm for a special MinPSC problem, the minimum power partial cover problem (MinPPC), which achieves approximation ratio at most (3+2 epsilon)(alpha)/1-2 epsilon in O(1/epsilon log mn/epsilon log(2) m) rounds, where alpha >= 1 is the attenuation factor of power. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Minimum partial set cover Minimum power partial cover parallel algorithm Approximation ratio

来源：评论

学校读者我要写书评

暂无评论

Efficient Construction of Directed Hopsets and parallel Approximate Shortest Paths 2020

Efficient Construction of Directed Hopsets and Parallel Appr...

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Cao, Nairen Fineman, Jeremy T. Russell, Katina Georgetown Univ Washington DC 20057 USA

ISBN: (纸本)9781450369794

The approximate single-source shortest-path problem is as follows: given a graph with nonnegative edge weights and a designated source vertex s, return estimates of the distances from s to each other vertex such that the estimate falls between the true distance and (1 + epsilon) times the distance. This paper provides the first nearly work-efficient parallel algorithm with sublinear span (also called depth) for the approximate shortest-path problem on directed graphs. Specifically, for constant epsilon and polynomially-bounded edge weights, our algorithm has work (O) over tilde (m) and span n(1/2+o(1)). Several algorithms were previously known for the case of undirected graphs, but none of the techniques seem to translate to the directed setting. The main technical contribution is the first nearly linear-work algorithm for constructing hopsets on directed graphs. A (beta, epsilon)-hopset is a set of weighted edges (sometimes called shortcuts) which, when added to the graph, admit beta-hop paths with weight no more than (1+epsilon) times the true shortest-path distances. There is a simple sequential algorithm that takes as input a directed graph and produces a linear-cardinality hopset with beta = (O) over tilde(root n), but its running time is quite highspecifically (O) over tilde (m root n). Our algorithm is the first more efficient algorithm that produces a directed hopset with similar characteristics. Specifically, our sequential algorithm runs in (O) over tilde (m) time and constructs a hopset with (O) over tilde (n) edges and beta = n(1/2+o(1)). A parallel version of the algorithm has work (O) over tilde (m) and span n(1/2+o(1)).

关键词： parallel algorithm hopsets shortest paths shortcuts

来源：评论

学校读者我要写书评

暂无评论

Efficient Route Selection for Drone-based Delivery Under Time-varying Dynamics 18

Efficient Route Selection for Drone-based Delivery Under Tim...

引用

18th IEEE International Conference on Mobile Ad hoc and Smart Systems (IEEE MASS)

作者： Khanda, Arindam Coro, Federico Sorbelli, Francesco Betti Pinotti, Cristina M. Das, Sajal K. Missouri Univ Sci & Technol Dept Comp Sci Rolla MO 65409 USA Univ Perugia Dept Comp Sci & Math Perugia Italy

ISBN: (纸本)9781665449359

The use of drones can be a valuable solution for the problem of delivering goods for many reasons. In fact, they can be efficiently employed in time-critical situations when there is a traffic jam on the roads, to serve customers in hard-toreach places, or simply to expand the business. However, due to limited battery capacities and the fact that drones can serve a single customer at a time, a drone-based delivery system (DBDS) aims to minimize the drones' energy usage for completing a route from the depot to the customer and go back to the depot for new deliveries. In general, the shortest delivery route could not be the optimal choice since external factors like the wind (which varies with time) can affect energy consumption. Previous work has mainly considered simplified DBDSs assuming architectures with a single drone and with static costs on paths. Moreover, in these non-centralized architectures, the drones themselves compute the routes on the fly employing their onboard processing resources, making this choice costly. In this paper we develop a centralized system for computing energy-efficient time-varying routes for drones in a multi-depot multi-drone delivery system. Specifically, we propose a novel centralized parallel algorithm called parallel Shortest Route Update (PSRU) that, over time, updates the drones' delivery routes avoiding the whole recomputation from scratch. A comprehensive evaluation proves that PSRU is up to 4.5x faster than the state-of-the-art algorithms.

关键词： Drone Dynamic graph parallel algorithm GPU

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：