Linear mixed models (LMMs) have become widely used for dealing with population structure in human GWAS, and they’re becoming increasing important for QTL mapping in model organisms, particularly for the analysis of advanced intercross lines (AIL), which often exhibit variation in the relationships among individuals.
In my efforts on R/qtl2, a reimplementation R/qtl to better handle highdimensional data and more complex cross designs, it was clear that I’d need to figure out LMMs. But while papers explaining the fit of LMMs seem quite explicit and clear, I’d never quite turned the corner to actually seeing how I’d implement it. In both reading papers and studying code (e.g., lme4), I’d be going along fine and then get completely lost partway through.
But I now finally understand LMMs, or at least a particular, simple LMM, and I’ve been able to write an implementation: the R package lmmlite.
It seemed worthwhile to write down some of the details.
The model I want to fit is y = X b + e, where var(e) = sK + tI, where K is a known kinship matrix and I is the identity matrix. Think of y as a vector of phenotypes and X as a matrix of covariates. Let v = s+t be the residual variance, and let h = s/(s+t) = s/v be the heritability.
First, a shout to Artem Tarasov, who wrote a series of blog posts walking through and explaining the source code for FaSTLMM and pylmm, and to Nick Furlotte, whose pylmm code is especially clear and easytoread. Only by reading their work did I come to understand these LMMs.
Back to the model fit:

For a fixed value of the heritability, h, we have var(e) = v[hK + (1h)I] = vV where V is known. And so we end up with a general least squares problem, which we can fit in order to estimate b and v.

And actually, if you take the eigen decomposition of K, say K = UDU', it turns out that you can write hK + (1h)I = hUDU' + (1h)UU' = U[hD + (1h)I]U'. That is, the eigenvectors of K are the same as the eigenvectors of hK + (1h)I. And so if you premultiply y and X by U', you end up with a weighted least squares problem, which is way faster to fit than a general least squares problem.

Having fit the weighted least squares problem to estimate b and v, you can then calculate the corresponding log likelihood (or, better, the restricted log likelihood, if you want to do REML).

You’re then left with a onedimensional optimization problem (optimizing the log likelihood over h), which you can solve by Brent’s method.

That’s it!
It seems quite obvious in retrospect. It’s a bit embarrassing that it’s taken me so long to come to this understanding.
In lmmlite, I implemented this algorithm (closely following the code in pylmm) twice: in plain R, and then in C++ (using RcppEigen, which is an interface to the Eigen C++ linear algebra library). The plain R code is a bit slower then pylmm; the C++ code is a bit faster. In the C++ code, almost all of the computation time is devoted to the eigen decomposition of the kinship matrix. Once that’s done, the rest is super quick.