In this work we present a novel full-vectorial fast Fourier transform (FFT) based mode solver to analyze arbitrarily shaped optical dielectric waveguides. The method is computationally efficient not only in computing time but also in memory requirements, thus overcoming some of the drawbacks of previously published Fourier decomposition methods (FDMs) mode solvers. To assess the method four different strongly guiding waveguides of practical interest have been analyzed: a step-index fiber, a photonic crystal fiber (PCF), a rectangular rib waveguide and finally a trapezoidal rib waveguide in silicon-on-insulator (SOI) technology. Obtained results clearly confirm the accuracy and efficiency of the proposed method