Here is a test:
For small matrices, apart from the first call, the performance is almost perfect (🎉!).
As a comparison, an equivalent test may be performed in modern Python:
As you can see, for 1024×1024, 2048×2048, 4096×4096, 8192×8192, and 16384×16384 matrices, Maple's performance gets pretty poor. Is the
FFT procedure not well optimized for larger matrices? I do have read the Fourier Transforms in Maple, yet I cannot find any information on this subject.
In accordance with the following output
FFT_complex8 := proc()
3 :-DiscreteTransforms:-FFT_complex8 := LinkExternal('hw_FFT',2003);
it appears that the code hasn't been developed for 20 years. Is it possible to improve the performance of the
FFT built into Maple in order that the computation on such a 2¹⁴×2¹⁴ matrix can be achieved in about twenty seconds (rather than in two minutes)?
Note. For these matrices, exact transform results (see below) can be obtained symbolically.
for n from 0 to 12 do
m := LinearAlgebra:-HankelMatrix(<$ (1 + 1 .. 2**n + 2**n)>, datatype = complex, shape = ): gc();
print(n, andseq(abs(_) < HFloat(1, -10, 2), _ in SignalProcessing:-FFT(m, normalization = none, inplace = true) - Matrix(2^n, <2^(2*n)*(2^n + 1), <'2^(2*n - 1)*(:-cot((k - 1)/2^n*Pi)*I - 1)' $ 'k' = 1 + 1 .. 2^n>>, shape = symmetric, storage = sparse, datatype = complex)) (* faster than `rtable_scanblock` and `ArrayTools:-IsZero` and much faster (🎊!) than `comparray` and `verify/Matrix` with testfloat *) )
However, the main goal is to test the numerical efficiency of Maple's fast Fourier transform algorithm.