A Short Note on Batch-efficient Divide-and-Conquer Algorithm for EigenDecomposition
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Parallelising MCMC via Random Forests
For Bayesian computation in big data contexts, the divide-and-conquer MCMC concept splits the whole data set into batches, runs MCMC algorithms separately over each batch to produce samples of parameters, and combines th…
Divide and Conquer in Video Anomaly Detection: A Comprehensive Review and New Approach
Video anomaly detection is a complex task, and the principle of "divide and conquer" is often regarded as an effective approach to tackling intricate issues. It's noteworthy that recent methods in video anomaly detection…
Anomaly DetectionPhilosophyVideo Anomaly DetectionImprove Sentence Alignment by Divide-and-conquer
In this paper, we introduce a divide-and-conquer algorithm to improve sentence alignment speed. We utilize external bilingual sentence embeddings to find accurate hard delimiters for the parallel texts to be aligned. We …
Optical Character Recognition (OCR)SentenceSentence EmbeddingsDivide and...conquer? On the limits of algorithmic approaches to syntactic semantic structure
In computer science, divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A D&C algorithm works by recursively and monotonically breaking down a problem into sub problems of the sam…
validTwo provably consistent divide and conquer clustering algorithms for large networks
In this article, we advance divide-and-conquer strategies for solving the community detection problem in networks. We propose two algorithms which perform clustering on a number of small subgraphs and finally patches the…
ClusteringCommunity DetectionVocal Bursts Valence Prediction