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

distributed Synchronous and Asynchronous algorithms for Semidefinite Programming With Diagonal Constraints

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2023年第2期68卷 1007-1022页

作者： Jiang, Xia Zeng, Xianlin Sun, Jian Chen, Jie Beijing Inst Technol Key Lab Intelligent Control & Decis Complex Syst Beijing Peoples R China Beijing Inst Technol Sch Automat Beijing Peoples R China Beijing Inst Technol Chongqing Innovat Ctr Chongqing 401120 Peoples R China Tongji Univ Sch Elect & Informat Engn Shanghai 200082 Peoples R China Minist Educ Beijing Inst Technol Beijing Adv Innovat Ctr Intelligent Robots & Syst Key Lab Biomimet Robots & Syst Beijing 100081 Peoples R China

This article develops distributed synchronous and asynchronous algorithms for the large-scale semidefinite programming with diagonal constraints, which has wide applications in combinatorial optimization, image processing, and community detection. The information of the semidefinite programming is allocated to multiple interconnected agents such that each agent aims to find a solution by communicating to its neighbors. Based on the low-rank property of solutions and the Burer-Monteiro factorization, we transform the original problem into a distributed optimization problem over unit spheres to reduce variable dimensions and ensure positive semidefiniteness without involving semidefinite projections, which are computationally expensive. For the distributed optimization problem, we propose distributed synchronous and asynchronous algorithms, both of which reduce computational burden and storage space compared with existing centralized algorithms. Specifically, the distributed synchronous algorithm almost surely escapes strict saddle points and converges to the set of optimal solutions to the optimization problem. In addition, the proposed distributed asynchronous algorithm allows communication delays and converges to critical points to the optimization problem under mild conditions. By applying the proposed algorithms to image segmentation, we illustrate the efficiency and convergence performance of the two proposed algorithms.

关键词： Optimization Symmetric matrices distributed algorithms Programming Costs Convergence Sun distributed optimization low-rank matrices semidefinite programming (SDP) with diagonal constraints synchronous and asynchronous algorithms

来源：评论

学校读者我要写书评

暂无评论

Certification of distributed algorithms Solving Problems with Optimal Substructure 1

引用

13th International Conference on Software Engineering and Formal Methods (SEFM)

作者： Voellinger, Kim Reisig, Wolfgang Humboldt Univ D-10099 Berlin Germany

ISBN: (数字)9783319229690

ISBN: (纸本)9783319229690;9783319229683

We report work-in-progress on applying the concept of a certifying algorithm to distributed algorithms. A certifying algorithm produces not only a result, but also a witness that verifies the result's correctness. Certifying variants of numerous (sequential) algorithms have been developed. However, distributed algorithms behave differently from sequential algorithms. Consequently, it is challenging to make them certifying. Our local approach is to make the distributed algorithm compute many local witnesses that together verify the result's correctness. We identified problems for which this approach is applicable. Particularly, we hypothesize that for problems with optimal substructure (i.e., an optimal solution can be constructed from optimal solutions of its sub-problems) it is often easy to apply the local approach. As an example, we give a certifying distributed algorithm for the shortest path problem.

关键词： distributed algorithms Certifying algorithms Optimal substructure Shortest path problem

来源：评论

学校读者我要写书评

暂无评论

distributed-Memory Parallel algorithms for Sparse Matrix and Sparse Tall-and-Skinny Matrix Multiplication 24

Distributed-Memory Parallel Algorithms for Sparse Matrix and...

引用

2024 International Conference for High Performance Computing, Networking, Storage and Analysis

作者： Ranawaka, Isuru Hussain, Md Taufique Block, Charles Gerogiannis, Gerasimos Torrellas, Josep Azad, Ariful Indiana Univ Bloomington IN 47405 USA Univ Illinois Champaign IL USA

ISBN: (数字)9798350352917

ISBN: (纸本)9798350352924;9798350352917

We consider a sparse matrix-matrix multiplication (SpGEMM) setting where one matrix is square and the other is tall and skinny. This special variant, TS-SpGEMM, has important applications in multi-source breadth-first search, influence maximization, sparse graph embedding, and algebraic multi-grid solvers. Unfortunately, popular distributed algorithms like sparse SUMMA deliver suboptimal performance for TS-SpGEMM. To address this limitation, we develop a novel distributed-memory algorithm tailored for TS-SpGEMM. Our approach employs customized 1D partitioning for all matrices involved and leverages sparsity-aware tiling for efficient data transfers. In addition, it minimizes communication overhead by incorporating both local and remote computations. On average, our TS-SpGEMM algorithm attains 5x performance gains over 2D and 3D SUMMA. Furthermore, we use our algorithm to implement multi-source breadth-first search and sparse graph embedding algorithms and demonstrate their scalability up to 512 Nodes (or 65,536 cores) on NERSC Perlmutter.

关键词： Three-dimensional displays Shape Scalability Performance gain Data transfer Partitioning algorithms Sparse matrices distributed algorithms Parallel algorithms Optimization

