CS Paper Radar

Greedy Vector Approximation Based on Rotation for Multiplierless Complex Products

Luiz F. da S. Coelho, Paulo S. R. Diniz, Didier Le Ruyet

eess.SP ·submitted 2026-11-18 17:59 UTC · v1

Abstract

This paper proposes a greedy approximation algorithm for performing complex-valued inner products in multiplierless hardware. The matching pursuits for accurate rotation approximation (MPARA) algorithm approximates the tangent of the phase of complex elements as a sum of signed powers of two (SOPOT) representation, enabling multiplierless hardware for complex-valued multiplication. The proposed algorithm outperforms other state-of-the-art approximation methods for approximating the twiddle factors of a fast Fourier transform (FFT).

Comment
This paper is submitted to ICASSP 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Sparse Integer Fourier Transform and Its Application In Machine Learning

cs.MS cs.LG ·2026-11-16 ·Jinyang Li, Jie Chen
similarity 0.56
Abstract

The Discrete Fourier transform, mainly implemented by Fast Fourier Transform (FFT), has been essential for numerous domains, such as digital signal processing and feature extraction in materials design. However, current FFT methods suffer from extensive non-trivial multiplications and twiddle-factor operations in the big data era. To improve the computational efficiency of FFT, this study proposes Sparse Integer Fourier Transform (SIFT), a method that leverages the fast computing of sparsity and small integers, and applies the Radix-n method to derive an FFT. The 2N-point DFT matrix in Radix-n FFT is decomposed into four sparse integer matrices. A diagonal matrix containing complex twiddle factors is efficiently approximated using an optimization strategy while the remaining matrices retain sparsity and integer entries. For radix-32 FFT, SIFT reduces the estimated arithmetic cost by 75%, with RMSE below $2.3765\times10^{-8}$ and MAPE below 0.01089%. We evaluate frequency extraction in a numerical test and an engineering case. In the numerical test, MAPE and RMSE are below 2.016% and $2.536\times10^{-6}$, respectively. For wind turbine fault diagnosis, SIFT extracts compact spectral features that retain fault information while reducing the classifier's input dimensionality relative to the full time series.

0.23

32-point DFT Approximations Based on Minimal Frobenius Error and DFT Symmetries

eess.SP math.NA ·2026-09-01 ·L. Andrade-Silva, W. A. S. Aleixo, R. J. Cintra
similarity 0.55
Abstract · 10 pages, 2 figures, 5 tables

This work introduces low-complexity, multiplierless approximations for the 32-point discrete Fourier transform. The proposed methods are obtained by minimizing the Frobenius error compared against the DFT matrix over a set of trivial multipliers. A row-wise, symmetry-constrained parameterization is employed to reduce the search space size, rendering the task computationally tractable. The resulting approximations could outperform the reference method in the literature according to energy-based error measurements. A sparse matrix factorization is provided for efficient computation; the arithmetic costs are 152 real additions and 34 bit-shifts only.

0.23

On the Real Part of Butterfly Factorizations, with Application to Fast Transforms

eess.SP ·2026-10-05 ·Ma{ë}l Chaumette, R{é}mi Gribonval, Elisa Riccietti
similarity 0.53
Abstract

Fast transforms such as the Discrete Cosine Transform can be expressed as the real part of a product of complex-valued structured sparse matrices known as Kronecker-sparse factors. More generally, products of such structured sparse matrices appear in square dyadic butterfly and monarch matrices, which are known to represent many fast transforms efficiently. Yet, it has remained unclear whether taking the real or the imaginary part of such products preserves this structure. In this letter, we give a condition on the factors to ensure that the structure is preserved. This condition is satisfied in the case of the Discrete Cosine Transform, the Discrete Sine Transform and the Discrete Hartley Transform, allowing us to provide a new representation of these transforms as products of real-valued Kronecker-sparse factors, which opens new avenues for efficient GPU implementations using low-precision numerical format.

0.22

PENDA: An Efficient Processing Element via Norm-of-Difference for Deep Learning Accelerators

cs.AR ·2026-09-08 ·Kai-Chieh Hsu, Tian-Sheuan Chang
similarity 0.53
Abstract · submitted to IEEE TCAS-AI

Inner product computation dominates the computational cost of deep learning models; thus, accelerating this primitive is key to improving hardware efficiency. However, most existing techniques rely on approximations, which can degrade model accuracy. To preserve exactness while optimizing hardware, this paper presents PENDA (processing element via norm-of-difference architecture), which leverages the law of cosines to recast multiplications as squared-difference operations. Replacing multiply-accumulate units with the proposed norm-of-difference units yields 11~36%, 5~48%, and 11~19% reductions in area, energy, and clock period, respectively, for the PE array of a deep learning accelerator.

0.25

Signed Powers-of-Two Greedy Vector Approximation of Zadoff-Chu Sequences

