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

PROCEEDINGS OF THE VLDB ENDOWMENT 2020年第11期13卷 1863-1876页

作者： Fan, Wenfei Jin, Ruochun Liu, Muyang Lu, Ping Tian, Chao Zhou, Jingren Univ Edinburgh Edinburgh Midlothian Scotland Shenzhen Univ Shenzhen Inst Comp Sci Shenzhen Peoples R China Beijing Adv Innovat Ctr Big Data & Brain Comp Beijing Peoples R China Alibaba Grp Seattle WA USA

This paper proposes a class of graph association rules, denoted by GARs, to specify regularities between entities in graphs. A GAR is a combination of a graph pattern and a dependency;it may take as predicates ML (machine learning) classifiers for link prediction. We show that GARs help us catch incomplete information in schemaless graphs, predict links in social graphs, identify potential customers in digital marketing, and extend graph functional dependencies (GFDs) to capture both missing links and inconsistencies. We formalize association deduction with GARs in terms of the chase, and prove its Church-Rosser property. We show that the satisfiability, implication and association deduction problems for GARs are coNP-complete, NP-complete and NP-complete, respectively, retaining the same complexity bounds as their GFD counterparts, despite the increased expressive power of GARs. The incremental deduction problem is DP-complete for GARs versus coNP-complete for GFDs. In addition, we provide parallel algorithms for association deduction and incremental deduction. Using real-life and synthetic graphs, we experimentally verify the effectiveness, scalability and efficiency of the parallel algorithms.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

High-Quality Shared-Memory Graph Partitioning

引用

IEEE TRANSACTIONS ON parallel AND DISTRIBUTED SYSTEMS 2020年第11期31卷 2710-2722页

作者： Akhremtsev, Yaroslav Sanders, Peter Schulz, Christian Google Zurich Switzerland Karlsruhe Inst Technol KIT D-76131 Karlsruhe Germany Univ Vienna Fac Comp Sci A-1010 Vienna Austria

Partitioning graphs into blocks of roughly equal size such that few edges run between blocks is a frequently needed operation in processing graphs. Recently, size, variety, and structural complexity of these networks has grown dramatically. Unfortunately, previous approaches to parallel graph partitioning have problems in this context since they often show a negative trade-off between speed and quality. We present an approach to multi-level shared-memory parallel graph partitioning that produces balanced solutions, shows high speedups for a variety of large graphs and yields very good quality independently of the number of cores used. For example, in an extensive experimental study, at 79 cores, one of our closest competitors is faster but fails to meet the balance criterion in the majority of cases and another is mostly slower and incurs about 13 percent larger cut size. Important ingredients include parallel label propagation for both coarsening and refinement, parallel initial partitioning, a simple yet effective approach to parallel localized local search, and fast locality preserving hash tables.

关键词： Partitioning algorithms Clustering algorithms Program processors Complex networks Contracts parallel algorithms parallel graph partitioning shared-memory parallelism local search label propagation

来源：评论

学校读者我要写书评

暂无评论

The complexity of the asynchronous prediction of the majority automata

引用

INFORMATION AND COMPUTATION 2020年 274卷

作者： Goles, Eric Montealegre, Pedro Univ Adolfo Ibanez Fac Ingn & Ciencias Santiago Chile

We consider the asynchronous prediction problem for some automaton as the one consisting in determining, given an initial configuration, if there exists a non-zero probability that some selected site changes its state, when the network is updated picking one site at a time uniformly at random. We show that for the majority automaton, the asynchronous prediction problem is in NC in the two-dimensional lattice with von Neumann neighborhood. Later, we show that in three or more dimensions the problem is NP-Complete. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Majority automata Cellular automata Prediction problem Asynchronous updating Computational complexity parallel algorithms Bootstrap percolation NP-Completeness

来源：评论

学校读者我要写书评

暂无评论

Super Real Time Electromechanical Electromagnetic Hybrid Simulation Technology Architecture for Large AC / DC Power Grid 2

Super Real Time Electromechanical Electromagnetic Hybrid Sim...

引用

2021 2nd International Conference on Electrical, Electronic Information and Communication Engineering, EEICE 2021

作者： Weijie, Zheng Dechao, Xu Xing, Zhang Xujiang, Chen Jianfeng, Yan Hongwei, Tang Qing, Mu Min, Liu Feng, Wang CEPRI Province Beijing100192 China ICTCLAS Province Beijing100192 China

