Fast algorithms for the discrete cosine transform and for the discrete Fourier transform. (Chinese. English summary) Zbl 0735.65096

Summary: A new sparse matrix factorization is proposed for the DCT-II matrix \([C^{II}_ N]\). The new algorithm for DCT-II requires a fewer number of operations than that of Z. Wang [IEEE Trans. Acoust. Speech Signal Process., ASSP-32: 803-816 (1984; Zbl 0577.65134)] and of J. Makhoul [ibid. ASSP-28, 27-34 (1980; Zbl 0522.65092)] and requires the same number as the algorithm of B. G. Lee [ibid. ASSP-32, 1243-1245 (1984; Zbl 0576.65143)], which introduces large errors easily. The present algorithm has overcome the limitation. We discuss then the fast computation for DCT, DST and DFT by the present algorithm, which requires the same number of multiplications and much fewer additions than that of the algorithm by R. D. Preuss [ibid. ASSP-30, 595-607 (1982; Zbl 0563.65089)].


65T50 Numerical methods for discrete and fast Fourier transforms
65F50 Computational methods for sparse matrices
65F30 Other matrix algorithms (MSC2010)