eess.SP ·2026-11-19 ·Luiz Coelho, Paulo Diniz, Didier Le Ruyet
published similarity 0.52
Abstract

This paper explores the use of sums of signed powers-of-two (SOPOT) for a representation suitable for multiplierless applications of ZC sequences, where multiplications are reduced to a prescribed number of shift-and-add operations. The SOPOT representation is achieved using a greedy algorithm that outperforms other approaches for multiplierless approximations, such as CORDIC and CSD. The proposed algorithm is based on the matching pursuits using generalized bit planes (MPGBP), and the proposed modification enables robustness to hyperparameter tuning. The resulting sequences retain, to some extent, the good autocorrelation properties of ZC, as shown in a matched-filter detection simulation. This corroborates to their use in various practical applications across mainstream cellular systems and devices requiring moderate computational cost.

0.44

Bit-Sparsity Aware Acceleration with Compact CSD Code on Generic Matrix Multiplication

cs.AR ·2026-11-11 ·Zixuan Zhu, Xiaolong Zhou, Chundong Wang, Li Tian, Zunkai Huang +1 more
top venuehighly cited similarity 0.50
Abstract · Accepted for publication in IEEE Transactions on Computers (TC)

The ever-increasing demand for matrix multiplication in artificial intelligence (AI) and generic computing emphasizes the necessity of efficient computing power accommodating both floating-point (FP) and quantized integer (QINT). While state-of-the-art bit-sparsity-aware acceleration techniques have demonstrated impressive performance and efficiency in neural networks through software-driven methods such as pruning and quantization, these approaches are not always feasible in typical generic computing scenarios. In this paper, we propose Bit-Cigma, a hardware-centric architecture that leverages bit-sparsity to accelerate generic matrix multiplication. Bit-Cigma features (1) CCSD encoding, an optimized on-chip sparsification technique based on canonical signed digit (CSD) representation; (2) segmented dot product, a multi-stage exponent matching technique for long FP vectors; and (3) the versatility to efficiently process both FP and QINT data types. CCSD encoding halves the cost of CSD encoding while achieving optimal bit-sparsity, and segmented dot product improves both accuracy and throughput. Bit-Cigma cores are implemented using 65 nm technology at 1 GHz, demonstrating substantial gains in performance and efficiency for both FP and QINT configurations. Compared to state-of-the-art Bitlet, Bit-Cigma achieves 3.2\texttimes{} performance, 6.1\texttimes{} area efficiency, and 15.3\texttimes{} energy efficiency when processing FP32 data while ensuring zero computing error.

0.66

A faster matrix multiplication algorithm through structured optimization

cs.DS cs.CC ·2026-10-06 ·Reza Zadeh
similarity 0.49
Abstract

We present a new asymptotic matrix multiplication construction yielding $ω<2.37115924$, and therefore an algorithm that multiplies two $n\times n$ matrices in $O(n^{2.37115924})$ arithmetic operations over the rationals, reals, or complex numbers. The construction improves the bound $2.371177$ of Dupont et al. within the combination-loss framework for the Coppersmith--Winograd tensor. Our approach combines a shared recursive parameter family with a conditioned optimization procedure that addresses two obstacles: weak gradients at low-mass constituents and competing bottlenecks in the retained exponent. A mass- and probability-dependent rescaling supports quasi-Newton optimization in $212\,820$ coordinates, while a six-control correction balances the three extraction roles at each relevant stage. Positive rational entropy-dual factors and an independent ordinary-string verifier turn the resulting construction into an exact certificate. The verified upper-bound expression lies in $[2.3711592385931075066123,\,2.3711592385931075066124]$. The complete witness and an offline verifier using only the Python standard library accompany the paper.

0.21

ASDL: A Fast Vector Approximation Algorithm for Multiplierless Designs of Convolutional Neural Networks

eess.SP ·2026-11-16 ·Guillaume H. Tong, Luiz F. da S. Coelho, Lounis Zerioul, Didier Le Ruyet
similarity 0.49
Abstract

Matrix multiplications are one of the main computational bottlenecks in neural networks. The calculation reduces to numerous sums of partial products, which scale with the total number of Signed Power of Two (SPT) values in the multiplier matrix. Minimizing the SPT count can significantly reduce the computational burden. In this context, we present a Sum Of (signed) Powers Of Two (SOPOT) vector approximation algorithm that limits SPT counts, namely the Accelerated Signed Digit Loading (ASDL) algorithm. This approximation algorithm converts ResNet50 10 times faster than its predecessor MPGBP, while being more precise. We apply this method to the pre-trained coefficients of different convolutional neural networks, achieving 80.41\% ImageNet accuracy down from 81.3\%, at an average of only 1.5 active bits per coefficient. This is done without any retraining or calibration, which are typically required for the most aggressive quantization methods. Our approach offers a promising direction for neural network inference with higher energy efficiency and fewer hardware requirements: we anticipate up to 10 times improvement over bfloat16 inference.

0.24