We develop a fast and scalable method for computing Reduced-order Nonlinear Solutions (RONS). RONS is a recently proposed framework for reduced-order modeling of time-dependent partial differential equations (PDEs), where the reduced model depends nonlinearly on a set of time-varying parameters. RONS obtains an explicit set of ordinary differential equations (ODEs) for the parameters, which optimally evolve the shape of the approximate solution. However, a naive construction of these ODEs requires the evaluation of $\mathcal O(n^2)$ integrals, where $n$ is the number of model parameters. For high-dimensional models, the resulting computational cost becomes prohibitive. Here, exploiting the structure of the RONS equations and using symbolic computing, we develop an efficient computational method which requires only $\mathcal O(K^2)$ integral evaluations, where $K\ll n$ is an integer independent of $n$. Our method drastically reduces the computational cost and allows for the development of highly accurate spectral methods where the modes evolve to adapt to the solution of the PDE, in contrast to existing spectral methods where the modes are static in time.