A Short Note on Batch-efficient Divide-and-Conquer Algorithm for EigenDecomposition

• URL: http://arxiv.org/abs/2604.27325v1
• Date: Thu, 30 Apr 2026 02:13:02 GMT
• Title: A Short Note on Batch-efficient Divide-and-Conquer Algorithm for EigenDecomposition
• Abstract summary: EigenDecomposition (ED) is at the heart of many computer vision algorithms and applications.<n>One crucial bottleneck limiting its usage is the expensive computation cost.<n>This paper proposes a batch-efficient Divide-and-Conquer based ED algorithm for larger matrices.
• Score: 26.007299980241964
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: EigenDecomposition (ED) is at the heart of many computer vision algorithms and applications. One crucial bottleneck limiting its usage is the expensive computation cost, particularly for a mini-batch of matrices in deep neural networks. Our previous work proposed a dedicated QR-based ED algorithm for batched small matrices (dim${<}32$). This short paper targets the limitation and proposes a batch-efficient Divide-and-Conquer based ED algorithm for larger matrices. The numerical test shows that for a mini-batch of matrices whose dimensions are smaller than $64$, our method can be much faster than the Pytorch SVD function.

Related papers

• 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)
• FFT-based Dynamic Subspace Selection for Low-Rank Adaptive Optimization of Large Language Models [49.397861654088636]
  We propose a two-step procedure to approximate SVD/QR-based gradient projections into lower-dimensional spaces.<n>We show that our strategy achieves faster runtime and reduced memory usage by up to $25%$ across different model sizes.
  arXiv  Detail & Related papers  (2025-05-23T14:37:00Z)
• An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks [8.779871128906787]
  We propose algorithms to improve the inference time and memory efficiency of Deep Neural Networks (DNNs)<n>We focus on matrix multiplication as the bottleneck operation of inference.<n>Our experiments show up to a 5.24x speedup in the inference time.
  arXiv  Detail & Related papers  (2024-11-10T04:56:14Z)
• Optimal Quantization for Matrix Multiplication [29.75700570685703]
  Algorithmically, we construct a universal quantizer based on nested lattices with an explicit guarantee of approximation error.<n>A practical low-complexity version of our quantizer achieves performance quite close to optimal.
  arXiv  Detail & Related papers  (2024-10-17T17:19:48Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
  EigenDecomposition (ED) is at the heart of many computer vision algorithms and applications. We propose a QR-based ED method dedicated to the application scenarios of computer vision.
  arXiv  Detail & Related papers  (2022-07-09T09:14:12Z)
• Multiplying Matrices Without Multiplying [0.0]
  Multiplying matrices is among the most fundamental and compute-intensive operations in machine learning. We introduce a learning-based algorithm for this task that greatly outperforms existing methods.
  arXiv  Detail & Related papers  (2021-06-21T05:08:54Z)
• 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)
• Direct Spatial Implementation of Sparse Matrix Multipliers for Reservoir Computing [0.0]
  Reservoir computing systems rely on the recurrent multiplication of a very large, sparse, fixed matrix. We argue that direct implementation of these fixed matrices minimizes the work performed in the computation. We present the structure of our bit-serial matrix multiplier, and evaluate using canonical signed digit representation to further reduce logic utilization.
  arXiv  Detail & Related papers  (2021-01-21T23:16:22Z)
• What if Neural Networks had SVDs? [66.91160214071088]
  Various Neural Networks employ time-consuming matrix operations like matrix inversion. We present an algorithm that is fast enough to speed up several matrix operations.
  arXiv  Detail & Related papers  (2020-09-29T12:58:52Z)
• Ranky : An Approach to Solve Distributed SVD on Large Sparse Matrices [0.0]
  Singular Value Decomposition (SVD) is a well studied research topic in many fields and applications. We propose Ranky, set of methods to solve rank problem on large and sparse matrices in a distributed manner.
  arXiv  Detail & Related papers  (2020-09-21T11:36:28Z)

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.