1
$\begingroup$

I see when I increase number of samples, the imaginary error part of the FFT growth due to the error of sin(n*pi)!=0 where n is the index of the sample in Matlab or octave. Is there anyway to force Matlab/Octave to perform FFT without these type of errors? for example I know if you have sin (sym(pi)*n) =0 in Matlab or octave. Why default FFT in matlab/octave does not use sym(pi) instead of pi?

How could I perform FFT that take care of such PI approximation error? Thanks

$\endgroup$
  • $\begingroup$ FFT is a fast computational algorithm for efficiency, It may also improve accuracy due to less number of MACs. However using a symbolic variable would reduce the efficiency, and render it useless... $\endgroup$ – Fat32 Oct 21 at 9:54
  • $\begingroup$ But if you want to have FFT algorithm and want to have exact values ( e.g. symbolic) what should we do? there is not any function in matlab / octave / python that does this? obviously, I do not want to write DFT and use symbolic as I do not have enough knowledge to write my own FFT and use symbolic $\endgroup$ – learner8059 Oct 21 at 10:40
0
$\begingroup$

An FFT using symbolic math might be possible, but would be many orders of magnitude slower. (I'm guessing at least 10,000 times slower, except for a set of exact equation input signals). You would have to use a symbolic math package instead of Matlab. (Perhaps Mathematica, Maxima, or Maple?)

Instead you might be able pre- and post-process certain inputs to produce known outputs. For instance, you can check if the input is strictly symmetrical around input sample 0. If so, set all the imaginary components of the FFT output to zero. If strictly odd (anti-symmetric), set all the real result components to zero. If strictly real, set all the negative frequency outputs to be exact complex conjugates of the positive frequency ones. etc.

$\endgroup$
  • $\begingroup$ Actually I am using Octave. Still It looks in Matlab it is possible to use Symbolic fft but I am looking for octave version of it $\endgroup$ – learner8059 Oct 21 at 18:27
0
$\begingroup$

If you can relax on pure orthogonality, there exist Integer Discrete Fourier transforms, like the Integer fast Fourier transform (INTFFT) (Integer FFT(Fast Fourier Transform) in Python).

$\endgroup$
0
$\begingroup$

No I would not suggest using symbollic math at all...

Matlab internally uses 64-bit IEEE binary64 (CPU hardware supported) numerical data format for all arithmetic operations including FFT function. Even at 64-bits there is a limit of precision and accumulation of errors.

You can consider the followings to increase (if possible) the precison of your numerical format while losing computational efficiency.

Fundamentally, you can try using a software emulated FPU library with, say, 256 bit, or 512-bit number formats. This will be much slower than the hardware supported 64-bit computations, but still much faster than the symbolic math packages. How to handle this using Matlab is another issue.

Instead of an emulated FPU librray, may be you can consider fixed point integer based implementation which can be much faster than an emulated FPU library. Harder to realize, but it can save a lot. Matlab has some integer support and fixed-point blockset, does that help ?

Furthermore, you can also consider using new features of CPU's such as SSE4, AVX1, AVX2 which are added into intel/amd architectures for vector-parallel operations. May be they would help accelerate wider bit operations than 64-bits (I'm not sure on this.). And even if this is possible how you would integrate this into Matlab is also not easy... (C-Mex files might be needed)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.