ANOVA Model Fitting via Sparse Matrix Computations: A Fast Direct Method
George Ostrouchov · SIAM Journal on Scientific and Statistical Computing · 1989
A fast and storage-efficient direct method for fitting analysis-of-variance models to unbalanced data is presented. This method exploits sparsity and rank deficiency of the model matrix and is based on orthogonal Givens factorization of a set of sparse columns of the model matrix. A class of matrices generated by index sets is defined and used to obtain results on linear dependencies between columns of a model matrix and fill during factorization. These results are used to develop an algorithm for the selection, ordering, and symbolic factorization of a set of sparse columns of the model matrix. This facilitates a fast and storage-efficient numerical factorization and solution. A comparison to both a standard direct algorithm and a general-purpose sparse least-squares algorithm shows that the new algorithm reduces time and storage by orders of magnitude for large models and is competitive for small models.