The existence of an optimal reverse-waterfilling algorithm to compute the nonanticipative rate distortion function (NRDF) for time-invariant vector-valued Gauss-Markov processes with a mean-squared-error distortion has been an open question since the pioneering work of Tatikonda et al. on stochastic linear control over a communication channel, in 2004. In this article, we derive strong structural properties on the time-invariant multidimensional Gauss-Markov processes that allow for an optimization problem that can be computed optimally via a reverse-waterfilling algorithm. Moreover, we propose an elegant optimal iterative scheme that computes this reverse-waterfilling algorithm. We show that the specific scheme operates much faster than any existing algorithmic approach that solves the same problem optimally and is also scalable. Finally, using our new results, we derive for the first time a nontrivial analytical solution of the asymptotic NRDF using a correlated time-invariant 2-D Gauss-Markov process.