COMPUTATIONALLY EFFICIENT CHOLESKY FACTORIZATION OF A COVARIANCE-MATRIX WITH BLOCK TOEPLITZ STRUCTURE

Many statistical procedures require some form of matrix factorization, and so can be computationally costly to implement for problems of large dimensions. However, it is often possible to reduce significantly overall computational costs by exploiting the structure of the matrix at hand. In this respect, a general analysis of the link between the amount of structure in a matrix and factorization costs has been recently reported in the literature and a whole class of fast factorization algorithms has been derived. In this paper, these recent results are invoked to derive a fast algorithm for the Cholesky factorization of a covariance matrix associated with a stationary spatial random field generated over a regular 2-D grid. The contribution of this paper is to derive explicitly the algorithm and show that it will run to completion in exact arithmetic. The factorization algorithm is particularly suited to parallel computation and remarkably simple to implement. In addition, with only minor modifications it extends to a fast Cholesky factorization of the inverse of the covariance matrix. As for issues of accuracy and run to completion, numerical experiments involving poorly conditioned covariance matrices indicate that the algorithm can be expected to perform as well as a standard Cholesky factorization.