論文の概要: Automatic Solver Generator for Systems of Laurent Polynomial Equations
- arxiv url: http://arxiv.org/abs/2307.00320v1
- Date: Sat, 1 Jul 2023 12:12:52 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-05 16:43:15.648164
- Title: Automatic Solver Generator for Systems of Laurent Polynomial Equations
- Title（参考訳）: ローラン多項式方程式系のための自動解法生成器
- Authors: Evgeniy Martyushev, Snehal Bhayani, Tomas Pajdla
- Abstract要約: 同じ単項構造であるが様々な係数を持つ三角系(ローラン系)が与えられたとき、任意の族に対する解をできるだけ早く計算する解法を見つける。
ローラン方程式系に対する自動解法生成器を提案する。
- 参考スコア（独自算出の注目度）: 1.7188280334580197
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In computer vision applications, the following problem often arises: Given a
family of (Laurent) polynomial systems with the same monomial structure but
varying coefficients, find a solver that computes solutions for any family
member as fast as possible. Under appropriate genericity assumptions, the
dimension and degree of the respective polynomial ideal remain unchanged for
each particular system in the same family. The state-of-the-art approach to
solving such problems is based on elimination templates, which are the
coefficient (Macaulay) matrices that encode the transformation from the initial
polynomials to the polynomials needed to construct the action matrix. Knowing
an action matrix, the solutions of the system are computed from its
eigenvectors. The important property of an elimination template is that it
applies to all polynomial systems in the family. In this paper, we propose a
new practical algorithm that checks whether a given set of Laurent polynomials
is sufficient to construct an elimination template. Based on this algorithm, we
propose an automatic solver generator for systems of Laurent polynomial
equations. The new generator is simple and fast; it applies to ideals with
positive-dimensional components; it allows one to uncover partial $p$-fold
symmetries automatically. We test our generator on various minimal problems,
mostly in geometric computer vision. The speed of the generated solvers exceeds
the state-of-the-art in most cases. In particular, we propose the solvers for
the following problems: optimal 3-view triangulation, semi-generalized hybrid
pose estimation and minimal time-of-arrival self-calibration. The experiments
on synthetic scenes show that our solvers are numerically accurate and either
comparable to or significantly faster than the state-of-the-art solvers.
- Abstract（参考訳）: コンピュータビジョンの応用において、以下の問題がしばしば生じている: 同じ単項構造を持つ(ローラン)多項式系の族が様々な係数を持つと、任意のファミリーメンバーの解をできるだけ早く計算する解法を見つける。
適切な一般性仮定の下では、各多項式イデアルの次元と次数は、同じ族の各特定の系に対して変わらない。
このような問題を解決するための最先端のアプローチは、初期多項式から作用行列を構成するために必要な多項式への変換を符号化する係数(マクロ行列)である除去テンプレートに基づいている。
作用行列を知れば、系の解はその固有ベクトルから計算される。
削除テンプレートの重要な特性は、族内のすべての多項式系に適用できる点である。
本稿では,ローラン多項式の与えられた集合が削除テンプレートを構築するのに十分かどうかをチェックする新しい実用的アルゴリズムを提案する。
このアルゴリズムに基づき,ローラン多項式方程式系に対する自動解法生成器を提案する。
新しいジェネレータは単純で高速であり、正次元成分を持つイデアルに適用できる。
我々は、主に幾何学的コンピュータビジョンにおいて、様々な最小限の問題でジェネレータをテストする。
生成したソルバの速度は、ほとんどの場合最先端を超える。
特に, 3次元三角測量の最適解法, 半一般化ハイブリッドポーズ推定法, 最小時間分割法を提案する。
合成シーンにおける実験により,我々の解法は数値的に正確であり,最先端の解法と同等か極めて高速であることが示された。
関連論文リスト
- Online Stability Improvement of Groebner Basis Solvers using Deep
Learning [29.805408457645886]
異なる変数や単項順序が異なる消去テンプレートにつながることを示す。
次に、元の係数の集合が、優れた解法の選択を訓練するのに十分な情報を含むことを証明した。
論文 参考訳（メタデータ） (2024-01-17T16:51:28Z) - Bauer's Spectral Factorization Method for Low Order Multiwavelet Filter
Design [0.6138671548064355]
本稿では,Bauer$'$s法に基づく行列スペクトルの高速分解法を提案する。
バウアー法を非線形行列方程式(NME)に変換する
NMEは2つの異なる数値アルゴリズムによって解決される。
論文 参考訳（メタデータ） (2023-12-09T00:26:52Z) - Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes [70.52097560486683]
我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。
特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
論文 参考訳（メタデータ） (2023-11-18T04:41:07Z) - An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。
このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。
本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-09-30T15:57:14Z) - CoLA: Exploiting Compositional Structure for Automatic and Efficient
Numerical Linear Algebra [62.37017125812101]
機械学習における大規模線形代数問題に対して, CoLA という, 単純だが汎用的なフレームワークを提案する。
線形演算子抽象と合成ディスパッチルールを組み合わせることで、CoLAはメモリと実行時の効率的な数値アルゴリズムを自動的に構築する。
偏微分方程式,ガウス過程,同変モデル構築,教師なし学習など,幅広い応用で有効性を示す。
論文 参考訳（メタデータ） (2023-09-06T14:59:38Z) - A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium [0.3749861135832073]
我々は,少なくとも1つの解を持つシステム向けに設計されたMultiというアルゴリズムで,この戦略を実装した。
我々は,最大ステップ数のマルチステップ戦略を用いることで,Multiの最適複雑性が達成されることを証明し,その結果,単一のステップからなる戦略である標準的な推測・決定戦略が最悪の選択であることを示す。
論文 参考訳（メタデータ） (2023-04-16T16:09:14Z) - Sparse resultant based minimal solvers in computer vision and their
connection with the action matrix [17.31412310131552]
いくつかのカメラ幾何問題に対して、我々の余剰手法は、最先端のGrobnerベースベースの解法よりも小さく、より安定な解法をもたらすことを示した。
コンピュータビジョンにおける最小限の問題に対して、一般的なベースベースの方法に代わる競争力のある代替手段を提供する。
論文 参考訳（メタデータ） (2023-01-16T14:25:19Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector
Problems [78.95866278697777]
本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。
次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
論文 参考訳（メタデータ） (2021-03-24T23:11:32Z) - GAPS: Generator for Automatic Polynomial Solvers [39.33174230839823]
異なる係数のインスタンスで繰り返されるシステムを考えると、従来のGr"オブナー基底または正規形式ベースの解は非常に非効率である。
このような構造をオフラインでプリ計算することで、Gr"オブナーベースとシステムソリューションをオンライン上で自動的に効率よく解決することができる。
Larssonらによる最新のツールオートゲンは、解決効率の最先端性能を持つこれらのツールの代表である。
論文 参考訳（メタデータ） (2020-04-24T14:11:28Z) - SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
SURFは分布を断片的に近似するアルゴリズムである。
実験では最先端のアルゴリズムよりも優れています。
論文 参考訳（メタデータ） (2020-02-22T01:03:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。