ORDERING STRATEGIES TO REDUCE COMPUTATIONAL REQUIREMENTS IN VARIANCE COMPONENT ESTIMATION

摘要

Computational requirements for sparse matrix factorisation or inversion are highly dependent on the 'fill-in' created. This can be reduced by judicious re-ordering of equations. It is shown that use of newer ordering strategies, with corresponding computer code available in the public domain, can reduce the time required for ordering and computational requirements of analyses dramatically. Mixed model analyses of data from livestock improvement schemes generally involve manipulations of large, sparsematrices. In particular, estimation of variance components via restricted maximum likelihood (REML) requires the Cholesky decomposition or the inverse of the coefficient matrix as the mixed equations for each likelihood evaluation. Computational steps for this can be thought of as sequentially 'absorbing' one row and column into the remainder of the matrix. Clearly, the numbero of calculations required for each of these steps increases quadratically with the number of non-zero off-diagonal elements inthe row. Moreover, each step is likely to create additional, non-zero entries in the remaining rows and columns, commonly referred to as 'fill-in'. In turn, the amount of 'fill-in' determines computational requirements of subsequent steps.