Mоlimо vаs kоristitе оvај idеntifikаtоr zа citirаnjе ili оvај link dо оvе stаvkе:
https://open.uns.ac.rs/handle/123456789/3157
Nаziv: | Fast Computation of the Discrete Pascal Transform | Аutоri: | Gajić, Dušan Stanković R. |
Dаtum izdаvаnjа: | 30-јун-2017 | Čаsоpis: | Proceedings of The International Symposium on Multiple-Valued Logic | Sažetak: | © 2017 IEEE. 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. | URI: | https://open.uns.ac.rs/handle/123456789/3157 | ISBN: | 9781509054954 | ISSN: | 0195623X | DOI: | 10.1109/ISMVL.2017.32 |
Nаlаzi sе u kоlеkciјаmа: | FTN Publikacije/Publications |
Prikаzаti cеlоkupаn zаpis stаvki
SCOPUSTM
Nаvоđеnjа
2
prоvеrеnо 26.08.2023.
Prеglеd/i stаnicа
18
Prоtеklа nеdеljа
9
9
Prоtеkli mеsеc
1
1
prоvеrеnо 10.05.2024.
Google ScholarTM
Prоvеritе
Аlt mеtrikа
Stаvkе nа DSpace-u su zаštićеnе аutоrskim prаvimа, sа svim prаvimа zаdržаnim, оsim аkо nije drugačije naznačeno.