論文の概要: Packing Entries to Diagonals for Homomorphic Sparse-Matrix Vector Multiplication

• arxiv url: http://arxiv.org/abs/2604.04683v1
• Date: Mon, 06 Apr 2026 13:48:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-07 15:49:19.208774
• Title: Packing Entries to Diagonals for Homomorphic Sparse-Matrix Vector Multiplication
• Title（参考訳）: 正則スパース行列ベクトル乗算のための対角線への包絡
• Authors: Kemal Mutluergil, Deniz Elbek, Kamer Kaya, Erkay Savaş,
• Abstract要約: ホモモルフィック暗号化(HE)は、暗号化されたデータに対する計算を可能にするが、かなりのオーバーヘッドを引き起こす。 スパース行列の行や列をパーミュレートして、その非ゼロをできるだけ少数の環状対角線に詰め込む方法を研究する。
• 参考スコア（独自算出の注目度）: 1.0499611180329802
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Homomorphic encryption (HE) enables computation over encrypted data but incurs a substantial overhead. For sparse-matrix vector multiplication, the widely used Halevi and Shoup (2014) scheme has a cost linear in the number of occupied cyclic diagonals, which may be many due to the irregular nonzero pattern of the matrix. In this work, we study how to permute the rows and columns of a sparse matrix so that its nonzeros are packed into as few cyclic diagonals as possible. We formalise this as the two-dimensional diagonal packing problem (2DPP), introduce the two-dimensional circular bandsize metric, and give an integer programming formulation that yields optimal solutions for small instances. For large matrices, we propose practical ordering heuristics that combine graph-based initial orderings - based on bandwidth reduction, anti-bandwidth maximisation, and spectral analysis - and an iterative-improvement-based optimization phase employing 2OPT and 3OPT swaps. We also introduce a dense row/column elimination strategy and an HE-aware cost model that quantifies the benefits of isolating dense structures. Experiments on 175 sparse matrices from the SuiteSparse collection show that our ordering-optimisation variants can reduce the diagonal count by $5.5\times$ on average ($45.6\times$ for one instance). In addition, the dense row/column elimination approach can be useful for cases where the proposed permutation techniques are not sufficient; for instance, in one case, the additional elimination helped to reduce the encrypted multiplication cost by $23.7\times$ whereas without elimination, the improvement was only $1.9\times$.
• Abstract（参考訳）: ホモモルフィック暗号化(HE)は、暗号化されたデータに対する計算を可能にするが、かなりのオーバーヘッドを引き起こす。 スパース行列ベクトル乗法では、広く使われている Halevi and Shoup (2014) スキームは、占有された巡回対角線の個数においてコスト線型であり、行列の不規則な非ゼロパターンのために多くのものが存在する。 本研究では,スパース行列の行や列の透過性について検討し,その非ゼロをできるだけ少数の環状対角線に詰め込む方法を検討した。 これを2次元対角パッキング問題 (2DPP) として定式化し、2次元の円帯サイズメートル法を導入し、小インスタンスに対して最適解を与える整数プログラミングの定式化を与える。 本研究では,2OPTおよび3OPTスワップを用いた繰り返し改善型最適化フェーズと,帯域幅の削減,帯域幅の最大化,スペクトル分析に基づくグラフベースの初期順序付けを併用した実用的な順序付けヒューリスティックを提案する。 また,高密度構造を分離する利点を定量化するための高密度行/カラム除去戦略とHE対応コストモデルも導入する。 SuiteSparseコレクションから175個のスパース行列を実験したところ、オーダー最適化の変種は、平均で5.5\times$(45.6\times$)の対角数を減らすことができる。 さらに、高密度行/カラムの除去アプローチは、提案された置換手法が不十分な場合に有効であり、例えば、追加の除去は暗号化された乗算コストを23.7\times$に減らすのに役立ち、一方、除去なしでは、改善は1.9\times$に過ぎなかった。

関連論文リスト

• Symplectic Split-Operator Propagators from Tridiagonalized Multi-Mode Bosonic Hilbert Spaces for Bose-Hubbard Hamiltonians [0.0]
  ボソニック・マルチモードシステムの2つのファミリーをトリディアゴナライズする。 ボソニック・マルチモードシステムの2つのファミリーをトリディアゴナライズする方法を示す。
  論文  参考訳（メタデータ） (2026-03-26T16:51:03Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。 本手法の様々な応用は, 微分問題を解く文脈で論じる。
  論文  参考訳（メタデータ） (2026-02-11T07:24:33Z)
• Improving Algorithmic Efficiency using Cryptography [11.496343300483904]
  計算問題を解く際の時間的複雑さを改善するために暗号を用いる方法を示す。 標準的な暗号仮定の下では、既存のアルゴリズムよりも決定的に高速なアルゴリズムを設計できることを示す。
  論文  参考訳（メタデータ） (2025-02-18T17:08:59Z)
• Kissing to Find a Match: Efficient Low-Rank Permutation Representation [33.880247068298374]
  そこで本稿では,低ランク行列係数化を用いて近似し,次いで非線形性を用いて,大きな置換行列の次元性の呪いに取り組むことを提案する。 提案手法の適用性とメリットを,様々な問題に対する一連の実験を通じて実証する。
  論文  参考訳（メタデータ） (2023-08-25T08:59:03Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。 合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T22:35:16Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  共分散行列の明示的な構成を避ける新しい推論手法を提案する。 本手法では, 数値線形代数と共役勾配アルゴリズムの対角線推定結果とを結合する。 いくつかのシミュレーションにおいて,本手法は計算時間とメモリにおける既存手法よりも拡張性が高い。
  論文  参考訳（メタデータ） (2022-02-25T16:35:26Z)
• 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)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  最小二乗問題に対する反復スケッチの性能について検討する。 本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。 これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
  論文  参考訳（メタデータ） (2020-02-03T16:17:50Z)

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

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