We introduce computational methods that allow for effective estimation of a flexible, parametric non-stationary spatial model when the field size is too large to compute the multivariate normal likelihood directly. In this method, the field is defined as a weighted spatially varying linear combination of a globally stationary process and locally stationary processes. Often in such a model, the difficulty in its practical use is in the definition of the boundaries for the local processes, and therefore we describe one such selec tion procedure that generally captures complex non-stationary relationships. We generalize the use of stochastic approximation to the score equations for data on a partial grid in this non-stationary case and provide tools for evaluating the approximate score in O(nlogn) operations and O(n) storage. We apply these methods to the accumulation behavior of arsenic applied to a sand grain.