Academic literature on the topic 'Butterfly factorization'

This paper describes an embedded FFT processor where the higher radices butterflies maintain one complex multiplier in its critical path. Based on the concept of a radix-r fast Fourier factorization and based on the FFT parallel processing, we introduce a new concept of a radix-r Fast Fourier Transform in which the concept of the radix-r butterfly computation has been formulated as the combination of radix-2α/4β butterflies implemented in parallel. By doing so, the VLSI butterfly implementation for higher radices would be feasible since it maintains approximately the same complexity of the radix-2/4 butterfly which is obtained by block building of the radix-2/4 modules. The block building process is achieved by duplicating the block circuit diagram of the radix-2/4 module that is materialized by means of a feed-back network which will reuse the block circuit diagram of the radix-2/4 module.

<span lang="EN-US">This paper presents an efficient fast Walsh–Hadamard–Hartley transform (FWHT) algorithm that incorporates the computation of the Walsh-Hadamard transform (WHT) with the discrete Hartley transform (DHT) into an orthogonal, unitary single fast transform possesses the block diagonal structure. The proposed algorithm is implemented in an integrated butterfly structure utilizing the sparse matrices factorization approach and the Kronecker (tensor) product technique, which proved a valuable and fast tool for developing and analyzing the proposed algorithm. The proposed approach was distinguished by ease of implementation and reduced computational complexity compared to previous algorithms, which were based on the concatenation of WHT and FHT by saving up to 3N-4 of real multiplication and 7.5N-10 of real addition.</span>

Cette thèse s’intéresse à deux enjeux de frugalité et d’efficacité dans l’apprentissage profond moderne : frugalité en données et efficacité en ressources de calcul. Premièrement, nous étudions l’apprentissage auto-supervisé, une approche prometteuse en vision par ordinateur qui ne nécessite pas d’annotations des données pour l'apprentissage de représentations. En particulier, nous proposons d’unifier plusieurs fonctions objectives auto-supervisées dans un cadre de noyaux invariants par rotation, ce qui ouvre des perspectives en termes de réduction de coût de calcul de ces fonctions objectives. Deuxièmement, étant donné que l’opération prédominante des réseaux de neurones profonds est la multiplication matricielle, nous nous penchons sur la construction d’algorithmes rapides qui permettent d’effectuer la multiplication matrice-vecteur avec une complexité presque linéaire. Plus spécifiquement, nous étudions le problème de factorisation creuse de matrices sous contrainte de parcimonie "butterfly", une structure commune à plusieurs transformées rapides comme la transformée de Fourier discrète. La thèse établit des garanties théoriques sur l’algorithme de factorisation butterfly, et étudie le potentiel de la parcimonie butterfly pour la réduction du coût computationnel des réseaux de neurones lors de leur phase d’apprentissage ou d’inférence. Nous explorons notamment l’efficacité des implémentations GPU de la multiplication matricielle avec parcimonie butterfly, dans le but d’accélérer réellement des réseaux de neurones parcimonieux
This thesis focuses on two challenges of frugality and efficiency in modern deep learning: data frugality and computational resource efficiency. First, we study self-supervised learning, a promising approach in computer vision that does not require data annotations for learning representations. In particular, we propose a unification of several self-supervised objective functions under a framework based on rotation-invariant kernels, which opens up prospects to reduce the computational cost of these objective functions. Second, given that matrix multiplication is the predominant operation in deep neural networks, we focus on the construction of fast algorithms that allow matrix-vector multiplication with nearly linear complexity. More specifically, we examine the problem of sparse matrix factorization under the constraint of butterfly sparsity, a structure common to several fast transforms like the discrete Fourier transform. The thesis establishes new theoretical guarantees for butterfly factorization algorithms, and explores the potential of butterfly sparsity to reduce the computational costs of neural networks during their training or inference phase. In particular, we explore the efficiency of GPU implementations for butterfly sparse matrix multiplication, with the goal of truly accelerating sparse neural networks