The attention module, which is a crucial component in Transformer, cannot\nscale efficiently to long sequences due to its quadratic complexity. Many works\nfocus on approximating the dot-then-exponentiate softmax function in the\noriginal attention, leading to sub-quadratic or even linear-complexity\nTransformer architectures. However, we show that these methods cannot be\napplied to more powerful attention modules that go beyond the\ndot-then-exponentiate style, e.g., Transformers with relative positional\nencoding (RPE). Since in many state-of-the-art models, relative positional\nencoding is used as default, designing efficient Transformers that can\nincorporate RPE is appealing. In this paper, we propose a novel way to\naccelerate attention calculation for Transformers with RPE on top of the\nkernelized attention. Based upon the observation that relative positional\nencoding forms a Toeplitz matrix, we mathematically show that kernelized\nattention with RPE can be calculated efficiently using Fast Fourier Transform\n(FFT). With FFT, our method achieves $\\mathcal{O}(n\\log n)$ time complexity.\nInterestingly, we further demonstrate that properly using relative positional\nencoding can mitigate the training instability problem of vanilla kernelized\nattention. On a wide range of tasks, we empirically show that our models can be\ntrained from scratch without any optimization issues. The learned model\nperforms better than many efficient Transformer variants and is faster than\nstandard Transformer in the long-sequence regime.\n