Software: Apache. PHP/5.4.45 

uname -a: Linux webm003.cluster110.gra.hosting.ovh.net 5.15.167-ovh-vps-grsec-zfs-classid #1 SMP Tue
Sep 17 08:14:20 UTC 2024 x86_64 

uid=243112(mycochar) gid=100(users) groups=100(users)  

Safe-mode: OFF (not secure)

/home/mycochar/Python-3.10.12/Modules/_decimal/libmpdec/literature/   drwxr-xr-x
Free 0 B of 0 B (0%)
Your ip: 216.73.216.218 - Server ip: 213.186.33.19
                            

Viewing file:     six-step.txt (1.45 KB)      -rw-r--r--

(* Copyright (c) 2011-2020 Stefan Krah. All rights reserved. *)


The Six Step Transform:
=======================

In libmpdec, the six-step transform is the Matrix Fourier Transform (See
matrix-transform.txt) in disguise. It is called six-step transform after
a variant that appears in [1]. The algorithm requires that the input
array can be viewed as an R*C matrix.


Algorithm six-step (forward transform):
---------------------------------------

  1a) Transpose the matrix.

  1b) Apply a length R FNT to each row.

  1c) Transpose the matrix.

  2) Multiply each matrix element (addressed by j*C+m) by r**(j*m).

  3) Apply a length C FNT to each row.

  4) Transpose the matrix.

Note that steps 1a) - 1c) are exactly equivalent to step 1) of the Matrix
Fourier Transform. For large R, it is faster to transpose twice and do
a transform on the rows than to perform a column transpose directly.



Algorithm six-step (inverse transform):
---------------------------------------

  0) View the matrix as a C*R matrix.

  1) Transpose the matrix, producing an R*C matrix.

  2) Apply a length C FNT to each row.

  3) Multiply each matrix element (addressed by i*C+n) by r**(i*n).

  4a) Transpose the matrix.

  4b) Apply a length R FNT to each row.

  4c) Transpose the matrix.

Again, steps 4a) - 4c) are equivalent to step 4) of the Matrix Fourier
Transform.



--

  [1] David H. Bailey: FFTs in External or Hierarchical Memory
      http://crd.lbl.gov/~dhbailey/dhbpapers/