  Finite-temperature, grand-canonical computations based on field theory are
widely applied in areas including condensed matter physics, ultracold atomic
gas systems, and 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 which 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 {\it 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.
