Authors: Gajić, Dušan
Stanković, Radomir 
Title: Fast Computation of the Discrete Pascal Transform
Journal: Proceedings of The International Symposium on Multiple-Valued Logic
First page: 149
Last page: 154
Conference: 47th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2017; Novi Sad; Serbia; 22 May 2017 through 24 May 2017
Issue Date: 30-Jun-2017
ISBN: 978-1-509-05495-4
ISSN: 0195-623X
DOI: 10.1109/ISMVL.2017.32
The discrete Pascal transform (DPT) is a relatively recently introduced spectral transform based on the concept of the Pascal triangle which has been known for centuries. It is used in digital image processing, digital filtering, pattern recognition, watermarking, and related areas. Its applicabilityis limited by the O(N2) asymptotical time complexity of bestcurrent algorithms for its computation, where N is the size of the function to be processed. In this paper, we propose a method for the efficient computation of the DPT in O(N logN) time, based on the factorization of its transform matrix into a product of three matrices with special structure - two diagonal matrices and a Toeplitz matrix. The Toeplitz matrix is further embedded into a circulant matrix of order 2N. The diagonalization of the circulant matrix by the Fourier matrix permits the use of the fast Fourier transform (FFT) for performing the computations, leading to an algorithm with the overall computational complexity of O(N logN). Since the entries in the Toeplitz matrix have very different magnitudes, the numerical stability of this algorithm is also discussed. We also consider the issues in implementing the proposed algorithm for highly-parallel computation on graphicsprocessing units (GPUs). The experiments show that computing the DPT using the proposed algorithm processed on GPUs is orders of magnitude faster than the best current approach. As a result, the proposed method can significantly extend the practical applicability of the discrete Pascal transform.
Keywords: discrete Pascal transform | fast algorithms | GPGPU | parallel computing | Pascal triangle | Toeplitz matrix
Publisher: IEEE

Show full item record


checked on Apr 17, 2024

Page view(s)

checked on Apr 16, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.