In this talk we discuss a framework for computing accurate approximate variances in large scale Gaussian Markov Random Fields. We start by motivating the need to compute variances in GMRFs, and discuss related problems in machine learning. Our approach is based on constructing a certain low-rank aliasing matrix which takes advantage of the Markov graph of the model. We first construct such a matrix for models with short-range correlation, and then describe a wavelet-based construction for models with long-range correlation. The approach is based on fast solution of sparse linear systems, and we describe suitable preconditioners. We also describe how the approach can be used for problems with sparse plus low-rank structure, for example in approximate Kalman filtering with large state spaces.