To study wave scattering from random lossy dielectric rough surfaces with large permittivities using the method of moments, a dense grid is needed for accurate results. A dense grid requires more CPU and memory. The physics-based two-grid (PBTG) method can reduce both CPU and memory requirements. In this paper, the PBTG is used in conjunction with the multilevel fast multipole method (FMM) to solve wave scattering from one-dimensional random lossy dielectric rough surfaces. The proposed algorithm has the computational complexities of O(Ndg) for near-field interactions and O(Ncg) for nonnear-field interactions, where Ndg and Ncg are the number of sampling points on the dense and coarse grids, respectively. Using the proposed algorithm, wave scattering from Gaussian and non-Gaussian rough surfaces is investigated and illustrated. Special emphasis is put on checking the accuracy of the algorithm and energy conservation. ¿ 2001 American Geophysical Union