論文の概要: Optimizing and benchmarking the computation of the permanent of general matrices
- arxiv url: http://arxiv.org/abs/2510.03421v1
- Date: Fri, 03 Oct 2025 18:32:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-07 16:52:59.035782
- Title: Optimizing and benchmarking the computation of the permanent of general matrices
- Title（参考訳）: 一般行列の永久性計算の最適化とベンチマーク
- Authors: Cassandra Masschelein, Michelle Richer, Paul W. Ayers,
- Abstract要約: 行列の永久性を評価することは、多くの領域に現れる基本的な計算である。
永続性を計算するのに最も効率的なアルゴリズムを自動で利用するソフトウェアは公開されていない。
本研究では,任意の矩形行列の永久性を評価するソフトウェアパッケージの設計,開発,評価を行った。
- 参考スコア（独自算出の注目度）: 11.873893621488527
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Evaluating the permanent of a matrix is a fundamental computation that emerges in many domains, including traditional fields like computational complexity theory, graph theory, many-body quantum theory and emerging disciplines like machine learning and quantum computing. While conceptually simple, evaluating the permanent is extremely challenging: no polynomial-time algorithm is available (unless $\textsc{P} = \textsc{NP}$). To the best of our knowledge there is no publicly available software that automatically uses the most efficient algorithm for computing the permanent. In this work we designed, developed, and investigated the performance of our software package which evaluates the permanent of an arbitrary rectangular matrix, supporting three algorithms generally regarded as the fastest while giving the exact solution (the straightforward combinatoric algorithm, the Ryser algorithm, and the Glynn algorithm) and, optionally, automatically switching to the optimal algorithm based on the type and dimensionality of the input matrix. To do this, we developed an extension of the Glynn algorithm to rectangular matrices. Our free and open-source software package is distributed via Github, at https://github.com/theochem/matrix-permanent.
- Abstract（参考訳）: 行列の永久性を評価することは、計算複雑性理論、グラフ理論、多体量子理論、機械学習や量子コンピューティングといった新しい分野を含む多くの領域で現れる基本的な計算である。
多項式時間アルゴリズムは利用できない($\textsc{P} = \textsc{NP}$でない限り)。
私たちの知る限り、永続性を計算するのに最も効率的なアルゴリズムを自動で利用するソフトウェアは、公開されていない。
本研究は,任意の矩形行列の永久性を評価するソフトウェアパッケージの設計,開発,検討を行い,正確な解(単純なコンビネータアルゴリズム,ライザアルゴリズム,グリンアルゴリズム)を与えながら,一般に最速と見なされる3つのアルゴリズムをサポートし,任意に入力行列の型と次元性に基づいて最適なアルゴリズムに自動的に切り替える。
そこで我々は,Glynnアルゴリズムを矩形行列に拡張する手法を開発した。
当社のフリーかつオープンソースソフトウェアパッケージはGithub経由で,https://github.com/theochem/matrix-permanent.comで配布しています。
関連論文リスト
- Improving Algorithmic Efficiency using Cryptography [11.496343300483904]
計算問題を解く際の時間的複雑さを改善するために暗号を用いる方法を示す。
標準的な暗号仮定の下では、既存のアルゴリズムよりも決定的に高速なアルゴリズムを設計できることを示す。
論文 参考訳（メタデータ） (2025-02-18T17:08:59Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
エルミート行列の最小固有値を求める量子アルゴリズムについて述べる。
このアルゴリズムは、量子位相推定と量子振幅推定を組み合わせて、2次高速化を実現する。
また、同じランタイムで同様のアルゴリズムを提供し、行列の低エネルギー部分空間に主に置かれる量子状態の準備を可能にします。
論文 参考訳（メタデータ） (2023-11-07T22:52:56Z) - Learning the Positions in CountSketch [49.57951567374372]
本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。
本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-06-11T07:28:35Z) - Block-encoding dense and full-rank kernels using hierarchical matrices:
applications in quantum numerical linear algebra [6.338178373376447]
本稿では,量子コンピュータ上の階層行列構造のブロック符号化方式を提案する。
我々の手法は、次元$N$から$O(kappa operatornamepolylog(fracNvarepsilon))$の量子線型系を解くランタイムを改善することができる。
論文 参考訳（メタデータ） (2022-01-27T05:24:02Z) - Fundamental Machine Learning Routines as Quantum Algorithms on a
Superconducting Quantum Computer [0.0]
Harrow-Hassidim-Lloydアルゴリズムは、量子デバイス上の線形方程式のシステムを解くことを目的としている。
本稿では,これらの特徴が完全に一致しない場合のアルゴリズムの性能に関する数値的研究を行う。
論文 参考訳（メタデータ） (2021-09-17T15:22:06Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z) - What if Neural Networks had SVDs? [66.91160214071088]
様々なニューラルネットワークでは、行列反転のような時間を要する行列演算を採用している。
本稿では,行列演算を高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-29T12:58:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。