search

raoyongming / GFNet

[NeurIPS 2021] [T-PAMI] Global Filter Networks for Image Classification
https://gfnet.ivg-research.xyz/
MIT License
450 stars 42 forks source link

Question about Complexity (FLOPs) #12

Closed techmonsterwang closed 2 years ago

techmonsterwang commented 2 years ago

Hi, interesting work! I wonder how the Complexity (FLOPs) for global filter in Table.1 is calculated. Since the conjugate symmetric for real signals, we have:

case1: consider the conjugate symmetric. RFFT: HWD/2 log2(HW) Global Filter: HWD/2 IRFFT: HWD/2 log2(HW)

Thus, the total Complexity (FLOPs) for global filter is: HWD * log2(HW) + HWD/2. Is it right?

case2: not consider the conjugate symmetric. RFFT: HWD log2(HW) Global Filter: HWD IRFFT: HWD log2(HW)

Thus, the total Complexity (FLOPs) for global filter is: 2HWD * log2(HW) + HWD. Is it right?

Which is right?

techmonsterwang commented 2 years ago

Oh, may be this is right?

case2: not consider the conjugate symmetric. RFFT: HWD/2 log2(HW) Global Filter: HWD IRFFT: HWD/2 log2(HW)

Thus, the total Complexity (FLOPs) for global filter is: HWD * log2(HW) + HWD. Is it right?

raoyongming commented 2 years ago

Hi, thanks for your interest in our work.

For a complex signal with a length of N, it requires N/2 log N complex-number multiplications to perform FFT. For 2D rFFT, the complexity should be W * (H/2 log H)/2 (1D FFT along the H dimension for a real signal) + H/2 * (W/2 log W) (1D FTT along the W dimension for a complex signal) = HW/4 log HW complex-number multiplications. Since 1 complex-number multiplication = 4 real-number multiplications, the complexity for the three operations are: rFFT: HWD log(HW), Global Filter: 2HWD irFFT: HWD log(HW)

The theoretical complexity may not be accurate on GPU due to the implementation. But our experiments show the actual complexity generally grows in proportion to O(HWD logHW).

techmonsterwang commented 2 years ago

Many thanks for the reply!

So maybe there is a mistake in table1 for flops? according to the reply？

---Original--- From: "Yongming @.> Date: Tue, Mar 8, 2022 15:40 PM To: @.>; Cc: "Wang @.**@.>; Subject: Re: [raoyongming/GFNet] Question about Complexity (FLOPs) (Issue #12)

Hi, thanks for your interest in our work.

For a complex signal with a length of N, it requires N/2 log N complex-number multiplications to perform FFT. For 2D rFFT, the complexity should be W (H/2 log H)/2 (1D FFT along the H dimension for a real signal) + H/2 (W/2 log W) (1D FTT along the W dimension for a complex signal) = HW/4 log HW complex-number multiplications. Since 1 complex-number multiplication = 4 real-number multiplications, the complexity for the three operations are: rFFT: HWD log(HW), Global Filter: 2HWD irFFT: HWD log(HW)

The theoretical complexity may not be accurate on GPU due to the implementation. But our experiments show the actual complexity generally grows in proportion to O(HWD logHW).

— Reply to this email directly, view it on GitHub, or unsubscribe. Triage notifications on the go with GitHub Mobile for iOS or Android. You are receiving this because you authored the thread.Message ID: @.***>

raoyongming commented 2 years ago

We have noticed the issue and added the big O notation in Table 1 in the camera-ready version of our paper. Please check the latest version (v2) on arXiv.

techmonsterwang commented 2 years ago

Thanks for reply！

---Original--- From: "Yongming @.> Date: Tue, Mar 8, 2022 17:08 PM To: @.>; Cc: "Wang @.**@.>; Subject: Re: [raoyongming/GFNet] Question about Complexity (FLOPs) (Issue #12)

We have noticed the issue and added the big O notation in Table 1 of the camera-ready version of our paper. Please check the latest version (v2) on arXiv.

— Reply to this email directly, view it on GitHub, or unsubscribe. Triage notifications on the go with GitHub Mobile for iOS or Android. You are receiving this because you authored the thread.Message ID: @.***>