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

Efficient Asynchronous Semi-Stochastic Block Coordinate Descent Methods for Large-Scale SVD

IEEE ACCESS 2021年 9卷 126159-126171页

作者： Shang, Fanhua Zhang, Zhihui Liu, Yuanyuan Liu, Hongying Xu, Jing Xidian Univ Sch Artificial Intelligence Minist Educ Key Lab Intelligent Percept & Image Understanding Xian 710071 Peoples R China Nankai Univ Coll Artificial Intelligence Tianjin 300350 Peoples R China

Eigenvector computation such as Singular Value Decomposition (SVD) is one of the most fundamental problems in machine learning, optimization and numerical linear algebra. In recent years, many stochastic variance reduction algorithms and randomized coordinate descent algorithms have been developed to efficiently solve the leading eigenvalue problem. By taking full advantage of both variance reduction and randomized coordinate descent techniques, this paper proposes a novel Semi-stochastic Block Coordinate Descent algorithm (SBCD-SVD), which is more suitable than existing algorithms for large-scale leading eigenvalue problems of SVD, and can obtain linear convergence. Unlike existing stochastic variance reduction and randomized coordinate descent methods, our algorithm inherits their advantages. Moreover, we propose a new Asynchronous parallel Semi-stochastic Block Coordinate Descent algorithm (ASBCD-SVD) and one new Asynchronous parallel Sparse approximated Variance Reduction algorithm (ASVR-SVD) for large-scale dense and sparse datasets, respectively. Finally, we prove that both dense and sparse asynchronous parallel variants can converge linearly. Extensive experimental results show that our algorithms attain high parallel speedup and achieve almost the same performance with significantly shorter time, and thus they can be widely used in various practice applications.

关键词： approximation algorithms Sparse matrices Convergence Eigenvalues and eigenfunctions Principal component analysis Matrix decomposition Symmetric matrices Singular value decomposition semi-stochastic gradient randomized coordinate descent asynchronous parallelism image compression

来源：评论

学校读者我要写书评

暂无评论

Matchings under distance constraints I

引用

ANNALS OF OPERATIONS RESEARCH 2021年第1-2期305卷 137-161页

作者： Madarasi, Peter Eotvos Lorand Univ Dept Operat Res Budapest Hungary

This paper introduces the d-distance matching problem, in which we are given a bipartite graph G = (S, T;E) with S = {s(1),..., s(n)}, a weight function on the edges and an integer d epsilon Z(+). The goal is to find a maximum-weight subset M subset of E of the edges satisfying the following two conditions: (i) the degree of every node of S is at most one in M, (ii) if s(i) t, s (j) t. M, then vertical bar j - i vertical bar= d. This question arises naturally, for example, in various scheduling problems. We show that the problem is NP-complete in general and admits a simple 3-approximation. We give an FPT algorithm parameterized by d and also showthat the casewhen the size of T is constant can be solved in polynomial time. From an approximability point of view, we show that the integrality gap of the natural integer programming model is at most 2- 1/2d-1, and give an LP-based approximation algorithm for the weighted case with the same guarantee. A combinatorial (2- 1/d)-approximation algorithm is also presented. Several greedy approaches are considered, and a local search algorithm is described that achieves an approximation ratio of 3/2 + epsilon for any constant epsilon > 0 in the unweighted case. The novel approaches used in the analysis of the integrality gap and the approximation ratio of locally optimal solutions might be of independent combinatorial interest.

关键词： Distance matching Restricted b-matching Constrained matching Scheduling Parameterized algorithms approximation algorithms Integrality gap

来源：评论

学校读者我要写书评

暂无评论

High-Dimensional Extension of the TICER Algorithm

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS I-REGULAR PAPERS 2021年第11期68卷 4722-4734页

作者： Hao, Limin Shi, Guoyong Shanghai Jiao Tong Univ Sch Elect Informat & Elect Engn Dept Micro Nano Elect Shanghai 200240 Peoples R China

