An efficient and widely used method of analysis for multi-environment trial (MET) data in plant improvement programs involves a linear mixed model with a factor analytic (FA) model for the variety by environment effects. The variance structure is generally constructed as the kronecker product of two matrices that relate to the variety and environment dimensions, respectively. In many applications, the FA variance structure is assumed for the environment dimension and either an identity matrix or a known matrix, such as the numerator relationship matrix, is used for the variety dimension. The factor analytic linear mixed model can be fitted to large and complex MET datasets using the sparse formulation of the average information algorithm of Thompson et al. (Aust N Z J Stat 45:445–459, 2003) or the extension provided by Kelly et al. (Genet Sel Evo, 41:1186–1297, 2009) for the case of a known non-identity matrix for the variety dimension. In this paper, we present a sparse formulation of the average information algorithm for a more general separable variance structure where all components are parametric and one component has an FA structure. The approach is illustrated using a large and highly unbalanced MET dataset where there is a factorial treatment structure. Supplementary materials accompanying this paper appear online.