This paper proposes a parallel algorithm of the electromagnetic electromechanical group decoupling based on the electromechanical electromagnetic dual master control, including the hybrid simulation architecture of the group decoupling including the electromechanical transient interface, the data transmission of the electromechanical electromagnetic hybrid simulation, and the corresponding network splitting method, the generation scheme of the electromagnetic subnet group and the master control scheme. The new algorithm can greatly improve the parallel computing efficiency of hybrid simulation and meet the requirements of accuracy. By the realization of the parallel algorithm of the electromagnetic electromechanical group decoupling based on the electromagnetic master control, the hybrid simulation performance of ADPSS is improved, which can support the hybrid simulation of large-scale AC and DC power grid. © Published under licence by IOP Publishing Ltd.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed algorithms for convex problems with linear coupling constraints

引用

JOURNAL OF GLOBAL OPTIMIZATION 2020年第1期77卷 53-73页

作者： Colombo, Tommaso Sagratella, Simone Sapienza Univ Rome Dept Comp Control & Management Engn Antonio Ruber Rome Italy

Distributed and parallel algorithms have been frequently investigated in the recent years, in particular in applications like machine learning. Nonetheless, only a small subclass of the optimization algorithms in the literature can be easily distributed, for the presence, e.g., of coupling constraints that make all the variables dependent from each other with respect to the feasible set. Augmented Lagrangian methods are among the most used techniques to get rid of the coupling constraints issue, namely by moving such constraints to the objective function in a structured, well-studied manner. Unfortunately, standard augmented Lagrangian methods need the solution of a nested problem by needing to (at least inexactly) solve a subproblem at each iteration, therefore leading to potential inefficiency of the algorithm. To fill this gap, we propose an augmented Lagrangian method to solve convex problems with linear coupling constraints that can be distributed and requires a single gradient projection step at every iteration. We give a formal convergence proof to at least epsilon-approximate solutions of the problem and a detailed analysis of how the parameters of the algorithm influence the value of the approximating parameter epsilon. Furthermore, we introduce a distributed version of the algorithm allowing to partition the data and perform the distribution of the computation in a parallel fashion.

关键词： Nonlinear optimization parallel algorithms Distributed algorithms Lagrangian methods

来源：评论

学校读者我要写书评

暂无评论

Distributed and Asynchronous Algorithm for Smooth High-dimensional Function Approximation using Orthotope B-splines

Distributed and Asynchronous Algorithm for Smooth High-dimen...

引用

作者： Meyer, Johann Delft University of Technology

学位级别：硕士

Aircraft are complex systems with, in some cases, high-dimensional nonlinear interactions between control surfaces. When a failure occurs, adaptive flight control methods can be utilised to stabilise and make the aircraft controllable. Adaptive flight control methods, however, require accurate aerodynamic models - where first-order continuity is necessary for estimating the control derivatives and mitigating chattering that can reduce the longevity of components. Additionally, high-dimensional offline model identification with current approaches can take several hours for a few dimensions and this means model iterating and hyper-parameter tuning is often not feasible. Current approaches to smooth high-dimensional functional approximation are not scalable, require global communication between iteration steps, and are ill-conditioned in higher dimensions. This research develops the Distributed Asynchronous B-spline (DAB) algorithm that is more robust to ill-conditioning, due to low data coverage, by using first-order methods with acceleration and weighted constraint application. This algorithm is also suitable for continuous state-spaces. Smooth aerodynamic models can be determined in exactly n·r iterations, where r is the number of continuity equations in a single dimension and n is the number of dimensions. Moreover, memory reorganisation is proposed to avoid false sharing and conflict-free use of shared memory on the GPU to ensure that the algorithm runs efficiently in parallel.

关键词： Smooth High-dimensional Linear Function Approximation Linearly-constrained Convex Quadratic Programming Asynchronous algorithms parallel algorithms Multivariate B-spline System Identification GPU Cache-aware

来源：评论

学校读者我要写书评

暂无评论

A Novel Plastic Phase-Field Method for Ductile Fracture with GPU Optimization

引用

COMPUTER GRAPHICS FORUM 2020年第7期39卷 105-117页

作者： Zhao, Zipeng Huang, Kemeng Li, Chen Wang, Changbo Qin, Hong East China Normal Univ Sch Comp Sci & Technol Shanghai Peoples R China SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA

In this paper, we articulate a novel plastic phase-field (PPF) method that can tightly couple the phase-field with plastic treatment to efficiently simulate ductile fracture with GPU optimization. At the theoretical level of physically-based modeling and simulation, our PPF approach assumes the fracture sensitivity of the material increases with the plastic strain accumulation. As a result, we first develop a hardening-related fracture toughness function towards phase-field evolution. Second, we follow the associative flow rule and adopt a novel degraded von Mises yield criterion. In this way, we establish the tight coupling of the phase-field and plastic treatment, with which our PPF method can present distinct elastoplasticity, necking, and fracture characteristics during ductile fracture simulation. At the numerical level towards GPU optimization, we further devise an advanced parallel framework, which takes the full advantages of hierarchical architecture. Our strategy dramatically enhances the computational efficiency of preprocessing and phase-field evolution for our PPF with the material point method (MPM). Based on our extensive experiments on a variety of benchmarks, our novel method's performance gain can reach 1.56x speedup of the primary GPU MPM. Finally, our comprehensive simulation results have confirmed that this new PPF method can efficiently and realistically simulate complex ductile fracture phenomena in 3D interactive graphics and animation.