来源：评论

学校读者我要写书评

暂无评论

A review of distributed optimization: Problems, models and algorithms

引用

NEUROCOMPUTING 2022年第0期483卷 446-459页

作者： Zheng, Yanling Liu, Qingshan Southeast Univ Sch Math Nanjing 210096 Peoples R China Southeast Univ Jiangsu Prov Key Lab Networked Collect Intelligen Nanjing 210096 Peoples R China

With the development of big data and artificial intelligence, distributed optimization has emerged as an indispensable tool for solving large-scale problems. In particular, the multi-agent system based on distributed information processing can be elaborately designed for distributed optimization, in which the agents collaboratively minimize a global objective function made up of a sum of local objective cost functions subject to some local and/or global constraints. Inspired by the applications involving resource allocation, machine learning, power systems, sensor networks and cloud computing, a variety of distributed optimization models and algorithms have been investigated and developed. The optimization models include unconstrained and constrained problems in continuous and discontinuous systems with undirected and directed communication topology graphs. The constraints include bounded constraint, separable and inseparable equality and inequality constraints. Meanwhile, in distributed algorithms, every agent executes its local computation and updating on basis of its own data information and that exchanging with its neighboring agents by means of the underlying communication networks, in order to deal with the optimization problems in a distributed way. This paper is designed to provide a comprehensive overview of extant distributed models and algorithms for distributed optimization.(c) 2021 Elsevier B.V. All rights reserved.

关键词： distributed optimization distributed algorithms distributed models Multi-agent systems

来源：评论

学校读者我要写书评

暂无评论

distributed algorithms for content allocation in interconnected content distribution networks

Distributed algorithms for content allocation in interconnec...

引用

IEEE Annual Joint Conference: INFOCOM, IEEE Computer and Communications Societies

作者： Valentino Pacifici György Dán ACCESS Linnaeus Center Royal Institute of Technology Stockholm Sweden

Internet service providers increasingly deploy internal CDNs with the objective of reducing the traffic on their transit links and to improve their customers' quality of experience. Once ISP managed CDNs (nCDNs) become commonplace, ISPs would likely provide common interfaces to interconnect their nCDNs for mutual benefit, as they do with peering today. In this paper we consider the problem of using distributed algorithms for computing a content allocation for nCDNs. We show that if every ISP aims to minimize its cost and bilateral payments are not allowed then it may be impossible to compute a content allocation. For the case of bilateral payments we propose two distributed algorithms, the aggregate value compensation (AC) and the object value compensation (OC) algorithms, which differ in terms of the level of parallelism they allow and in terms of the amount of information exchanged between nCDNs. We prove that the algorithms converge, and we propose a scheme to ensure ex-post individual rationality. Simulations performed on a real AS-level network topology and synthetic topologies show that the algorithms have geometric rate of convergence, and scale well with the graphs' density and the nCDN capacity.

关键词： Resource management Convergence distributed algorithms Aggregates Cost function Games Nash equilibrium

来源：评论

学校读者我要写书评

暂无评论

Consensus-Based Cooperative algorithms for Training Over distributed Data Sets Using Stochastic Gradients

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2022年第10期33卷 5579-5589页

作者： Li, Zhongguo Liu, Bo Ding, Zhengtao Univ Manchester Dept Elect & Elect Engn Manchester M13 9PL Lancs England

In this article, distributed algorithms are proposed for training a group of neural networks with private data sets. Stochastic gradients are utilized in order to eliminate the requirement for true gradients. To obtain a universal model of the distributed neural networks trained using local data sets only, consensus tools are introduced to derive the model toward the optimum. Most of the existing works employ diminishing learning rates, which are often slow and impracticable for online learning, while constant learning rates are studied in some recent works, but the principle for choosing the rates is not well established. In this article, constant learning rates are adopted to empower the proposed algorithms with tracking ability. Under mild conditions, the convergence of the proposed algorithms is established by exploring the error dynamics of the connected agents, which provides an upper bound for selecting the constant learning rates. Performances of the proposed algorithms are analyzed with and without gradient noises, in the sense of mean square error (MSE). It is proved that the MSE converges with bounded errors determined by the gradient noises, and the MSE converges to zero if the gradient noises are absent. Simulation results are provided to validate the effectiveness of the proposed algorithms.

关键词： Training Neural networks Convergence distributed databases Machine learning algorithms Optimization distributed algorithms Consensus convergence analysis distributed training multiagent systems neural networks optimization

来源：评论

学校读者我要写书评

暂无评论

Parallel graph coloring algorithms for distributed GPU environments

引用

PARALLEL COMPUTING 2022年 110卷

作者： Bogle, Ian Slota, George M. Boman, Erik G. Devine, Karen D. Rajamanickam, Sivasankaran Rensselaer Polytech Inst Dept Comp Sci Troy NY 12180 USA Sandia Natl Labs Scalable Algorithms Dept POB 5800 Albuquerque NM 87185 USA

