論文の概要: Directed percolation and numerical stability of simulations of digital memcomputing machines

• arxiv url: http://arxiv.org/abs/2102.03547v2
• Date: Wed, 31 Mar 2021 16:41:46 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-12 11:30:09.253299
• Title: Directed percolation and numerical stability of simulations of digital memcomputing machines
• Title（参考訳）: ディジタルmem計算機の数値シミュレーションにおける有向パーコレーションと数値安定性
• Authors: Yuan-Hang Zhang, Massimiliano Di Ventra
• Abstract要約: DMM(Digital memcomputing Machine)は、最適化問題を解決するために設計された新しい非解決型マシンである。 これらのマシンは、メモリを持つ連続時間非量子力学系で物理的に実現することができる。 多くの困難問題の解は、DMMのODEを数値的に統合することによって報告されている。
• 参考スコア（独自算出の注目度）: 8.761355402590105
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Digital memcomputing machines (DMMs) are a novel, non-Turing class of machines designed to solve combinatorial optimization problems. They can be physically realized with continuous-time, non-quantum dynamical systems with memory (time non-locality), whose ordinary differential equations (ODEs) can be numerically integrated on modern computers. Solutions of many hard problems have been reported by numerically integrating the ODEs of DMMs, showing substantial advantages over state-of-the-art solvers. To investigate the reasons behind the robustness and effectiveness of this method, we employ three explicit integration schemes (forward Euler, trapezoid and Runge-Kutta 4th order) with a constant time step, to solve 3-SAT instances with planted solutions. We show that, (i) even if most of the trajectories in the phase space are destroyed by numerical noise, the solution can still be achieved; (ii) the forward Euler method, although having the largest numerical error, solves the instances in the least amount of function evaluations; and (iii) when increasing the integration time step, the system undergoes a "solvable-unsolvable transition" at a critical threshold, which needs to decay at most as a power law with the problem size, to control the numerical errors. To explain these results, we model the dynamical behavior of DMMs as directed percolation of the state trajectory in the phase space in the presence of noise. This viewpoint clarifies the reasons behind their numerical robustness and provides an analytical understanding of the unsolvable-solvable transition. These results land further support to the usefulness of DMMs in the solution of hard combinatorial optimization problems.
• Abstract（参考訳）: digital memcomputing machines (dmms) は、組合せ最適化問題を解決するために設計された新しい非チューリング機械である。 これらは、通常の微分方程式(ODE)を現代のコンピュータに数値的に組み込むことができるメモリ(時間非局所性)を持つ連続時間非量子力学系で物理的に実現することができる。 多くの困難問題の解法は、DMMのODEを数値的に統合することによって報告され、最先端の解法に対して大きな優位性を示している。 本手法のロバスト性と有効性を検討するために,3つの明示的な統合スキーム (euler, trapezoid, runge-kutta 4-order) を一定の時間ステップで採用し,3-satインスタンスを植込み解で解く。 私たちはそれを示します。 (i)位相空間におけるほとんどの軌道が数値ノイズによって破壊されても、解は得られない。 (ii)フォワードオイラー法は最大の数値誤差を持つが、最小限の関数評価で問題を解く。 3) 積分時間ステップを増大させると, 限界しきい値において「解けない遷移」を行い, 数値誤差を制御するためには, 最大でも問題の大きさの電力法則として崩壊する必要がある。 これらの結果を説明するために,DMMの動的挙動をノイズの存在下での位相空間における状態軌道の直接パーコレーションとしてモデル化する。 この視点は、その数値的強固さの背後にある理由を明確にし、解けない遷移を解析的に理解する。 これらの結果は、ハード組合せ最適化問題の解法におけるDMMの有用性をさらに裏付けるものである。

関連論文リスト

• A Constant Velocity Latent Dynamics Approach for Accelerating Simulation of Stiff Nonlinear Systems [0.0]
  厳密な常微分方程式(StODE)を解くには洗練された数値解法が必要であるが、しばしば計算コストがかかる。 本研究では,StODEの潜在力学を学習し,数値積分を完全に回避する手法を提案する。 言い換えれば、元の力学の解は一連の直線に符号化され、それを復号して実際の解を必要な時に取り出すことができる。
  論文  参考訳（メタデータ） (2025-01-14T20:32:31Z)
• Enhancing Low-Order Discontinuous Galerkin Methods with Neural Ordinary Differential Equations for Compressible Navier--Stokes Equations [0.1578515540930834]
  圧縮可能なNavier-Stokes方程式を解くためのエンドツーエンドの微分可能なフレームワークを提案する。 この統合アプローチは、微分可能不連続なガレルキン解法とニューラルネットワークのソース項を組み合わせる。 提案するフレームワークの性能を2つの例で示す。
  論文  参考訳（メタデータ） (2023-10-29T04:26:23Z)
