  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
selection 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(n\log n)$ operations and
$O(n)$ storage. We perform various simulations to explore the effectiveness and
speed of the proposed methods and conclude by making inference on the
accumulation behavior of arsenic applied to a sand grain.
