The forward-backward method has been shown to be an effective iterative technique for the computation of scattering from one-dimensional rough surfaces, often converging rapidly even for very large surface heights. However, previous studies with this method have computed interactions between widely separated points on the surface exactly, resulting in an O(N ² ) computational algorithm that becomes intractable for large rough surface sizes, as are required when low grazing incidence angles are approached. An acceleration algorithm for more rapidly computing interactions between widely separated points in the forward-backward method is proposed in this paper and results in an O(N) algorithm with increasing surface size. The approach is based on a spectral domain representation of source currents and the Green's function and is developed for both perfectly conducting and impedance boundary surfaces. The method is applied in a Monte Carlo study of low grazing incidence backscattering from very rough (up to 10 m/s wind speed) ocean-like surfaces at 14 GHz and is found to require only a small fraction of the CPU time required by other competing methods; such as the banded matrix iterative approach/canonical grid and fast multipole methods.