Practical method to solve large least squares problems using Cholesky decomposition

Abstract

In Geomatics, the method of least squares is commonly used to solve the systems of observation equations for a given number of unknowns. This method is basically implemented in case of having number observations larger than the number of unknowns. Implementing the large least squares problems would require a large storage on the hard drive to store the different matrices for applying the solution. The computational time for solution would extremely increase with increasing number of unknowns and observations. The calculation of the inverse of the normal equation matrix will get more complex using the traditional methods with higher numbers of unknowns. Here, practical methods to eliminate the required storage and computations times during the solution are introduced. The Cholesky decomposition will be used to solve the systems of equations in order to avoid the complexity of the matrix inversion and to guarantee faster solutions. A block matrix implementation of Cholesky decomposition is to be used to enable the management of the memory and its limitations through the solutions. The principle of threading, which is supported in most of the programming languages like C++ or Java, is implemented to use the computer resources especially all available central processing units (CPU). This principle can be implemented over networks of computers to use of the resources of more available computers working under common servers.

Keyword : systems of equations, least squares solutions, matrix, matrix inverse, Cholesky decomposition, block matrix, normal equations matrix, threading, parallel processing