The Experts below are selected from a list of 180045 Experts worldwide ranked by ideXlab platform
Babak Hassibi - One of the best experts on this subject based on the ideXlab platform.
-
Distributed Solution of large scale linear systems via accelerated projection based consensus
IEEE Transactions on Signal Processing, 2019Co-Authors: Navid Azizanruhi, Farshad Lahouti, Amir Salman Avestimehr, Babak HassibiAbstract:Solving a large-scale system of linear equations is a key step at the heart of many algorithms in scientific computing, machine learning, and beyond. When the problem dimension is large, computational and/or memory constraints make it desirable, or even necessary, to perform the task in a Distributed fashion. In this paper, we consider a common scenario in which a taskmaster intends to solve a large-scale system of linear equations by distributing subsets of the equations among a number of computing machines/cores. We propose a new algorithm called Accelerated Projection-based Consensus , in which at each iteration every machine updates its Solution by adding a scaled version of the projection of an error signal onto the nullspace of its system of equations, and the taskmaster conducts an averaging over the Solutions with momentum. The convergence behavior of the proposed algorithm is analyzed in detail and analytically shown to compare favorably with the convergence rate of alternative Distributed methods, namely Distributed gradient descent, Distributed versions of Nesterov's accelerated gradient descent and heavy-ball method, the block Cimmino method, and Alternating Direction Method of Multipliers. On randomly chosen linear systems, as well as on real-world data sets, the proposed method offers significant speed-up relative to all the aforementioned methods. Finally, our analysis suggests a novel variation of the Distributed heavy-ball method, which employs a particular Distributed preconditioning and achieves the same theoretical convergence rate as that in the proposed consensus-based method.
-
Distributed Solution of large scale linear systems via accelerated projection based consensus
International Conference on Acoustics Speech and Signal Processing, 2018Co-Authors: Navid Azizan Ruhi, Farshad Lahouti, Salman A Avestimehr, Babak HassibiAbstract:Solving a large-scale system of linear equations is a key step at the heart of many algorithms in scientific computing, machine learning, and beyond. When the problem dimension is large, computational and/or memory constraints make it desirable, or even necessary, to perform the task in a Distributed fashion. In this paper, we consider a common scenario in which a taskmaster intends to solve a large-scale system of linear equations by distributing subsets of the equations among a number of computing machines/cores. We propose a new algorithm called Accelerated Projection-based Consensus (APC) for this problem. The convergence behavior of the proposed algorithm is analyzed in detail and analytically shown to compare favorably with the convergence rate of alternative Distributed methods, namely Distributed gradient descent, Distributed versions of Nesterov's accelerated gradient descent and heavy-ball method, the block Cimmino method, and ADMM. On randomly chosen linear systems, as well as on real-world data sets, the proposed method offers significant speed-up relative to all the aforementioned methods.
-
Distributed Solution of large scale linear systems via accelerated projection based consensus
arXiv: Learning, 2017Co-Authors: Navid Azizan Ruhi, Farshad Lahouti, Salman A Avestimehr, Babak HassibiAbstract:Solving a large-scale system of linear equations is a key step at the heart of many algorithms in machine learning, scientific computing, and beyond. When the problem dimension is large, computational and/or memory constraints make it desirable, or even necessary, to perform the task in a Distributed fashion. In this paper, we consider a common scenario in which a taskmaster intends to solve a large-scale system of linear equations by distributing subsets of the equations among a number of computing machines/cores. We propose an accelerated Distributed consensus algorithm, in which at each iteration every machine updates its Solution by adding a scaled version of the projection of an error signal onto the nullspace of its system of equations, and where the taskmaster conducts an averaging over the Solutions with momentum. The convergence behavior of the proposed algorithm is analyzed in detail and analytically shown to compare favorably with the convergence rate of alternative Distributed methods, namely Distributed gradient descent, Distributed versions of Nesterov's accelerated gradient descent and heavy-ball method, the block Cimmino method, and ADMM. On randomly chosen linear systems, as well as on real-world data sets, the proposed method offers significant speed-up relative to all the aforementioned methods. Finally, our analysis suggests a novel variation of the Distributed heavy-ball method, which employs a particular Distributed preconditioning, and which achieves the same theoretical convergence rate as the proposed consensus-based method.
Zhen Jiang - One of the best experts on this subject based on the ideXlab platform.
-
on constructing the minimum orthogonal convex polygon for the fault tolerant routing in 2 d faulty meshes
IEEE Transactions on Reliability, 2005Co-Authors: Zhen JiangAbstract:The rectangular faulty block model is the most commonly used fault model for designing fault-tolerant, and deadlock-free routing algorithms in mesh-connected multicomputers. The convexity of a rectangle facilitates simple, efficient ways to route messages around fault regions using relatively few or no virtual channels to avoid deadlock. However, such a faulty block may include many nonfaulty nodes which are disabled, i.e., they are not involved in the routing process. Therefore, it is important to define a fault region that is convex, and at the same time, to include a minimum number of nonfaulty nodes. In this paper, we propose an optimal Solution that can quickly construct a set of minimum faulty polygons, called orthogonal convex polygons, from a given set of faulty blocks in a 2-D mesh (or 2-D torus). The formation of orthogonal convex polygons is implemented using either a centralized, or Distributed Solution. Both Solutions are based on the formation of faulty components, each of which consists of adjacent faulty nodes only, followed by the addition of a minimum number of nonfaulty nodes to make each component a convex polygon. Extensive simulation has been done to determine the number of nonfaulty nodes included in the polygon, and the result obtained is compared with the best existing known result. Results show that the proposed approach can not only find a set of minimum faulty polygons, but also does so quickly in terms of the number of rounds in the Distributed Solution.
-
on constructing the minimum orthogonal convex polygon in 2 d faulty meshes
International Parallel and Distributed Processing Symposium, 2004Co-Authors: Zhen JiangAbstract:Summary form only given. The rectangular faulty block model is the most commonly used fault model for designing fault-tolerant and deadlock-free routing algorithms in mesh-connected multicomputer. The convexity of a rectangle facilitates simple and efficient ways to route messages around fault regions using relatively few or no virtual channels to avoid deadlock. However, such a faulty block may include many nonfaulty nodes which are disabled, i.e., they are not involved in the routing process. Therefore, it is important to define a fault region that is convex and, at the same time, to include a minimum number of nonfaulty nodes. We propose an optimal Solution that can quickly construct a set of minimum faulty polygons, called orthogonal convex polygons, from a given set of faulty blocks in a 2-D mesh (or 2-D torus). The formation of orthogonal convex polygons is implemented using either a centralized or Distributed Solution. Both Solutions are based on the formation of faulty components each of which consists of adjacent faulty nodes only, followed by the addition of a minimum number of nonfaulty nodes to make each component a convex polygon. Extensive simulation has been done to determine the number of nonfaulty nodes included in the polygon, and the result obtained is compared with the best existing known result. Results show that the proposed approach can not only find a set of minimum faulty polygons but also does so quickly in terms of the number of rounds of information exchanges and updates between neighbors in the Distributed Solution.
Cosimo Antonio Prete - One of the best experts on this subject based on the ideXlab platform.
-
an architecture to integrate iec 61131 3 systems in an iec 61499 Distributed Solution
Computers in Industry, 2015Co-Authors: Stefano Campanelli, Pierfrancesco Foglia, Cosimo Antonio PreteAbstract:The paper presents a software architecture to integrate IEC-61131 and IEC-61499 modules in a DCS Solutions.The architecture permits to reuse IEC-61131 software.The architecture permits to maintain IEC-61499 advanced sw engineering concepts.A methodology on how to perform integration utilizing the architecture is presented via a case study.The architecture does not introduce significant performance overhead. The IEC 61499 standard has been developed to allow the modeling and design of Distributed control systems, providing advanced concepts of software engineering (such as abstraction and encapsulation) to the world of control engineering. The introduction of this standard in already existing control environments poses challenges, since programs written using the widespread IEC 61131-3 programming standard cannot be directly executed in a fully IEC 61499 environment without reengineering effort. In order to solve this problem, this paper presents an architecture to integrate modules of the two standards, allowing the exploitation of the benefits of both. The proposed architecture is based on the coexistence of control software of the two standards. Modules written in one standard interact with some particular interfaces that encapsulate functionalities and information to be exchanged with the other standard. In particular, the architecture permits to utilize available run-times without modification, it allows the reuse of software modules, and it utilizes existing features of the standards. A methodology to integrate IEC 61131-3 modules in an IEC 61499 Distributed Solution based on such architecture is also developed, and it is described via a case study to prove feasibility and benefits. Experimental results demonstrate that the proposed Solution does not add substantial load or delays to the system when compared to an IEC 61131-3 based Solution. By acting on task period, it can achieve performances similar to an IEC 61499 Solution.
-
An architecture to integrate IEC 61131-3 systems in an IEC 61499 Distributed Solution
Computers in Industry, 2015Co-Authors: Stefano Campanelli, Pierfrancesco Foglia, Cosimo Antonio PreteAbstract:The IEC 61499 standard has been developed to allow the modeling and design of Distributed control systems, providing advanced concepts of software engineering (such as abstraction and encapsulation) to the world of control engineering. The introduction of this standard in already existing control environments poses challenges, since programs written using the widespread IEC 61131-3 programming standard cannot be directly executed in a fully IEC 61499 environment without reengineering effort. In order to solve this problem, this paper presents an architecture to integrate modules of the two standards, allowing the exploitation of the benefits of both. The proposed architecture is based on the coexistence of control software of the two standards. Modules written in one standard interact with some particular interfaces that encapsulate functionalities and information to be exchanged with the other standard. In particular, the architecture permits to utilize available run-times without modification, it allows the reuse of software modules, and it utilizes existing features of the standards. A methodology to integrate IEC 61131-3 modules in an IEC 61499 Distributed Solution based on such architecture is also developed, and it is described via a case study to prove feasibility and benefits.\ud Experimental results demonstrate that the proposed Solution does not add substantial load or delays to the system when compared to an IEC 61131-3 based Solution. By acting on task period, it can achieve performances similar to an IEC 61499 Solution
Frank L Lewis - One of the best experts on this subject based on the ideXlab platform.
-
Cooperative optimal control for multi-agent systems on directed graph topologies
IEEE Transactions on Automatic Control, 2014Co-Authors: Kristian Hengster Movric, Frank L LewisAbstract:This note brings together stability and optimality theory to design Distributed cooperative control protocols that guarantee consensus and are globally optimal with respect to a positive semi-definite quadratic performance criterion. A common problem in cooperative optimal control is that global optimization problems generally require global information, which is not available to Distributed controllers. Optimal control for multi-agent systems is complicated by the fact that the communication graph topology interplays with the agent system dynamics. In the note we use an inverse optimality approach together with partial stability to consider the cooperative consensus and pinning control. Agents with identical linear time-invariant dynamics are considered. Communication graphs are assumed directed and having fixed topology. Structured quadratic performance indices are derived that capture the topology of the graph, which allows for global optimal control that is implemented using local Distributed protocols. A new class of digraphs is defined that admits a Distributed Solution to the global optimal control problem, namely those with simple graph Laplacian matrices.
-
Distributed Solution for the economic dispatch problem
Mediterranean Conference on Control and Automation, 2013Co-Authors: Giulio Binetti, Ali Davoudi, David Naso, Frank L Lewis, Mohammed I. Abouheaf, Biagio TurchianoAbstract:A Distributed approach for the economic dispatch of generating units is presented. It is assumed that the generators are connected by a communication graph. Each unit has information about itself, and can exchange information only with a few neighboring units in such a graph. Using graph theory and consensus algorithms, the proposed approach solves the economic dispatch problem in a Distributed manner instead of existing centralized approaches. The proposed Solution is shown to be optimal, independent of the initial power distribution, and to respond automatically to real-time load demand changes. Moreover, it requires only that the communication graph be connected. The effectiveness of the proposed algorithm is verified by simulating a standard IEEE test system.
Georgios B Giannakis - One of the best experts on this subject based on the ideXlab platform.
-
cross layer design of coded multicast for wireless random access networks
IEEE Journal on Selected Areas in Communications, 2011Co-Authors: Ketan Rajawat, Nikolaos Gatsis, Georgios B GiannakisAbstract:Joint optimization of network coding and Aloha-based medium access control (MAC) for multi-hop wireless networks is considered. The multicast throughput with a power consumption-related penalty is maximized subject to flow conservation and MAC achievable rate constraints to obtain the optimal transmission probabilities. The relevant optimization problem is inherently non-convex and hence difficult to solve even in a centralized manner. A successive convex approximation technique is employed to obtain a Karush-Kuhn-Tucker Solution. A separable problem structure is obtained and the dual decomposition technique is adopted to develop a Distributed Solution. The algorithm is thus applicable to large networks, and amenable to online implementation. Numerical tests verify performance and complexity advantages of the proposed approach over existing designs. A network simulation with implementation of random linear network coding shows performance very close to the one theoretically designed.
-
cross layer design of coded multicast for wireless random access networks
Conference on Information Sciences and Systems, 2011Co-Authors: Ketan Rajawat, Nikolaos Gatsis, Georgios B GiannakisAbstract:Joint optimization of network coding and Aloha-based medium access control (MAC) for multi-hop wireless networks is considered. The multicast throughput is maximized subject to flow conservation and MAC achievable rate constraints to obtain the optimal transmission probabilities. The resultant optimization problem is inherently non-convex and hence difficult to solve even in a centralized manner. A successive convex approximation technique is employed to obtain a Karush-Kuhn-Tucker Solution. A separable problem structure is obtained and the dual decomposition technique is adopted to develop a Distributed Solution. The algorithm is thus applicable to large networks, and amenable to online implementation. Numerical tests verify performance and complexity advantages of the proposed approach over existing designs.