Packing Entries to Diagonals for Homomorphic Sparse-Matrix Vector Multiplication

• URL: http://arxiv.org/abs/2604.04683v1
• Date: Mon, 06 Apr 2026 13:48:39 GMT
• Title: Packing Entries to Diagonals for Homomorphic Sparse-Matrix Vector Multiplication
• Abstract summary: Homomorphic encryption (HE) enables computation over encrypted data but incurs a substantial overhead.<n>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.
• Score: 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$.

Related papers

• GPTQ-2D: Cubic-Time Two-Sided Adaptive Rounding [54.10836630612739]
  GPTQ, or equivalently Babai's nearest plane algorithm, rounds a real matrix to integers under a quadratic metric.<n>We present GPTQ-2D, which produces the identical rounded matrix in cubic time.
  arXiv  Detail & Related papers  (2026-07-29T15:34:00Z)
• Symplectic Split-Operator Propagators from Tridiagonalized Multi-Mode Bosonic Hilbert Spaces for Bose-Hubbard Hamiltonians [0.0]
  We tridia-go-nalize two families of bosonic multimode systems.<n>We show how to tridia-go-nalize two families of bosonic multimode systems.
  arXiv  Detail & Related papers  (2026-03-26T16:51:03Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Improving Algorithmic Efficiency using Cryptography [11.496343300483904]
  We show how to use cryptography to improve the time complexity of solving computational problems.<n>We show that under standard cryptographic assumptions, we can design algorithms that are determinantally faster than existing ones.
  arXiv  Detail & Related papers  (2025-02-18T17:08:59Z)
• Kissing to Find a Match: Efficient Low-Rank Permutation Representation [33.880247068298374]
  We propose to tackle the curse of dimensionality of large permutation matrices by approximating them using low-rank matrix factorization, followed by a nonlinearity. We demonstrate the applicability and merits of the proposed approach through a series of experiments on a range of problems.
  arXiv  Detail & Related papers  (2023-08-25T08:59:03Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  We propose a natural algorithm that involves imputing the missing values of the matrix $XTX$. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing.
  arXiv  Detail & Related papers  (2023-06-06T22:35:16Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function. We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
  arXiv  Detail & Related papers  (2021-09-30T19:17:35Z)
• Sparse Factorization of Large Square Matrices [10.94053598642913]
  In this paper, we propose to approximate a large square matrix with a product of sparse full-rank matrices. In the approximation, our method needs only $N(log N)2$ non-zero numbers for an $Ntimes N$ full matrix. We show that our method gives a better approximation when the approximated matrix is sparse and high-rank.
  arXiv  Detail & Related papers  (2021-09-16T18:42:21Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)
• Graph Metric Learning via Gershgorin Disc Alignment [46.145969174332485]
  We propose a fast general projection-free metric learning framework, where the objective $min_textbfM in mathcalS$ is a convex differentiable function of the metric matrix $textbfM$. We prove that the Gershgorin discs can be aligned perfectly using the first eigenvector $textbfv$ of $textbfM$. Experiments show that our efficiently computed graph metric matrices outperform metrics learned using competing methods in terms of classification tasks.
  arXiv  Detail & Related papers  (2020-01-28T17:44:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.