Finite-temperature grand-canonical computations based on field theory are widely applied in areas including condensed matter physics, ultracold atomic gas systems, and the lattice gauge theory. However, these calculations have computational costs scaling as N_{s}^{3} with the size of the lattice or basis set, N_{s}. We report a new approach based on systematically controllable low-rank factorization that reduces the scaling of such computations to N_{s}N_{e}^{2}, where N_{e} is the average number of fermions in the system. In any realistic calculations aiming to describe the continuum limit, N_{s}/N_{e} is large and needs to be extrapolated effectively to infinity for convergence. The method thus fundamentally changes the prospect for finite-temperature many-body computations in correlated fermion systems. Its application, in combination with frameworks to control the sign or phase problem as needed, will provide a powerful tool in ab initio quantum chemistry and correlated electron materials. We demonstrate the method by computing exact properties of the two-dimensional Fermi gas with zero-range attractive interaction as a function of temperature in both the normal and superfluid states.