The TICER (TIme-Constant Equilibration Reduction) algorithm is a well-known resistor-capacitor (RC) network reduction algorithm. It finds wide applications in integrated circuit post-layout simulation tools. However, the original algorithm is one-dimensional in that each step eliminates one circuit node to obtain an approximately equivalent circuit by connecting additional elements to the neighboring nodes after each elimination. This work extends the TICER algorithm to its high-dimensional version in the sense that each step eliminates a subcircuit as a whole to obtain an approximately equivalent circuit, again by connecting extra elements to the neighboring nodes after each elimination. In practice the high-dimensional TICER (HD-TICER) algorithm finds many advantages over the classical one-dimensional TICER (1D-TICER) algorithm, which is a special case of the HD-TICER algorithm. An elegant mathematical derivation of the HD-TICER algorithm is provided by applying the notion of driving point impedance (DPI). The advantages of the HD-TICER algorithm are demonstrated by application to reductions of some purely resistive networks and RC networks. An approximate time constant estimation method is also provided for selection of a subblock circuit to eliminate.

关键词： Integrated circuit modeling approximation algorithms Impedance Passive networks Capacitance Symmetric matrices Transfer functions Driving point impedance (DPI) model order reduction post-layout simulation realizable RC reduction time-constant equilibration reduction (TICER)

来源：评论

学校读者我要写书评

暂无评论

Faber Polynomial Based approximations of Nonlinear Integrators for Electrodynamics

引用

IEEE JOURNAL ON MULTISCALE AND MULTIPHYSICS COMPUTATIONAL TECHNIQUES 2021年 6卷 41-49页

作者： Kleene, Hendrik Luong, Tommy Schulz, Dirk Tech Univ Dortmund Chair High Frequency Tech D-44227 Dortmund Germany

Faber polynomial based approximations of time dependent exponential integrators for the numerical solution of Maxwell's equations based on explicit algorithms are extended for the inclusion of nonlinear media so that multiphysical problems can be considered. For this purpose, appropriate exponential integrators, such as Lawson type and Rosenbrock type integrators are reviewed and investigated. The formulation with regard to Rosenbrock type integrators is extended to develop exponential integrators allowing the straightforward implementation of the resulting explicit algorithm and the application of large time step sizes opening up the potential for a parallel implementation. The Faber polynomial based approach for the approximation of the exponential integrator is utilized and as in the case of linear material models has an order of magnitude higher efficiency than comparable conventional methods, especially, when a high accuracy is required.

关键词： Jacobian matrices Mathematical model approximation algorithms Electrodynamics Nonlinear systems Media Electromagnetic propagation Exponential integrators Faber polynomial based expansion nonlinear media time dependent electromagnetic propagation

来源：评论

学校读者我要写书评

暂无评论

A fast and differentiable optimization model for finding the minimum dominating set in large-scale graphs

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2023年 73卷

作者： Ding, Xiaojun Chen, Jianmei Qiu, Jie Yulin Normal Univ Sch Comp Sci & Engn Jiaoyu Rd Yulin 537000 Guangxi Peoples R China

The minimum dominating set is an important NP-hard problem in graph theory, widely used in various fields such as computer network layout and social networks. Although linear programming algorithms can obtain a global optimal solution on small graphs, they are not suitable for large graphs. To find a local optimal solution, many heuristic algorithms have been proposed. These algorithms require strong techniques and programming, and most of them still need improvement in performance on large graphs. This paper presents a cooperative- competitive model that transforms the discrete problem into a continuously differentiable problem. By using the gradient descent method, this approach can handle all vertices simultaneously, and its time complexity is linear. Compared to existing search algorithms, this method is based on a straightforward principle and is fast. For small graphs, it can achieve performance almost comparable to linear programming methods. For large graphs, this method can explore more diverse local optimal solutions in the same amount of time, making it easier to obtain better performance. In this paper, a comparison and analysis of this gradient-based algorithm and graph theory-based search algorithms are conducted on the minimum dominating set, allowing researchers to have a clearer understanding of the advantages and disadvantages of search algorithms and gradient methods in complex problems. The referenced search algorithms may potentially improve the gradient descent algorithm, leading to better solutions in other fields. At the same time, gradient-based methods can be used to solve many similar NP-hard problems in graph theory.

