Estimates of variances and covariances by restricted maximum likelihood (REML) have desirable properties but can be very expensive to compute. Strategies are presented which may make REML estimates easier to obtain in many models used by animal breeders. A strategy which can greatly reduce costs is to obtain only upper and lower bounds on traces used in computing REML estimates rather than obtaining exact values with inversion. This strategy is effective when the mixed model equations are very large. For smaller sized problems, diagonalization of the system of equations before iteration begins is warranted;An algorithm is developed which guarantees positive definite estimated variance-covariance matrices in multiple-trait problems. By constraining eigenvalues to remain above zero, this algorithm can converge to a point arbitrarily close to the edge of the parameter space, yielding an "almost" singular matrix, without encountering numerical problems. Similarly, by applying upper constraints to eigenvalues, heritabilities of all traits and all linear combinations of traits can be forced to remain below one. Multiple-trait REML estimates of variances and covariances are produced by this algorithm for about the same cost as would be required to estimate variances only using single-trait REML. A limitation of the algorithm is that all traits must be measured on all animals;A Fortran program was developed which incorporates many of these cost-saving features. The program handles single- or multiple-trait problems, related or unrelated sires, genetic groups or no genetic groups, and computes with either an exact procedure (diagonalization) or approximate procedures (estimates of traces). The program was applied to four data sets of colleagues, the largest one including 49,918 records from 428 sires. Multiple-trait REML estimates of variances and covariances for a model including relationships in this largest data set were obtained with a computing time of 568 CPU seconds and cost of 200. The algorithms presented may make more widespread use of REML estimation possible.