  The thermal and expansion history of the Universe before big bang
nucleosynthesis is unknown. We investigate the evolution of cosmological
perturbations through the transition from an early matter era to radiation
domination. We treat reheating as the perturbative decay of an oscillating
scalar field into relativistic plasma and cold dark matter. After reheating, we
find that subhorizon perturbations in the decay-produced dark matter density
are significantly enhanced, while subhorizon radiation perturbations are
instead suppressed. If dark matter originates in the radiation bath after
reheating, this suppression may be the primary cutoff in the matter power
spectrum. Conversely, for dark matter produced nonthermally from scalar decay,
enhanced perturbations can drive structure formation during the cosmic dark
ages and dramatically increase the abundance of compact substructures. For low
reheat temperatures, we find that as much as 50% of all dark matter is in
microhalos with M > 0.1 Earth masses at z=100, compared to a fraction of 1e-10
in the standard case. In this scenario, ultradense substructures may constitute
a large fraction of dark matter in galaxies today.