关键词： Minimum dominating set NP-hard problem Large-scale graphs approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

New graph algorithms via polyhedral techniques

引用

IT-INFORMATION TECHNOLOGY 2021年第3期63卷 177-182页

作者： Tarnawski, Jakub Microsoft Res Redmond WA 98052 USA

This article gives a short overview of my dissertation, where new algorithms are given for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. The first part of the dissertation addresses a benchmark problem in combinatorial optimization: the asymmetric traveling salesman problem (ATSP). It consists in finding the shortest tour that visits all vertices of a given edge-weighted directed graph. A.-approximation algorithm for ATSP is one that runs in polynomial time and always produces a tour at most. times longer than the shortest tour. Finding such an algorithm with constant rho had been a long-standing open problem. Here we give such an algorithm. The second part of the dissertation addresses the perfect matching problem. We have known since the 1980s that it has efficient parallel algorithms if the use of randomness is allowed. However, we do not know if randomness is necessary - that is, whether the matching problem is in the class NC. We show that it is in the class quasi-NC. That is, we give a deterministic parallel algorithm that runs in poly-logarithmic time on quasi-polynomially many processors.

关键词： graph algorithms traveling salesman problem perfect matching derandomization parallel algorithms approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Beep-and-Sleep: Message and Energy Efficient Set Cover

引用

THEORETICAL COMPUTER SCIENCE 2023年 950卷

作者： Goette, Thorsten Kolb, Christina Scheideler, Christian Werthmann, Julian Paderborn Univ Warburger Str 100 D-33098 Paderborn Germany Poolsterstrat 10 NL-7521 XG Enschede Netherlands

This article considers message and energy-efficient distributed algorithms for the SETCOVER Problem. Given a ground set U of n elements and a set S of m subsets of U, we aim to find the minimal number of these subsets that contain all elements. In the default distributed setup of this problem, each set has a bidirected communication link with each element it contains. This results in a communication graph with n + m nodes and degree A. The value A denotes the maximal degree of the communication graph, i.e., the maximum of all subsets' sizes and the maximum number of sets an element is contained *** present SETCOVER algorithm in the BEEPING model that only relies on carrier-sensing. In each synchronous time step, a node can either listen to the channel or beep. A listening node learns if one or more of its neighbors beeped or if none of its neighbors beeped. In particular, it neither learns which neighbors beeped nor how many neighbors beeped exactly. Given this model, we present an algorithm that runs in O(k3) time and has an expected approximation ratio of O (A3/k log2 A). The value k is an element of [3, log A] is a parameter that lets us trade runtime for approximation ratio similar to the celebrated algorithm by Kuhn and Wattenhofer [14]. Our next result is a O (k2) -time and O tilde (A12+1k (n +m)) -message algorithm (where O tilde (middot) hides polylogarithmic factors) with expected approximation ratio of O (A k log A) in the K T0-CONGEST model. In this variant of the well-known CONGEST model, 1 time proceeds in synchronous rounds, and each node can send a distinct message of size O (log (n + m)) to each of its neighbors. Further, each node has a unique identifier of size O (log (n + m)). However, the crucial aspect of K T0-CONGEST is that the nodes do not know their neighbors' identifiers. Our algorithm is almost optimal concerning time and message complexity as we can show that there are hard instances that require S2(A12 -Em) messages for a constant appr

关键词： Set cover approximation algorithms Beeping model K T0 model

来源：评论

学校读者我要写书评

暂无评论

On the Use of Difference of Log-Sum-Exp Neural Networks to Solve Data-Driven Model Predictive Control Tracking Problems

引用

IEEE CONTROL SYSTEMS LETTERS 2021年第4期5卷 1267-1272页

作者： Brueggemann, Sven Possieri, Corrado Univ Calif San Diego Mech & Aerosp Engn Dept La Jolla CA 92093 USA Consiglio Nazl Ric IASI CNR Ist Anal Sistemi & Informat A Ruberti I-00185 Rome Italy

