Молимо вас користите овај идентификатор за цитирање или овај линк до ове ставке:
https://open.uns.ac.rs/handle/123456789/3157
Назив: | Fast Computation of the Discrete Pascal Transform | Аутори: | Gajić, Dušan Stanković R. |
Датум издавања: | 30-јун-2017 | Часопис: | Proceedings of The International Symposium on Multiple-Valued Logic | Сажетак: | © 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 |
Налази се у колекцијама: | FTN Publikacije/Publications |
Приказати целокупан запис ставки
SCOPUSTM
Навођења
2
проверено 26.08.2023.
Преглед/и станица
18
Протекла недеља
9
9
Протекли месец
1
1
проверено 10.05.2024.
Google ScholarTM
Проверите
Алт метрика
Ставке на DSpace-у су заштићене ауторским правима, са свим правима задржаним, осим ако није другачије назначено.