This proceedings contribution presents a novel, non-linear extension to the Lomb-Scargle periodogram that allows periodograms to be generated for arbitrary signal shapes. Such periodograms are already known as "template periodograms" or "periodic matched filters," but current implementations are computationally inefficient. The "fast template periodogram" presented here improves existing techniques by a factor of ∼a few for small test cases (O(10) observations), and over three orders of magnitude for lightcurves containing O(104) observations. The fast template periodogram scales asymptotically as O(HNf log HNf + H4Nf), where H denotes the number of harmonics required to adequately approximate the template and Nf is the number of trial frequencies. Existing implementations scale as O(NobsNf), where Nobs is the number of observations in the lightcurve. An open source Python implementation is available on GitHub.