.png){kind=icon}
返回
Accelerating numerical simulation of continuous-time Boolean satisfiability solver using discrete gradient
.png){kind=icon}
OA
AI
DOI：10.1016/j.cnsns.2021.105908.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
To explore the design of analog computing devices, modeling the problem-solving process as a continuous-time dynamical system is important. Ercsey-Ravasz and Toroczkai [Nature Physics 7, 966 (2011)] proposed such a model for solving the Boolean satisfiability (SAT) problem. This system consists of a gradient system that minimizes the potential function reduced from the SAT problem and a system for achieving a temporal variation of the po-tential function to avoid the problem of non-solution local minima. Although the ability of the system to find a solution to the SAT problem is demonstrated, its large simulation cost hinders theoretical research towards the physical realization and limits its utility on digital computers. This is due to the necessity of small time steps to maintain the numerical sta-bility of the simulation. In this study, we propose a fast and stable numerical simulation algorithm for this solver using the discrete gradient method to allow a larger time step. We also propose an adaptive time step control method for this system. The proposed algo-rithm achieves a faster simulation by a factor of approximately 100, compared to conven-tional methods. Although taking a large time step degrades the accuracy, we found that it does not necessarily degrade the performance as a SAT solver; this indicates the new util-ity of the discrete gradient apart from the conventional studies of numerical simulation algorithms that pursue accuracy as well as efficiency. (c) 2021 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license ( http://creativecommons.org/licenses/by/4.0/ )
Keyword:
Boolean satisfiability problem
Continuous-time SAT solver
Discrete gradient
Adaptive step size
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.8
论文数:
9.2K
被引数:
1.8W
机构
引用论文
分享收藏The properties of Bi-2223 precursor powders ground by fluid energy comminuting由流体能研磨制备的Bi-2223前驱体粉末的性质
PREAI
分享收藏THE ZIG-ZAG PROCESS AND SUPER-EFFICIENT SAMPLING FOR BAYESIAN ANALYSIS OF BIG DATA.png)
ANNALS OF STATISTICSOAAI
ANNALS OF STATISTICSIF3.7
OAAI分享收藏分享收藏The Bouncy Particle Sampler: A Nonreversible Rejection-Free Markov Chain Monte Carlo Method有弹性粒子采样器: 一种不可逆的无排斥马尔可夫链蒙特卡罗方法OAAI
OAAI分享收藏Geometric integration using discrete gradientsPHILOSOPHICAL TRANSACTIONS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES
PHILOSOPHICAL TRANSACTIONS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCESIF3.7
PREAI
分享收藏
查看更多内容