APPLICATION OF GRAPH THEORY TO THE ORDERING OF LARGE SURVEY NETWORKS

AbstractMany researchers in surveying, geodesy and photogrammetry have a need for an efficient method of solving large, sparse sets of linear equations. Over the past decade or so, much research on this problem has been reported in the applied mathematics literature, but little of this material has found its way into the surveying literature. This paper surveys some modern algorithms, based on graph theory, for reordering systems of linear equations so as to reduce the bandwidth or the profile of the coefficient matrix, in order to improve the efficiency of solutions based on treating the coefficient matrix as having a banded, or a low profile, structure. Block elimination methods, based on partitioning the reordered coefficient matrix, and suited to the factorisation of a symmetric matrix such as those encountered in many surveying applications, are also briefly considered.