On the efficiency and accuracy of a fast computation of discrete monomial transform

Abstract

Let {z₀, z₁,...zₙ₋₁} be a given set of 𝘯 sample points. The 𝘯-point Discrete Monomial Transform (DMT) of an input vector (𝘧₀, 𝘧₁,...𝘧ₙ₋₁) is defined by the collection: 𝘧= {𝘧(0),𝘧(1),...𝘧(𝘯-1)}, where <formula> for 0≤𝘬≤ 𝘯-1. The DMT is a widely used numerical tool in numerous scientific and technical applications, including Magnetic-resonance imaging (MRI), signal and image processing, weather forecasting, and engineering. The direct method (algo. 1) for computing the DMT at 𝘯 sample points requires an 𝘖 (𝘯²) computational complexity. This cost gets prohibitively increased for large values of 𝘯 and hence it makes a heavy burden in many DMT applications. In this paper, we consider an 𝘖 (𝘯log₂² 𝘯) algorithm (algo. 2) for computing an 𝘯 point DMT. This algorithm takes advantage of the natural divide and conquer algorithm, fast polynomial multiplication via the Fast Fourier Transform (FFT), and fast Toeplitz matrix-vector multiplication. The key objective of this paper is to assess the accuracy and time efficiency of this algorithm when it is implemented in finite precision computer arithmetic.

MATLAB programs are coded using a tree data structure in MATLAB to implement algo. 2, and two numerical tests are carried out to test the performance of algo. 2. The CPU times taken by each algorithm are computed and compared for each numerical computation. The accuracy of the algorithm is computed by the absolute relative errors of the numerical solutions of the same numerical tests.

The experiment results demonstrate that algo.2 is more efficient than algo. 1 when 𝘯≥128 However, the absolute relative errors of the numerical solution show the accuracy of algo. 2 is drastically contaminated by lots of errors when 𝘯>16 The tests done using matrix condition number indicate that the lower triangular matrices associated with algo. 2 become ill-conditioned when 𝘯>16 Possible factors which affect the contamination of the accuracy of algo. 2 are identified.

Although algo. 2 is exact in hand computations, it can yield unreliable numerical errors for problems of modest size when it is implemented in reasonable computer arithmetic. However, its time efficiency can be trusted since it applies the same set of instructions for every problem size.