关键词： CCS Concepts • Computing methodologies → Physical simulation parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A Probabilistic Linear Solver Based on a Multilevel Monte Carlo Method

引用

JOURNAL OF SCIENTIFIC COMPUTING 2020年第3期82卷 1-22页

作者： Acebron, Juan A. Univ Inst Lisbon Dept Informat Sci & Technol ISCTE Lisbon Portugal Univ Lisbon INESC ID Inst Super Tecn Lisbon Portugal

We describe a new Monte Carlo method based on a multilevel method for computing the action of the resolvent matrix over a vector. The method is based on the numerical evaluation of the Laplace transform of the matrix exponential, which is computed efficiently using a multilevel Monte Carlo method. Essentially, it requires generating suitable random paths which evolve through the indices of the matrix according to the probability law of a continuous-time Markov chain governed by the associated Laplacian matrix. The convergence of the proposed multilevel method has been discussed, and several numerical examples were run to test the performance of the algorithm. These examples concern the computation of some metrics of interest in the analysis of complex networks, and the numerical solution of a boundary-value problem for an elliptic partial differential equation. In addition, the algorithm was conveniently parallelized, and the scalability analyzed and compared with the results of other existing Monte Carlo method for solving linear algebra systems.

关键词： Multilevel Monte Carlo method Network analysis parallel algorithms High performance computing

来源：评论

学校读者我要写书评

暂无评论

Multicore and manycore parallelization of cheap synchronizing sequence heuristics

引用

JOURNAL OF parallel AND DISTRIBUTED COMPUTING 2020年 140卷 13-24页

作者： Karahoda, Sertac Erenay, Osman Tufan Kaya, Kamer Turker, Uraz Cengiz Yenigun, Husnu Sabanci Univ Fac Sci & Engn Comp Sci & Engn Istanbul Turkey Univ Leicester Dept Informat Leicester Leics England

An important concept in finite state machine based testing is synchronization which is used to initialize an implementation to a particular state. Usually, synchronizing sequences are used for this purpose and the length of the sequence used is important since it determines the cost of the initialization process. Unfortunately, the shortest synchronization sequence problem is NP-Hard. Instead, heuristics are used to generate short sequences. However, the cubic complexity of even the fastest heuristic algorithms can be a problem in practice. In order to scale the performance of the heuristics for generating short synchronizing sequences, we propose algorithmic improvements together with a parallel implementation of the cheapest heuristics existing in the literature. To identify the bottlenecks of these heuristics, we experimented on random and slowly synchronizing automata. The identified bottlenecks in the algorithms are improved by using algorithmic modifications. We also implement the techniques on multicore CPUs and Graphics Processing Units (GPUs) to take benefit of the modern parallel computation architectures. The sequential implementation of the heuristic algorithms are compared to our parallel implementations by using a test suite consisting of 1200 automata. The speedup values obtained depend on the size and the nature of the automaton. In our experiments, we observe speedup values as high as 340x by using a 16-core CPU parallelization, and 496x by using a GPU. Furthermore, the proposed methods scale well and the speedup values increase as the size of the automata increases. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Software testing Finite state automata Synchronizing sequences parallel algorithms Graphics processing units

来源：评论

学校读者我要写书评

暂无评论

Weak Constraint Gaussian Processes for optimal sensor placement

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2020年 42卷

作者： Dur, Tolga Hasan Arcucci, Rossella Mottet, Laetitia Molina Solana, Miguel Pain, Christopher Guo, Yi-Ke Imperial Coll London Data Sci Inst Dept Comp London England Imperial Coll London Dept Earth Sci & Engn London England Univ Granada Dept Comp Sci & AI Granada Spain

We present a Weak Constraint Gaussian Process (WCGP) model to integrate noisy inputs into the classical Gaussian Process (GP) predictive distribution. This model follows a Data Assimilation approach (i.e. by considering information provided by observed values of a noisy input in a time window). Due to the increased number of states processed from real applications and the time complexity of GP algorithms, the problem mandates a solution in a high performance computing environment. In this paper, parallelism is explored by defining the parallel WCGP model based on domain decomposition. Both a mathematical formulation of the model and a parallel algorithm are provided. We use the algorithm for an optimal sensor placement problem. Experimental results are provided for pollutant dispersion within a real urban environment. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Gaussian Processes Sensor placement Data assimilation parallel algorithms Big data

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：