We employ Difference of Log-Sum-Exp neural networks to generate a data-driven feedback controller based on Model Predictive Control (MPC) to track a given reference trajectory. By using this class of networks to approximate the MPC-related cost function subject to the given system dynamics and input constraint, we avoid two of the main bottlenecks of classical MPC: the availability of an accurate model for the system being controlled, and the computational cost of solving the MPC-induced optimization problem. The former is tackled by exploiting the universal approximation capabilities of this class of networks. The latter is alleviated by making use of the difference-of-convex-functions structure of these networks. Furthermore, we show that the system driven by the MPC-neural structure is practically stable.

关键词： Computational modeling Artificial neural networks Trajectory Optimization approximation algorithms Predictive control Predictive control for nonlinear systems neural networks optimal control uncertain systems

来源：评论

学校读者我要写书评

暂无评论

Super oriented cycles in permutations

引用

COMPUTERS IN BIOLOGY AND MEDICINE 2023年 165卷 107426-107426页

作者： Jayakumar, P. Chitturi, Bhadrachalam Amrita Vishwa Vidyapeetham Dept Comp Sci & Applicat Amritapuri India Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

The degree of dissimilarity between genome sequences of homologous species is a measure of the evolutionary distance between them. It serves as a metric in the construction of phylogenetic trees, which depict the evolutionary relationships and common ancestry among different species. Given two genome sequences, evolutionary distance is determined by estimating the number of global mutations that transform one sequence to the other. The computation of the evolutionary distance is done by modelling a genome with the corresponding permutation. Global rearrangement operations such as transposition that model a particular genomic mutation are studied by employing a combinatorial structure known as a cycle graph of the corresponding permutation. A cycle in a cycle graph that has odd length is called an odd cycle. In the context of the problem of sorting by transpositions (SBT), a valid 2-move is a transposition that increases the number of odd cycles in the cycle graph by two. A super oriented cycle (SOC) is an odd cycle C where C and one of the resultant cycles admit valid 2-moves. The minimum number of mutations required to transform a species S into a related species T is the distance from S to T under that mutation. Christie opined that characterizing SOCs will improve the lower bound of the transposition distance. We characterize super oriented cycles. Equivalent transformations on permutations like reduction and (g,b)-split preserve the transposition distance of a given permutation and map SBT to the corresponding SBT on a transformed simpler permutation. We introduce merge, a novel equivalent transformation. These results have applications in computing transposition and other distances between related species.

关键词： approximation algorithms Mutations Permutations Sorting Super oriented cycles Transpositions Upper bound

来源：评论

学校读者我要写书评

暂无评论

Efficient Expectation Propagation Massive MIMO Detector With Neumann-Series approximation

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS 2020年第10期67卷 1924-1928页

作者： Tan, Xiaosi Xu, Weihong Zhang, Yaping Zhang, Zaichen You, Xiaohu Zhang, Chuan Southeast Univ LEADS Nanjing 210096 Peoples R China Southeast Univ Natl Mobile Commun Res Lab Nanjing 210096 Peoples R China Southeast Univ Quantum Informat Ctr Nanjing 210096 Peoples R China Purple Mt Labs Nanjing 210096 Peoples R China

Expectation propagation (EP) attains near-optimal performance for massive multiple-input multiple-output (MIMO) detection. However, the inevitable matrix inversions and exponentiations at each EP iteration bring great challenges to realistic hardware implementation. To address these issues, a low-complexity EP with iterative Neumann-series approximation (EP-INSA) detector is proposed by employing INSA to estimate the inverse matrices. Further approximations are applied to avoid the exponentiations, which makes EP-INSA an efficient, feasible, and hardware-friendly detector for massive MIMO with various modulations. Simulation results show that EP-INSA attains similar performance as exact EP with only a few INSA terms, which assures enhanced performance and complexity trade-off. The associated hardware architectures of EP-INSA detector are also presented. The implementation results on 65 nm CMOS technology show that our design yields a throughput of 0.62 Gb/s with 2.63x area efficiency of existing EP detector.

关键词： Detectors Complexity theory approximation algorithms Modulation Massive MIMO Circuits and systems Massive MIMO expectation propagation iterative Neumann-series approximation hardware implementation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：