**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Publication# pyFFS: A Python Library for Fast Fourier Series Computation and Interpolation with GPU Acceleration

Résumé

Fourier transforms are an often necessary component in many computational tasks, and can be computed efficiently through the fast Fourier transform (FFT) algorithm. However, many applications involve an underlying continuous signal, and a more natural choice would be to work with e.g. the Fourier series (FS) coefficients in order to avoid the additional overhead of translating between the analog and discrete domains. Unfortunately, there exists very little literature and tools for the manipulation of FS coefficients from discrete samples. This paper introduces a Python library called pyFFS for efficient FS coefficient computation, convolution, and interpolation. While the libraries SciPy and NumPy provide efficient functionality for discrete Fourier transform coefficients via the FFT algorithm, pyFFS addresses the computation of FS coefficients through what we call the fast Fourier series (FFS). Moreover, pyFFS includes an FS interpolation method based on the chirp Z-transform that can make it more than an order of magnitude faster than the SciPy equivalent when one wishes to perform interpolation. GPU support through the CuPy library allows for further acceleration, e.g. an order of magnitude faster for computing the 2-D FS coefficients of 1000 x 1000 samples and nearly two orders of magnitude faster for 2-D interpolation. As an application, we discuss the use of pyFFS in Fourier optics. pyFFS is available as an open source package at https://github.com/imagingofthings/pyFFS, with documentation at https://pyffs.readthedocs.io.

Official source

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Publications associées (32)

Chargement

Chargement

Chargement

Concepts associés (17)

Algorithme

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation).
Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de

Transformation de Fourier

thumb|Portrait de Joseph Fourier.
En mathématiques, plus précisément en analyse, la transformation de Fourier est une extension, pour les fonctions non périodiques, du développement en série de Fou

Série de Fourier

vignette|250px|Les quatre premières sommes partielles de la série de Fourier pour un signal carré.
vignette|250px|Le premier graphe donne l'allure du graphe d'une fonction périodique ; l'histogramme d

In recent work, methods from the theory of modular forms were used to obtain Fourier uniqueness results in several key dimensions (d = 1, 8, 24), in which a function could be uniquely reconstructed from the values of it and its Fourier transform on a discrete set, with the striking application of resolving the sphere packing problem in dimensions d = 8 and d = 24. In this short note, we present an alternative approach to such results, viable in even dimensions, based instead on the uniqueness theory for the KleinGordon equation. Since the existing method for the Klein-Gordon uniqueness theory is based on the study of iterations of Gauss-type maps, this suggests a connection between the latter and methods involving modular forms. The derivation of Fourier uniqueness from the Klein-Gordon theory supplies conditions on the given test function for Fourier interpolation, which are hoped to be optimal or close to optimal.

2021Matthieu Martin Jean-André Simeoni

The Square Kilometre Array (SKA) will form the largest radio telescope ever built, generating on the order of one terabyte of data per second. To reduce the data flow sent to the central processor, hierarchical designs have been proposed: the data is primarily collected in groups of antennas, and summed coherently by beamforming. Historically, Fourier analysis has played a prominent role in radio astronomy interferometry, legitimated by the celebrated van Cittert-Zernike theorem. We show that, in the case of modern hierarchical designs, beamformed data has a less intimate, and thus more complicated relationship to the Fourier domain. Unsatisfactory attempts have been proposed to compensate, which implicitly retain the Fourier framework, and are limited to directive beamforming. We show that when stepping away from Fourier, we can embed the data in a more natural domain originating from the telescope configuration and the specific beamforming technique. This leads to a new, more accurate, imaging pipeline. Standard techniques such as w-projection, and gridding are no longer needed, as the reconstruction is performed on the celestial sphere. The proposed imager operates in two steps. First, a preconditioning based on the Gram-Schmidt orthogonalization procedure is performed, in order to facilitate the computation of the pseudoinverse sky estimate. Then, from this, the LASSO estimate is approximated very efficiently. The quality of this approximation is shown to be linked directly to the effective support of the instrument point spread function. Due to the greater flexibility of this framework, information-maximising beamforming techniques such as randomised beamforming can be readily incorporated. Moreover, we use the Bonferroni method to construct global confidence intervals onto the Gram-Schmidt least squares estimate, and use them to test the statistical significance of each pixel. The complexity of the proposed technique is assessed and compared to the the state-of-the-art combined CLEAN and A-projection algorithm. In the case of LOFAR, we show that our algorithm can be from 2 to 34 times faster. The accuracy and sensitivity of the new technique is also shown, for simulated data, to be superior.

2015Let K be a totally real number field of degree n >= 2. The inverse different of K gives rise to a lattice in Rn. We prove that the space of Schwartz Fourier eigenfunctions on R-n which vanish on the "component-wise square root" of this lattice, is infinite dimensional. The Fourier non-uniqueness set thus obtained is a discrete subset of the union of all spheres root mS(n-1) for integers m >= 0 and, as m -> infinity, there are similar to c(K)m(n-1) many points on the m-th sphere for some explicit constant c(K), proportional to the square root of the discriminant of K. This contrasts a recent Fourier uniqueness result by Stoller (2021) Using a different construction involving the codifferent of K, we prove an analogue for discrete subsets of ellipsoids. In special cases, these sets also lie on spheres with more densely spaced radii, but with fewer points on each. We also study a related question about existence of Fourier interpolation formulas with nodes "root Lambda" for general lattices Lambda subset of R-n. Using results about lattices in Lie groups of higher rank we prove that if n >= 2 and a certain group Gamma(Lambda) >= PSL2.(R)(n) is discrete, then such interpolation formulas cannot exist. Motivated by these more general considerations, we revisit the case of one radial variable and prove, for all n >= 5 and all real lambda >= 2, Fourier interpolation results for sequences of spheres root 2m/lambda Sn-1, where m ranges over any fixed cofinite set of non-negative integers. The proof relies on a series of Poincare type for Hecke groups of infinite covolume and is similar to the one in Stoller (2021).