The problem of verifying the nonnegativity of a real valued function on a finite set is a long-standing challenging problem, which has received extensive attention from both mathematicians and computer scientists. Given a finite set $X$ together with a function $F:X \to \mathbb{R}$, if we equip $X$ a group structure $G$ via a bijection $\varphi:G \to X$, then effectively verifying the nonnegativity of $F$ on $X$ is equivalent to computing a sparse Fourier sum of squares (FSOS) certificate of $f=F\circ \varphi$ on $G$. In this talk, we show that by performing the fast (inverse) Fourier transform, we are able to compute a sparse FSOS certificate of $f$ on $G$ with complexity $\operatorname{O}(|G|\log |G| + |G| t^4 + \operatorname{poly}(t))$, which is quasi-linear in the order of $G$ and polynomial in the FSOS sparsity $t$ of $f$. We demonstrate the efficiency of the proposed algorithm by numerical experiments on various abelian groups of order up to $10^6$.