  Regression models with crossed random effect errors can be very expensive to
compute. The cost of both generalized least squares and Gibbs sampling can
easily grow as $N^{3/2}$ (or worse) for $N$ observations. Papaspiliopoulos et
al. (2020) present a collapsed Gibbs sampler that costs $O(N)$, but under an
extremely stringent sampling model. We propose a backfitting algorithm to
compute a generalized least squares estimate and prove that it costs $O(N)$. A
critical part of the proof is in ensuring that the number of iterations
required is $O(1)$ which follows from keeping a certain matrix norm below
$1-\delta$ for some $\delta>0$. Our conditions are greatly relaxed compared to
those for the collapsed Gibbs sampler, though still strict. Empirically, the
backfitting algorithm has a norm below $1-\delta$ under conditions that are
less strict than those in our assumptions. We illustrate the new algorithm on a
ratings data set from Stitch Fix.
