atatomir's blog

Fast Fourier Transform and variations of it
By atatomir, 8 years ago, In English

Hello Codeforces !

I invite all of you to read my first article. It is about Fast Fourier Transform and other two linear transformations. Feel free to comment and ask any question that comes into your mind. Any positive or negative feedback is welcome, too.

Link : https://csacademy.com/blog/fast-fourier-transform-and-variations-of-it

  • Vote: I like it
  • +107
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Thank you for this article. How can the bitwise xor formula be proved for Walsh-Hadamard transform?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hi Nikita, I added some information about that in the article. (in section "How to determine the Walsh-Hadamard Matrix (my approach)"). Thank you!

    → Reply
»
8 years ago, # |
  Vote: I like it +33 Vote: I do not like it

You got two things slightly wrong. Fast Walsh–Hadamard transform is very quite like FFT. Walsh-Hadamard transformation is just N-dimensional version of Fourier Transform. You do not xor the powers of x, you multiply monoms of N variables (by modulo x2-1 for each variable of course).

There are multiple ways to calculate N-dimensional Fourier Transform. The trivial one is to make Fourier Transform along each dimension. If you use "slow" version of transform, you will need O((N1+N2+...+Nk)N1N2...Nk) time for N1×N2×...×Nk k-dimensional hypercube. If you use FFT for each transform, you will need O((log(N1)+log(N2)+...+log(Nk))N1N2...Nk) time. There are other algorithms, some of which even work for O(N1N2...Nk) time for some hypercubes.

The second thing, you can create N-dimensional version of any linear transformation. There is no need "to do some math". Just choose any invertible matrix and create N-dimensional version of the matrix and its inverse just like in N-dimensional Fourier Transform. In practice, I have never seen anything other than three ones and one zero 2×2 matrices or their inverses though.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Hi Andrey, I would like to thank you for reading my article. I tried to do my best reproducing what helped me to understand FFT better. I know that "using xor at power" is not the best mathematical explanation, but i found it useful. However, I wish you enjoyed the article. Any other suggestion is welcome, too :)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +34 Vote: I do not like it

      Now that you know a better mathematical model, use it! You should probably also mention how to do FFT over whole numbers by choosing a good modulo. It is very common technique.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    As a side note, the Walsh transform is used a lot in cryptography. It allows to measure "linearity" of a boolean function. Just apply FWHT to the truth table with 0s replaced by -1. The resulting values tell how "good" is each mask m as a linear approximation  < m, x >  (scalar product over ) of the original boolean function .

    Also quite often the notation is used, so the atatomir's "xor at power" is ok. Maybe the multidimensional view of it allows to explain it better, but I still don't get it. Mainly, how each dimension's FFT is connected with others?

    The second thing, you can create N-dimensional version of any linear transformation.

    The fact that we can do "binary AND at powers" really surprised me, as I don't see what exactly is linear here. What are the limitations of FFT? In what cases the desired transformation will be nonlinear?

    There is no need "to do some math". Just choose any invertible matrix and create N-dimensional version of the matrix and its inverse ...

    I guess the "math" here is to find the right matrix (for example for binary AND). Is there a simple way?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Hi hellman1908, Thank you for your appreciation. I did't know this use of FWHT (in cryptography). I was really surprised when i found the matrix for and, too. I can guess that the matrix for or can be also determined. The method that i used to find it is similar to the one presented in the article (section "How to determine the Walsh-Hadamard Matrix (my approach)"). Just change the result of convolution. This lack of limitations of FFT fascinated me. You can use (+, -, xor, and, or). Another interesting approach of FFT is to replace complex roots with roots of unit in modulo (halyavin suggestion).

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    I don't really get how to do N-dimensional Fourier Transform. What would be the Point-value Representation for a N-variable polynomial?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      Instead of

      we have

      .

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

        So which point values would we choose to evaluate? All n-tuples of roots of unities?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +18 Vote: I do not like it

          All n-tuples of roots of unities?

          Exactly!

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +13 Vote: I do not like it

            When we calculate the inverse FFT instead we divide by n, so if we want to calculate inverse for n-dimensional FFT we will divide by n1n2...nk?

            → Reply
»
8 years ago, # |
  Vote: I like it +63 Vote: I do not like it

Who is the target audience for your article? It looks like a person should already know about polynomials, polynomial interpolation (as you assume that two representations of polynomials are obviously correct), and have a pretty solid understanding of everything except FFT in order to understand it.

I find the article to be very brief and sketchy, for me it looks more like a "memo for those who already know FFT" rather than a full-blown educational article which tells you how and why it works. There is an idea and after three lines it suddenly becomes recursive implementation, and in the next paragraph you go right to the non-recursive implementation, without any comments or thought about how it was done. I personally think that code is fine for demonstrating implementation details of an algorithm, but not for describing the algorithm itself.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it +21 Vote: I do not like it

    Hi Egor, All I wanted to do is to make an introduction to FFT and present two other linear transformations that can run in O(n*log(n)). I still have a lot to learn in order to present a more complex article. That's what i could write for the moment. Thank you for your feedback.

    → Reply
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Seems related to these two TC editorials (D1-1000):

https://apps.topcoder.com/wiki/display/tc/SRM+518 https://apps.topcoder.com/wiki/display/tc/TCO+2012+Round+2A

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You are right. I used the solution of task Nim from SRM 518 as starting point to find the last matrix. ;)

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks for that article. Excuse but I wonder that can we use a fast tranform for the min-max operator ? sorry for my poor english !

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    Thank you for your question :) You do not need to use FFT in this case. Some simple partial sums are enough. I will present the solution for the MAX operator. Let a[i] = coefficient of x^i; s[i] = sum of coefficient of x^j (where j <= i); If you want to compute the resulting coefficient of x^i you can apply the following formula: ans[i] = 2 * a[i] * s[i-1] + a[i] * a[i]. (only if you "multiply" one polynomial with itself, otherwise use a1, s1, a2, s2) If you want to compute the number of subsets of a set that have their max equal to i then the following formula should work : ans[i] = (2^(a[i]) — 1) * (2^(s[i — 1])). Please let me know if you have other questions or if anything above seems unclear :)

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

Great article!

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

I think the correct H matrix for XOR in Fast Walsh–Hadamard transform is for n > 2 and where n is number of polynomial elements (degree(polynomial) + 1). Because if it was for n > 2 and , The appropriate steps to be taken for multiplication without using the would be:

  1. Transform using
  2. Transform using
  3. Multiply in using
  4. Transform using
  5. Divide by to get PQ

But since we are dividing only by n at the end regardless of the multiplications done in step 3, the correct H should be as I mentioned in the beginning, and so its inverse would be for n > 2 and . And this explains why division by n at the end is enough, as .

Is this correct or did I miss something?

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hi. So I am very new to these convolutions stuff. I have learnt how the FFT DnC algorithm works. However I am not able to correlate a similar fast walsh-hadamard transform algorithm from the H matrices itself. Could someone give some resource/ explain how we exactly formulate the algorithm from this recursively defined matrix...

(PS: It would be nice if you could also give an intuition as to how the vandermonde matrix is related to FFT, as its not immediately clear for me from the algorithm.) Thanks for any help.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Hello,

I came across this post while trying to solve Winning Ways (MDSWIN) from November Challenge 2019 on CodeChef. I tried probably not enough to derive 3x3 transformation matrix for "3-xor" using the method from article but failed. Can anyone show the fast derivation? Editorial is here

Thank you very much

UPD: the discussion was really helpful

→ Reply