Graph coloring is often used in parallelizing scientific computations that run in distributed and multi-GPU environments;it identifies sets of independent data that can be updated in parallel. Many algorithms exist for graph coloring on a single GPU or in distributed memory, but to the best of our knowledge, hybrid MPI+GPU algorithms have been unexplored until this work. We present several MPI+GPU coloring approaches based on the distributed coloring algorithms of Gebremedhin et al. and the shared-memory algorithms of Deveci et al. The on-node parallel coloring uses implementations in KokkosKernels, which provide parallelization for both multicore CPUs and GPUs. We further extend our approaches to compute distance-2 and partial distance-2 colorings, giving the first known distributed, multi-GPU algorithm for these problems. In addition, we propose a novel heuristic to reduce communication for recoloring in distributed graph coloring. Our experiments show that our approaches operate efficiently on inputs too large to fit on a single GPU and scale up to graphs with 76.7 billion edges running on 128 GPUs.

关键词： Graph coloring distributed algorithms GPU Combinatorial scientific computing

来源：评论

学校读者我要写书评

暂无评论

Towards Formal Verification of distributed algorithms

Towards Formal Verification of Distributed Algorithms

引用

22nd International Symposium on Temporal Representation and Reasoning (TIME)

作者： Bollig, Benedikt ENS Cachan CNRS LSV Cachan France Inria Rocquencourt France

Model checking is an automatic verification technique, which provides an answer to the question whether a pro-gram, given as a state-transition system, satisfies its specification, given in terms of a temporal-logic f... 详细信息

ISBN: (纸本)9781467393171

关键词： Towards Formal Verification distributed algorithms terms of a temporal-logic distributed algorithms Formal verification Model checking Answer

来源：评论

学校读者我要写书评

暂无评论

Predefined-time distributed event-triggered algorithms for resource allocation

引用

IET CYBER-PHYSICAL SYSTEMS: THEORY & APPLICATIONS 2022年第4期7卷 183-196页

作者： Shi, Xiasheng Xu, Lei Yang, Tao Dalian Univ Technol Key Lab Intelligent Control & Optimizat Ind Equip Minist Educ Dalian Peoples R China Northeastern Univ State Key Lab Synthet Automat Proc Ind Shenyang 110819 Liaoning Peoples R China

The resource allocation problem in a distributed multi-agent system is considered in this study. First, the authors develop a predefined-time distributed algorithm and analyse its convergence analysis using the Lyapunov stability theory, in which the local constraint is ensured by a differential projection operator. Thus, a predefined time is obtained by a time-varying time-based generator. Second, to reduce the communication consumption between agents, the authors develop a static as well as a dynamic-based event-triggered control scheme, where the information broadcast only occurs at some discrete time instants. Moreover, the three proposed algorithms converge precisely to the global optimal solution. Besides, the Zeno behaviour is excluded in the above static and dynamic event-triggered mechanisms. Finally, the authors test the proposed algorithms' efficiency based on the provided numerical examples.

关键词： Lyapunov stability theory time-varying systems distributed multiagent system predefined-time distributed event-triggered algorithms multi-agent systems distributed algorithms predefined-time distributed algorithm convergence analysis stability differential projection operator distributed control resource allocation problem static event-triggered mechanisms convergence resource allocation Lyapunov methods dynamic-based event-triggered control scheme time-varying time-based generator

来源：评论

学校读者我要写书评

暂无评论

Geometric Convergence of Gradient Play algorithms for distributed Nash Equilibrium Seeking

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2021年第11期66卷 5342-5353页

作者： Tatarenko, Tatiana Shi, Wei Nedic, Angelia Arizona State Univ Sch Elect Comp & Energy Engn Phoenix AZ 85004 USA Moscow Inst Phys & Technol Dolgoprudnyi 141701 Russia

We study distributed algorithms for seeking a Nash equilibrium in a class of convex networked Nash games with strongly monotone mappings. Each player has access to her own smooth local cost function and can communicate to her neighbors in some undirected graph. To deal with fast distributed learning of Nash equilibria under such settings, we introduce a so called augmented game mapping and provide conditions under which this mapping is strongly monotone. We consider a distributed gradient play algorithm for determining a Nash equilibrium (GRANE). The algorithm involves every player performing a gradient step to minimize her own cost function while sharing and retrieving information locally among her neighbors in the network. Using the reformulation of the Nash equilibrium problem based on the strong monotone augmented game mapping, we prove the convergence of this algorithm to a Nash equilibrium with a geometric rate. Furthermore, we introduce the Nesterov type acceleration for the gradient play algorithm. We demonstrate that, similarly to the accelerated algorithms in centralized optimization and variational inequality problems, our accelerated algorithm outperforms GRANE in the convergence rate. Moreover, to relax assumptions required to guarantee the strongly monotone augmented mapping, we analyze the restricted strongly monotone property of this mapping and prove geometric convergence of the distributed gradient play under milder assumptions.

关键词： Games Nash equilibrium Convergence Cost function Acceleration distributed algorithms Symmetric matrices distributed algorithms gradient methods multi-agent systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：