×

zbMATH — the first resource for mathematics

Fast and numerically stable algorithms for discrete cosine transforms. (English) Zbl 1072.65171
The authors deal with fast cosine transform algorithms from the stability point of view. Their algorithm is based on a factorization of cosine matrices into sparse, almost orthogonal matrices. This is the due to achieve a better numerical stability than previous fast cosine transforms without orthogonal factors.

MSC:
65T50 Numerical methods for discrete and fast Fourier transforms
65G50 Roundoff error
15A23 Factorization of matrices
Software:
mctoolbox
PDF BibTeX Cite
Full Text: DOI
References:
[1] Ahmed, H.; Natarajan, T.; Rao, K.R., Discrete cosine transform, IEEE trans. comput., 23, 90-93, (1974) · Zbl 0273.65097
[2] Baszenski, G.; Schreiber, U.; Tasche, M., Numerical stability of fast cosine transforms, Numer. funct. anal. optim., 21, 25-46, (2000) · Zbl 0953.65102
[3] Britanak, V., A unified discrete cosine and discrete sine transform computation, Signal process., 43, 333-339, (1995) · Zbl 0925.65256
[4] Chen, W.H.; Smith, C.H.; Fralick, S., A fast computational algorithm for the discrete cosine transform, IEEE trans. comm., 25, 1004-1009, (1977) · Zbl 0371.94016
[5] Cheng, L.; Hu, H.; Luo, Y., Integer discrete cosine transform and its fast algorithm, Electron. lett., 37, 64-65, (2001)
[6] Daubechies, I.; Sweldens, W., Factoring wavelet transforms into lifting steps, J. Fourier anal. appl., 4, 247-269, (1998) · Zbl 0913.42027
[7] E. Feig, A scaled DCT algorithm, Proc. SPIE 1244 (1990), 2-13
[8] Feig, E.; Winograd, S., Fast algorithms for the discrete cosine transform, IEEE trans. signal process., 40, 2174-2193, (1992) · Zbl 0762.65103
[9] Heideman, M.T.; Johnson, D.H.; Burrus, C.S., Gauss and the history of the fast Fourier transform, Arch. hist. exact sci., 34, 265-277, (1985) · Zbl 0577.01027
[10] Higham, N.J., Accuracy and stability of numerical algorithms, (1996), SIAM Philadelphia, PA · Zbl 0847.65010
[11] Hou, H.S., A fast recursive algorithm for computing the discrete cosine transform, IEEE trans. acoust. speech signal process., 35, 1455-1461, (1987)
[12] Lee, B., A new algorithm to compute the discrete cosine transform, IEEE trans. acoust. speech signal process., 32, 1243-1245, (1984) · Zbl 0576.65143
[13] L. Loeffler, A. Lightenberg, G.S. Moschytz, Practicle fast 1-d DCT algorithms with 11 multiplications, Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (1989) 989-991
[14] Püschel, M.; Moura, J.M., The algebraic approach to the discrete cosine and sine transforms and their fast algorithms, SIAM J. comput., 32, 1280-1316, (2003) · Zbl 1046.42003
[15] Rao, K.R.; Yip, P., Discrete cosine transform: algorithms, advantages, applications, (1990), Academic Press Boston · Zbl 0726.65162
[16] Runge, C.; König, H., Lectures on numerical arithmetic, (1924), Springer Berlin, (in German).
[17] U. Schreiber, Fast and numerically stable trigonometric transforms, Thesis, University of Rostock, 1999 (in German)
[18] Skodras, A.N.; Christopolous, C.A., Split-radix fast cosine transform algorithm, Int. J. electr., 74, 513-522, (1993)
[19] Steidl, G., Fast radix-p discrete cosine transform, Appl. algebra engrg. comm. comput., 3, 39-46, (1992) · Zbl 0755.65145
[20] Steidl, G.; Tasche, M., A polynomial approach to fast algorithms for discrete Fourier-cosine and Fourier-sine transforms, Math. comput., 56, 281-296, (1991) · Zbl 0725.65145
[21] Strang, G., The discrete cosine transform, SIAM rev., 41, 135-147, (1999) · Zbl 0939.42021
[22] C.W. Sun, P. Yip, Split-radix algorithms for DCT and DST, Proc. Asilomar Conf. Signals Systems Comput., Pacific Grove, 1989, pp. 508-512
[23] Tasche, M.; Zeuner, H., Roundoff error analysis for fast trigonometric transforms, (), 357-406 · Zbl 0976.65123
[24] Van Loan, C.F., Computational framework for the fast Fourier transform, (1992), SIAM Philadelphia, PA · Zbl 0757.65154
[25] Wang, Z., Fast algorithms for the discrete W transform and the discrete Fourier transform, IEEE trans. acoust. speech signal process., 32, 803-816, (1984) · Zbl 0577.65134
[26] Wang, Z., On computing the discrete Fourier and cosine transforms, IEEE trans. acoust. speech signal process., 33, 1341-1344, (1985) · Zbl 0621.65034
[27] H. Zeuner, A general theory of stochastic roundoff error analysis with applications to DFT and DCT, J. Comput. Anal. Appl., in press · Zbl 1099.65044
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.