Observed galaxy clustering exhibits local transverse statistical isotropy around the line of sight (LOS). The variation of the LOS across a galaxy survey complicates the measurement of the observed clustering as a function of the angle to the LOS, as fast Fourier transforms (FFTs) based on Cartesian grids, cannot individually allow for this. Recent advances in methodology for calculating LOS-dependent clustering in Fourier space include the realization that power spectrum LOS-dependent moments can be constructed from sums over galaxies, based on approximating the LOS to each pair of galaxies by the LOS to one of them. We show that we can implement this method using multiple FFTs, each measuring the LOS-weighted clustering along different axes. The Nlog N nature of FFTs means that the computational speed-up is a factor of >1000 compared with summing over galaxies. This development should be beneficial for future projects such as DESI and Euclid which will provide an order of magnitude more galaxies than current surveys.