論文の概要: 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の有用性をさらに裏付けるものである。

関連論文リスト

• On Robust Numerical Solver for ODE via Self-Attention Mechanism [82.95493796476767]
  我々は,内在性雑音障害を緩和し,AIによって強化された数値解法を,データサイズを小さくする訓練について検討する。 まず,教師付き学習における雑音を制御するための自己認識機構の能力を解析し,さらに微分方程式の数値解に付加的な自己認識機構を導入し,簡便かつ有効な数値解法であるAttrを提案する。
  論文  参考訳（メタデータ） (2023-02-05T01:39:21Z)
• Self-averaging of digital memcomputing machines [4.429709236737154]
  DMM(Digital memcomputing Machine)は、メモリを持つ非量子力学系を用いて最適化問題を解決する新しいタイプの計算機である。 DMMの解法時間(TTS)は逆ガウス分布に従っており、TTSは問題サイズを増大させる。 本研究では,この現象の解析的理解と3-SAT問題の解法による数値的エビデンスを提供する。
  論文  参考訳（メタデータ） (2023-01-20T20:09:05Z)
• Algorithms for perturbative analysis and simulation of quantum dynamics [0.0]
  我々はダイソン級数とマグナス展開の両方を計算・利用するための汎用アルゴリズムを開発した。 モデルパラメータ空間の領域における忠実度を近似するためにこれらのツールの使い方を実証する。 計算前のステップを,元法よりも少ない項数で多変数展開問題と表現できることを示す。
  論文  参考訳（メタデータ） (2022-10-20T21:07:47Z)
• 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)
• PI-VAE: Physics-Informed Variational Auto-Encoder for stochastic differential equations [2.741266294612776]
  我々は、物理学インフォームド・ニューラルネットワーク(PI-VAE)と呼ばれる新しいタイプの物理インフォームド・ニューラルネットワークを提案する。 PI-VAEは、システム変数とパラメータのサンプルを生成する変分オートエンコーダ(VAE)で構成されている。 提案手法の精度と効率を,物理インフォームド生成対向ネットワーク (PI-WGAN) と比較して数値的に検証した。
  論文  参考訳（メタデータ） (2022-03-21T21:51:19Z)
• 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)

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

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