Computation of the vilenkin-Chrestenson transform on a GPU

Abstract

The Vilenkin-Chrestenson transform on finite Abelian groups is a useful mathematical tool for the analysis, synthesis, and optimization of multiple-valued functions. This paper proposes techniques for the efficient computation of the Vilenkin-Chrestenson transform using graphics processing units (GPUs). The development of the method is motivated by certain computationally demanding problems in multiplevalued logic (MVL), such as the spectral analysis of mosaics and the design and analysis of MVL circuits. The paper presents mappings of two distinct fast Fourier transform (FFT)-like algorithms, the Cooley- Tukey and the constant geometry algorithms, to the GPU computing model. The proposed solution implements each of the algorithms through a single kernel which permits the computation of the Vilenkin- Chrestenson spectrum of a p-valued function for an arbitrary value of p. The paper also discusses GPU implementation issues specific for the considered algorithms, such as their computational requirements, memory optimizations, and the use of compiler options in overcoming certain restrictions in GPU programming. Experimental results are included in order to verify the validity of the approach and examine its potential for applications in MVL and other areas.