論文の概要: Factorization-in-Loop: Proximal Fill-in Minimization for Sparse Matrix Reordering

• arxiv url: http://arxiv.org/abs/2511.09093v1
• Date: Thu, 13 Nov 2025 01:31:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-13 22:34:54.407929
• Title: Factorization-in-Loop: Proximal Fill-in Minimization for Sparse Matrix Reordering
• Title（参考訳）: Factorization-in-Loop: Sparse Matrix Reorderingのための近位フィルイン最小化
• Authors: Ziwei Li, Shuzi Niu, Tao Yuan, Huiyuan Li, Wenjia Wu,
• Abstract要約: 我々は,行列の三角要素を最小化し,フィインの正確な数を近似することにより,リオーダーネットワークを学習する。 勾配に基づく最適化では、予測ノードスコアと最適化対象の三角要素との間に大きなギャップがある。 ベンチマークスパース行列収集スイートSparseの実験結果から,提案手法の補充数とLU分解時間の削減率は,最先端のベースラインと比較して20%と17.8%であった。
• 参考スコア（独自算出の注目度）: 9.46982964997944
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Fill-ins are new nonzero elements in the summation of the upper and lower triangular factors generated during LU factorization. For large sparse matrices, they will increase the memory usage and computational time, and be reduced through proper row or column arrangement, namely matrix reordering. Finding a row or column permutation with the minimal fill-ins is NP-hard, and surrogate objectives are designed to derive fill-in reduction permutations or learn a reordering function. However, there is no theoretical guarantee between the golden criterion and these surrogate objectives. Here we propose to learn a reordering network by minimizing \(l_1\) norm of triangular factors of the reordered matrix to approximate the exact number of fill-ins. The reordering network utilizes a graph encoder to predict row or column node scores. For inference, it is easy and fast to derive the permutation from sorting algorithms for matrices. For gradient based optimization, there is a large gap between the predicted node scores and resultant triangular factors in the optimization objective. To bridge the gap, we first design two reparameterization techniques to obtain the permutation matrix from node scores. The matrix is reordered by multiplying the permutation matrix. Then we introduce the factorization process into the objective function to arrive at target triangular factors. The overall objective function is optimized with the alternating direction method of multipliers and proximal gradient descent. Experimental results on benchmark sparse matrix collection SuiteSparse show the fill-in number and LU factorization time reduction of our proposed method is 20% and 17.8% compared with state-of-the-art baselines.
• Abstract（参考訳）: フィルイン(Fill-in)は、LU因子化時に生じる上下三角形の因子の和における新しい非ゼロ元素である。 大きなスパース行列の場合、メモリ使用量と計算時間が増加し、適切な行や列アレンジメント、すなわち行列のリオーダーによって削減される。 最小のフィインで行や列の置換を見つけることはNPハードであり、サロゲート目的は、フィイン還元置換を導出したり、再順序関数を学ぶように設計されている。 しかし、金の基準とこれらの代理目的の間に理論的保証はない。 ここでは, 行列の三角要素の基準である \(l_1\) を最小化し, フィインの正確な数を近似することにより, 再順序ネットワークの学習を提案する。 リオーダーネットワークは、グラフエンコーダを使用して行または列ノードのスコアを予測する。 推論のために、行列のソートアルゴリズムから置換を導出するのは簡単かつ高速である。 勾配に基づく最適化では、予測ノードスコアと最適化対象の三角要素との間に大きなギャップがある。 このギャップを埋めるために、まず2つのパラメータ化手法を設計し、ノードスコアから置換行列を得る。 行列は置換行列を乗算して再順序付けされる。 次に,対象の三角要素に到達するための因子化過程を対象関数に導入する。 全体目的関数は乗算器の交互方向法と近位勾配降下法で最適化される。 ベンチマークスパース行列収集スイートSparseの実験結果から,提案手法の補充数とLU分解時間の削減率は,最先端のベースラインと比較して20%と17.8%であった。

関連論文リスト

• Diff-PCR: Diffusion-Based Correspondence Searching in Doubly Stochastic Matrix Space for Point Cloud Registration [0.8287206589886881]
  最先端の手法では、ソリューションを洗練させるためにRAFTのような反復的な更新が採用されている。 本稿では,最適マッチング行列の探索を予測するために,Denoising Diffusion Modelを利用する新しい手法を提案する。 提案手法は,オンラインバックボーンやホワイトノイズによって提供される任意の初期マッチング行列から検索を開始することで,柔軟性を提供する。
  論文  参考訳（メタデータ） (2023-12-31T09:24:28Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Matrix Reordering for Noisy Disordered Matrices: Optimality and Computationally Efficient Algorithms [9.245687221460654]
  単細胞生物学とメダゲノミクスの応用により,ノイズモノトンToeplitz行列モデルに基づく行列化の問題を考察した。 我々は、決定理論の枠組みでこの問題の基本的な統計的限界を確立し、制約付き最小二乗率を示す。 そこで本研究では,性能向上を保証した新しい時間適応ソートアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-01-17T14:53:52Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Sparse Factorization of Large Square Matrices [10.94053598642913]
  本稿では,大面積の正方行列とスパースフルランク行列の積を近似する。 近似では、我々の手法は$Ntimes N$ full matrix に対して$N(log N)2$ non-zero number しか必要としない。 近似行列がスパースかつハイランクである場合,本手法により近似精度が向上することを示す。
  論文  参考訳（メタデータ） (2021-09-16T18:42:21Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries [4.230158563771147]
  低階行列補完のための新しい,単純で,計算効率のよい反復法を提案する。 我々のアルゴリズムは、R2RILS(R2RILS for rank $2r$peterative least squares)と呼ばれ、メモリ要件が低い。
  論文  参考訳（メタデータ） (2020-02-05T16:20:58Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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