User:AboutFace 22/sandbox3

FAST FOURIER TRANSFORM

DFT (Discrete Fourier Transform):

$\mathbf {(} F)_{n}=\sum _{k=0}^{N-1}\mathrm {f} _{k}e^{-i{\dfrac {2kn\pi }{N}}}$

Where ${f_{0},f_{1},....,f_{N-1}}$ is input discrete function sampling and ${F_{0},F_{1},....,F_{N-1}}$ is the result of Fourier Transform.

For sampled function continuous transfrom turns into discrete one:

$F_{n}=\sum _{k=0}^{N-1}f_{k}e^{-ikn{\frac {2\pi }{N}}}$

Lets say N = 8 and write down the DFT:

$\mathbf {(} F)_{n}=\mathrm {f} _{0}+\mathrm {f} _{1}e^{{\dfrac {-i2\pi }{8}}n}+\mathrm {f} _{2}e^{{\dfrac {-i2\pi }{8}}2n}+\mathrm {f} _{3}e^{{\dfrac {-i2\pi }{8}}3n}+\mathrm {f} _{4}e^{{\dfrac {-i2\pi }{8}}4n}+\mathrm {f} _{5}e^{{\dfrac {-i2\pi }{8}}5n}+\mathrm {f} _{6}e^{{\dfrac {-i2\pi }{8}}6n}+\mathrm {f} _{7}e^{{\dfrac {-i2\pi }{8}}7n}$

$\mathbf {(} F)_{n}={\Biggl [}\mathrm {f} _{0}+\mathrm {f} _{2}e^{{\dfrac {-i2\pi }{8}}2n}+\mathrm {f} _{4}e^{{\dfrac {-i2\pi }{8}}4n}+\mathrm {f} _{6}e^{{\dfrac {-i2\pi }{8}}6n}{\Biggr ]}+e^{{\dfrac {-i2\pi }{8}}n}{\Biggl [}\mathrm {f} _{1}+\mathrm {f} _{3}e^{{\dfrac {-i2\pi }{8}}2n}+\mathrm {f} _{5}e^{{\dfrac {-i2\pi }{8}}4n}+\mathrm {f} _{7}e^{{\dfrac {-i2\pi }{8}}6n}{\Biggr ]}$

$\mathbf {(} F)_{n}={\Biggl [}{\Biggl (}\mathrm {f} _{0}+\mathrm {f} _{4}e^{{\dfrac {-i2\pi }{8}}4n}{\Biggr )}+e^{{\dfrac {-i2\pi }{8}}2n}{\Biggl (}\mathrm {f} _{2}+\mathrm {f} _{6}e^{{\dfrac {-i2\pi }{8}}4n}{\Biggr )}{\Biggr ]}+e^{\dfrac {-i\pi {n}}{4}}{\Biggl [}{\Biggl (}\mathrm {f} _{1}+\mathrm {f} _{5}e^{-i\pi {n}}{\Biggr )}+e^{\dfrac {-i\pi {n}}{2}}{\Biggl (}\mathrm {f} _{3}+\mathrm {f} _{7}e^{-i\pi {n}}{\Biggr )}{\Biggr ]}$

MULTIPROCESSORS

A year ago (June 18th 2017) I posted on the issue [1] and got helpful advice. Now I want to ask more questions. There were hardware suggestions and I wonder if more advanced things are available now. First I want to describe what I want to do.

I need a GPU with a CPU or a number of CPU's like dual, or quadruple arrangement. I expect them to control the multitude of GPU's, perhaps 3,000. I will have a webcam and the images from the webcam will be read at a rate of perhaps 10 a second. Each flat image will be converted into an image on a virtual hemispherical surface by the CPU's. Then the image on the hemisphere will be divided (fragmented) into 3,000 or so portions to provide parallel treatment of the fragments. I expect that the GPU's will do that job. The treatment in the small fragments will amount to numerical integration. Then the CPU's will add calculated numbers and provide a multitude of combinations.

I've read that EVGA GeForce GTX TITAN has up to 7,000 gpu channels. I found some on Amazon[2] but they are not new, used. Is it safe to buy such? There is another model, though: [3]. But it has half of the CUDA channels than the previous model and is twice as expensive. Are there any better models now? AboutFace 22 (talk) 21:20, 5 May 2018 (UTC)

PAIRWISE SUMMATION

PAIRWISE SUMMATIONS I do a lot of computations, mostly in complex numbers. That includes multiplications and additions. Rounding errors accumulate and eventually become a problem. I found this article in Wikipedia [4] but it gives a pseudocode instead of C or C++ and it seems some information is missing.

I quote:

In pseudocode, the pairwise summation algorithm for an array x of length n > 0 can be written:

s = pairwise(x[1…n])
      if n ≤ N                    base case: naive summation for a sufficiently small array
          s = x[1]
          for i = 2 to n
              s = s + x[i]
      else                        divide and conquer: recursively sum two halves of the array
          m = floor(n / 2)
          s = pairwise(x[1…m]) + pairwise(x[m+1…n])
      endif

What is clear so far that the algorithm is recursive because the function calls upon itself, and then the input is an array of reals but I mostly operate with complex numbers. So, this is my thought on how it could be implemented in C, my OS is Linux Ubuntu:

dcomp is my definition of double complex. Suppose I have an array of 100 complex numbers to add, my typical situation. I expect to get one complex number in the end.

typedef std::complex<double> dcomp;

int main () {

int n = 100;
 dcomp ss, * xx;         // ss is the expected sum
 xx = new dcomp [n];     // array of input complex numbers, size of the array is n
 ss = pairwise (0, n, xx);

}

public : dcomp pairwise (int start, int end, dcomp * xx) {

int mm;
 dcomp ss;
 if (n <= N) {
   ss = xx[0];
   for (int ii = 1; ii < n; ii++) 
     ss += xx[ii];
  }
  else {
    mm = n/2;
    ss = pairwise(0,mm,xx) + pairwise(mm+1,n,xx);
  }
  return ss;

} // pairwise

I am not sure this code in this form will work. First, N is undefined. Obviously, N is an integer. Any hunch as to its possible value? My hunch is that iT is something like $N<<n$, but how is it defined? Also is it a number that changes during iterations? I must make this code work. I do have considerable loss of precision in my computations of significant practical value. I will appreciate any comments to improve the code. Thanks, - AboutFace 22 (talk) 16:16, 17 May 2018 (UTC)

The pseudocode clearly states that N is small enough to make "a sufficiently small array". The point is that you have to have a point at which you don't make a recursive call. You start adding. How small of an array do you think you need to be sure that you won't have rounding errors? That is how small N needs to be. Example: N=5. Then, when the array has 5 (or less) elements, you will just add them together and not perform a recursive call. 209.149.113.5 (talk) 18:56, 17 May 2018 (UTC)

Thank you. It makes sense. I will follow it, although it is unclear how it operates. I will think about it too. AboutFace 22 (talk) 22:28, 17 May 2018 (UTC)

You might also be interested in Kahan summation algorithm. Dmcq (talk) 22:57, 17 May 2018 (UTC)

I am familiar with it but it's considered much slower than pairwise and only slightly better in avoiding rounding errors. AboutFace 22 (talk) 19:45, 18 May 2018 (UTC)