• Self-averaging of digital memcomputing machines [4.429709236737154]
  DMM(Digital memcomputing Machine)は、メモリを持つ非量子力学系を用いて最適化問題を解決する新しいタイプの計算機である。 DMMの解法時間(TTS)は逆ガウス分布に従っており、TTSは問題サイズを増大させる。 本研究では,この現象の解析的理解と3-SAT問題の解法による数値的エビデンスを提供する。
  論文  参考訳（メタデータ） (2023-01-20T20:09:05Z)
• Tunable Complexity Benchmarks for Evaluating Physics-Informed Neural Networks on Coupled Ordinary Differential Equations [64.78260098263489]
  本研究では,より複雑に結合した常微分方程式(ODE)を解く物理インフォームドニューラルネットワーク(PINN)の能力を評価する。 PINNの複雑性が増大するにつれて,これらのベンチマークに対する正しい解が得られないことが示される。 PINN損失のラプラシアンは,ネットワーク容量の不足,ODEの条件の低下,局所曲率の高さなど,いくつかの理由を明らかにした。
  論文  参考訳（メタデータ） (2022-10-14T15:01:32Z)
• Semi-supervised Learning of Partial Differential Operators and Dynamical Flows [68.77595310155365]
  本稿では,超ネットワーク解法とフーリエニューラル演算子アーキテクチャを組み合わせた新しい手法を提案する。 本手法は, 1次元, 2次元, 3次元の非線形流体を含む様々な時間発展PDEを用いて実験を行った。 その結果、新しい手法は、監督点の時点における学習精度を向上し、任意の中間時間にその解を補間できることを示した。
  論文  参考訳（メタデータ） (2022-07-28T19:59:14Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Message Passing Neural PDE Solvers [60.77761603258397]
  我々は、バックプロップ最適化されたニューラル関数近似器で、グラフのアリーデザインのコンポーネントを置き換えるニューラルメッセージパッシング解決器を構築した。 本稿では, 有限差分, 有限体積, WENOスキームなどの古典的手法を表現的に含んでいることを示す。 本研究では, 異なる領域のトポロジ, 方程式パラメータ, 離散化などにおける高速, 安定, 高精度な性能を, 1次元, 2次元で検証する。
  論文  参考訳（メタデータ） (2022-02-07T17:47:46Z)
• Stable Implementation of Probabilistic ODE Solvers [27.70274403550477]
  常微分方程式(odes)の確率的解法は、数値の不確かさの効率的な定量化をもたらす。 それらは高い順序でまたは小さいステップ サイズと動くとき数値不安定に苦しみます。 本研究は,この問題に対する解決策を提案し,検討する。 正確な初期化、数値安定性をステップサイズ非依存にする座標変更事前条件、平方根実装の3つのコンポーネントを含んでいる。
  論文  参考訳（メタデータ） (2020-12-18T08:35:36Z)
• Fast and differentiable simulation of driven quantum systems [58.720142291102135]
  我々は、ダイソン展開に基づく半解析手法を導入し、標準数値法よりもはるかに高速に駆動量子系を時間発展させることができる。 回路QEDアーキテクチャにおけるトランスモン量子ビットを用いた2量子ゲートの最適化結果を示す。
  論文  参考訳（メタデータ） (2020-12-16T21:43:38Z)
• Efficient Solution of Boolean Satisfiability Problems with Digital MemComputing [0.0]
  メモリアシスト物理系はSAT問題を連続的に効率的に解くことができることを示す。 シミュレーションの効率は、元の物理系の集合力学特性と関係している。 我々は、物理学に着想を得た計算パラダイムの研究の方向性を広げることを期待している。
  論文  参考訳（メタデータ） (2020-11-12T18:13:46Z)
• Large-scale Neural Solvers for Partial Differential Equations [48.7576911714538]
  偏微分方程式 (PDE) を解くことは、多くのプロセスがPDEの観点でモデル化できるため、科学の多くの分野において不可欠である。 最近の数値解法では、基礎となる方程式を手動で離散化するだけでなく、分散コンピューティングのための高度で調整されたコードも必要である。 偏微分方程式, 物理インフォームドニューラルネットワーク(PINN)に対する連続メッシュフリーニューラルネットワークの適用性について検討する。 本稿では,解析解に関するGatedPINNの精度と,スペクトル解法などの最先端数値解法について論じる。
  論文  参考訳（メタデータ） (2020-09-08T13:26:51Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。