Abstract
In this paper several ordering algorithms for the unknowns in geodetic least squares systems are compared. The comparison is restricted to the case of the well known Cholesky factorization of the normal matrixA into a lower triangular factorL. p ]The algorithms which were investigated are: minimum degree, minimum deficiency, nested dissection, reverse Cuthill-McKee, King's-, Snay's-, and Levy's-banker's and Gibbs-King. p ]Also some strategies are presented to reduce the time needed to compute the ordering using a priori information about the way the unknowns are connected to each other. p ]The algorithms are applied to normal matrices of the least squares adjustment of 2D geodetic terrestrial networks, photogrammetric bundle-block adjustments, and a photogrammetric adjustment using independent models. p ]The results show that ordering the unknowns yields a considerable decrease of the cpu time for computing the Cholesky factor, and that in general the minimum degree and Snay's banker's ordering perform best. Furtheron they show that a priori information about the connection structure of the unknowns speeds up the computation of the ordering substantially.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Cuthill, E., McKee, J. (1969) Reducing the bandwidth of sparse symmetric matrices. In Proceedings 24th National Conference ACM. ACM publication no. P- 69, Brandon Systems Press, NJ.
Dongarra, J.J., Grosse, E. (1987) Distribution of mathematical software via electronic mail. In Comm. ACM 30, pp. 403–407.
George, A., Liu, J.W.H. (1979) An implementation of a pseudo-peripheral node finder. In ACM Trans. on Math. Softw., Vol. 5, pp. 286–295.
George, A., Liu, J.W.H. (1980) A fast implementation of the minimum degree algorithm using quotient graphs. In ACM Trans. on Math. Softw., Vol. 6, No. 3, pp. 337–358.
George, A., Liu, J.W. (1981) Computer solution of large sparse positive definite systems, Prentice-Hall, Englewood Cliffs, NJ.
George, A., Liu, J.W. (1989) The evolution of the minimum degree ordering algorithm. In SIAM Review, Vol. 31, No. 1, pp. 1–19.
Gibbs, N.E. (1976) A hybrid profile reduction algorithm. In ACM Trans. on Math. Softw., Vol. 2, No. 4, pp. 378–387.
Gibbs, N.E., Poole, W.G., Stockmeyer, P.K. (1976) An algorithm for reducing the bandwidth and profile of a sparse matrix. In SIAM J. Numer. Anal., Vol. 13, No. 2, pp. 236–250.
Jonge de, P.J. (1987) On the ordering of the unknowns during the Hipparcos reduction on circles. Graduate thesis Department of Geodesy, Delft University of Technology.
Jonge de, P.J. (1991) An analysis of ordering schemes for the unknowns during the solving of geodetic least squares systems, Reports of the Faculty of Geodetic Engineering/Dept. of Mathematical and Physical Geodesy, Delft University of Technology, 91.4.
King, I.P. (1970) An automatic reordering scheme for simultaneous equations derived from network systems. In Int. J. Numer. Meth. Eng., Vol. 2, pp. 497–509.
Levy, R. (1971) Restructuring of the structural stiffness matrix to improve computational efficiency. In Jet Propulsion Laboratory Technical Review. 1, pp. 61–70.
Marel, van der, H. (1988) On the “great circle reduction” in the data analysis for the astrometric satellite Hipparcos. Netherlands Geodetic Commission, Publications on Geodesy New Series, Vol. 8(2).
Parter, S. (1961) The use of linear graphs in Gauss elimination. In SIAM Review, Vol. 3, No. 2, pp. 119–130.
Pissanetzky, S. (1984) Sparse matriz technology. Academic Press, London.
Snay, R.A. (1976) Reducing the profile of sparse symmetric matrices. In Bulletin Geodesique, Vol. 50, pp. 341–352.
Author information
Authors and Affiliations
Additional information
Supported by the Netherlands Organization for Scientific Research (NWO)
Rights and permissions
About this article
Cite this article
de Jonge, P.J. A comparative study of algorithms for reducing the fill-in during Cholesky factorization. Bulletin Geodesique 66, 296–305 (1992). https://doi.org/10.1007/BF02033190
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02033190