[Octave-bug-tracker] [bug #43742] ifft, ifft2, ifftn should accept 'nonsymmetric' and 'symmetric' options

[Hg200]

Follow-up Comment #20, bug #43742 (group octave):

As promised, I am attaching two patches that should cover any outstanding
issues to hopefully close a 10 year old bug report. Let me briefly summarize
what you get.

1.) The first patch adds two "FFTW-C2R" planners, one with single and the
other with double precision. Unlike "C2C" and "R2C", "C2R" erases its input
data array for rank > 1 cases. Furthermore, "C2R" only uses data from the
lower half of the last dimension (in row major order) plus one element. There
are auxiliary functions to handle these issues. Interface functions are
necessary for the combinations of ifft, ifft2 and ifftn & single and double
precision types & complex and real valued input (CNDArray, dNDArray,
fCNDArray, fNDArray).

2.) The obvious prerequisite for doing an inverse Fourier transform of type
"C2R" is that the input data must be a conjugate-symmetric spectrum. What
happens if it is not? Well, in the rank == 1 case, the "FFTW-C2R" transformer
cuts away half of the input data so that the data is treated as if it were
conjugate-symmetric based on the content stored in the non-redundant part
(positive frequency locations). This means that for rank == 1, asymmetries in
the input data are removed implicitely.
In the generalized Nd Fourier transform (rank > 1), the symmetry is, let's
say, located in "subspace" permutations. It is a cross-complex symmetry hidden
in respective hyper-edges, hyper-faces, hyper-volumes etc., so things are
different and much more difficult here. To eliminate asymmetries, the choice
is to cross mirror the conjugate values of the lower part in each subspace,
sub-subspace, etc. into the upper part. I finally found a solution to this
problem, but it requires recursion. The good news is that the heap grows
exponentially with rank, while the maximum recursion depth only grows
linearly. I did a stack frame investigation with gdb. As expected there is a
noteworthy stack consumption, but it looks okay to me. E.g. for rank = 8 with
a input size array of 8^8 the "makesymmetric" stack consumption is 2kb
compared to 9kb for the complete backtrace.

3.) I've added BISTs that cover more code and also trigger various internal
loops and branches as there wasn't very much before.

4.) The second patch implements the SIMD macros introduced in the first patch
into the existing "R2C" and "C2C" planner code. They replace the currently
hard-coded padding size with sizeof()-based calculations at compile time,
taking into account the size of the data type actually used. The memory
alignment can now be set by the "SIMD_ALIGN_BYTES" definition and is
automatically overtaken into the complete code. Note that unlike "R2C" and
"C2C", "C2R" always requires an intermediate buffer, which is SIMD-aligned by
default. Nevertheless, I have kept the alignment check for the input array in
the "C2R" planner to maintain compatibility with the existing "R2C" and "C2C"
code.

5.) Finally, a small note on the existing code. If you look at fftw::ifft(),
fftw::fft(), the statement "dist = (dist < 0 ? npts : dist)" is unnecessary.
However since it does not cause damage i have overtaken this into my code to
be compatible with the existing code.

Questions and comments are welcome.

(file #55884, file #55885)

    _______________________________________________________

Additional Item Attachment:

File name: bug43742_implement_full_c2r_planner_release.diff Size:63 KB
   
<https://file.savannah.gnu.org/file/bug43742_implement_full_c2r_planner_release.diff?file_id=55884>

File name: bug43742_simd_macros_for_r2c_and_c2c_release.diff Size:4 KB
   
<https://file.savannah.gnu.org/file/bug43742_simd_macros_for_r2c_and_c2c_release.diff?file_id=55885>


    AGPL NOTICE

These attachments are served by Savane. You can download the corresponding
source code of Savane at
https://git.savannah.nongnu.org/cgit/administration/savane.git/snapshot/savane-0ba62ed3a038e8b50b65b09fae7f127f4f071c33.tar.gz


    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?43742>

_______________________________________________
Message sent via Savannah
https://savannah.gnu.org/