In cuDNN v3, algorithm CUDNN_CONVOLUTION_FWD_ALGO_FFT worked with half precision tensors, ie, CUDNN_DATA_HALF format tensors.
In cuDNN v4, it seems to be no longer supported, contrary to the documentation.
cudnnGetConovlutionForwardWorkspaceSize always returns cudnnStatusNotSupported, and cudnnGetConvolutionForwardAlgorithm will not select FFT or FFT_TILING algorithms for any layer parameters when the tensor data types are half precision.
I am using a Titan X on Ubuntu 14.04.