The superiority of iterative reconstruction techniques over classic analytical ones is well documented in a variety of CT imaging applications where radiation dose and sampling time are limiting factors. However, by definition, the iterative nature of advanced reconstruction techniques is accompanied by a substantial increase in data processing time. This problem is further exacerbated in temporal and spectral CT reconstruction problems where the gap between the amount of data acquired and the amount of data to be reconstructed is exaggerated within the framework of compressive sensing. Two keys to overcoming this barrier include (1) advancements in parallel-computing technology and (2) advancements in data-efficient reconstruction. In this work, we propose a novel, two-stage strategy for 4D cardiac CT reconstruction which leverages these two keys by (1) exploiting GPU computing hardware and by (2) reconstructing temporal contrast on a limited spatial domain. Following a review of the proposed algorithm, we demonstrate its application in retrospectively gated cardiac CT reconstruction using the 4D MOBY mouse phantom. Quantitatively, reconstructing the temporal contrast on a limited domain reduces the overall reconstruction error by 20% and the reconstruction error within the dynamic portion of the phantom by 15% (root-mean-square error metric). A complementary in vivo mouse experiment demonstrates a suitable reconstruction fidelity to allow the measurement of cardiac functional metrics while reducing computation time by 75% relative to direct reconstruction of ten phases of the cardiac cycle. We believe that the proposed algorithm will serve as the basis for novel, data-efficient, multi-dimensional CT reconstruction techniques.