Algebraic Geodesy and Geoinformatics

This chapter presents the concepts of ring theory from a geodetic and geoinformatics perspective. The presentation is such that the mathematical formulations are augmented with examples from the two fields. Ring theory forms the basis upon which polynomial rings operate. As we shall see later, exact solution of nonlinear systems of equations are pinned to the operations on polynomial rings. In Chap. 3, polynomials will be discussed in detail. In order to understand the concept of polynomial rings, one needs first to be familiar with the basics of ring theory. This chapter is therefore a preparation for the understanding of the polynomial rings presented in Chap. 3. Ring of numbers which is presented in Sect. 2-2 plays a significant role in daily operations. They permit operations addition, subtraction, multiplication and division of numbers.

In geodesy and geoinformatics, most observations are related to unknowns parameters through equations of algebraic (polynomial) type. In cases where the observations are not of polynomial type, as exemplified by the GPS meteorology problem of Chap. 15, they are converted via Theorem3.1 on p. 19 into polynomials. The unknown parameters are then be obtained by solving the resulting polynomial equations. Such solutions are only possible through application of operations addition and multiplication on polynomials which form elements of polynomial rings. This chapter discusses polynomials and the properties that characterize them. Starting from the definitions of monomials, basic polynomial aspects that are relevant for daily operations are presented.

This chapter presents you the reader with one of the most powerful computer algebra tools, besides the polynomial resultants (discussed in the next chapter), for solving nonlinear systems of equations which you may encounter. The basic tools that you will require to develop your own algorithms for solving problems requiring closed form (exact) solutions are presented. This powerful tool is the “Gröbner basis” written in English as Groebner basis. It was first suggested by B. Buchberger in 1965, a PhD student of Wolfgang Groebner (1899 - 1980). Groebner, already in 1949, had suggested a method for finding a linearly independent basis of the vector space of the residue class ring of the polynomial ring modulo a polynomial ideal. In studying termination of this method, Buchberger came up both with the notion of Groebner bases (certain generating sets for polynomial ideals) and with an always terminating algorithm for computing them. In 1964, H. Hironaka (1931-) had independently introduced an analogous notion for the domain of power series in connection with his work on resolution of singularities in algebraic geometry and named it standard basis [262, p. 187]. However, he did not give any method for computing these bases.

Besides Groebner basis approach discussed in Chap. 4, the other powerful algebraic tools for solving nonlinear systems of equations are the polynomial resultants approaches. While Groebner basis may require large storage capacity during its computations, polynomial resultants approaches presented herein offers remedy to users who may not be lucky to have computers with large storage capacities. This chapter presents polynomial resultants approaches starting from the resultants of two polynomials, known as the “Sylvester resultants”, to the resultants of more than two polynomials in several variables known as “multipolynomial resultants”. In normal matrix operations in linear algebra, one is often faced with the task of computing determinants. Their applications to least squares approach are well known.

A fundamental task in geodesy is the solving of systems of equations. Many geodetic problems are represented as systems of multivariate polynomials. A common problem in solving such systems is improper initial starting values for iterative methods, leading to the convergence to solutions with no physical meaning, or convergence that requires global method. Although symbolic methods such as Groebner bases or resultants have been shown to be very efficient, i.e., providing solutions for determined systems such as 3-point problem of 3D affine transformation, the symbolic algebra can be very time consuming, even with special Computer Algebra Systems (CAS). This Chapter proposes the Linear Homotopy method that can be implemented easily in high level computer languages like C++ and Fortran, which are faster than CAS by at least two orders of magnitude. Using Mathematica, the power of Homotopy is demonstrated by solving three nonlinear geodetic problems: resection, GPS positioning and affine transformation. The method enlarging the domain of convergence is found to be efficient, less sensitive to rounding errors, and has a lower complexity compared to other local methods like Newton-Raphson.

In geodesy and geoinformatics, field observations are normally collected with the aim of estimating parameters. Very frequently, one has to handle overdetermined systems of nonlinear equations. In such cases, there exist more equations than unknowns, therefore “the solution” of the system can be interpreted only in least squares sense.

In geodynamics for example, GPS and gravity measurements are undertaken with the aim of determining crustal deformation. With improvement in instrumentation, more observations are often collected than the unknowns. Let us consider a simple case of measuring structural deformation. For deformable surfaces, such as mining areas, or structures (e.g., bridges), several observable points are normally marked on the surface of the body. These points would then be observed from a network of points set up on a non-deformable stable surface. Measurements taken are distances, angles or directions which are normally more than the unknown positions of the points marked on the deformable surface leading to redundant observations.

In Chap. 7, we have seen that overdetermined nonlinear systems are common in geodetic and geoinformatic applications, that is there are frequently more measurements than it is necessary to determine unknown variables, consequently the number of the variables n is less then the number of the equations m. Mathematically, a solution for such systems can exist in a least square sense.

This chapter presents the minimization approach known as “Procrustes” which falls within the multidimensional scaling techniques discussed in Sect. 9-22. Procrustes analysis is the technique of matching one configuration into another in-order to produce a measure of match. In adjustment terms, the partial Procrustes problem is formulated as the least squares problem of transforming a given matrix \( {\mathbf A} \) into another matrix \( {\mathbf B} \) by an orthogonal transformation matrix \( {\mathbf T} \) such that the sum of squares of the residual matrix \( {\mathbf E} = {\mathbf A} - {\mathbf {BT}} \) is minimum. This technique has been widely applied in shape and factor analysis. It has also been used for multidimensional rotation and also in scaling of different matrix configurations. In geodesy and geoinformatics, data analysis often require scaling, rotation and translation operations of different matrix configurations. Photogrammetrists, for example, have to determine the orientation of the camera during aerial photogrammetry and transform photo coordinates into ground coordinates. This is achieved by employing scaling, translation and rotation operations. These operations are also applicable to remote sensing and Geographical Information System (GIS) where map coordinates have to be transformed to those of the digitizing table. In case of robotics, the orientation of the robotic arm has to be determined, while for machine and computer visions, the orientation of the Charge-Coupled Device (CCD) cameras has to be established. In practice, positioning with satellites, particularly the Global Navigation Satellite Systems (GNSS) such us GPS and GLONASS has been on rise. The anticipated GALILEO satellites will further increase the use of satellites in positioning. This has necessitated the transformation of coordinates from the Global Positioning System (WGS 84) into local geodetic systems and vice versa.

Since the advent of the Global Navigation Satellite System (GNSS) , in particular the Global Positioning System (GPS), many fields within geosciences, such as geodesy, geoinformatics, geophysics, hydrology etc., have undergone tremendous changes. GPS satellites have in fact revolutionized operations in these fields and the entire world in ways that its inventors never imagined. The initial goal of GPS satellites was to provide the capability for the US military to position themselves accurately from space. This way, they would be able to know the positions of their submarines without necessarily relying on fixed ground stations that were liable to enemy attack. Slowly, but surely, the civilian community, led by geodesists, began to devise methods of exploiting the potential of this system. The initial focus of research was on the improvement of positioning accuracies since civilians only have access to the so called coarse acquisition or C/A-code of the GPS signal. This code is less precise when compared to the P-code used by the US military and its allies. The other source of error in GPS positioning was the Selective Availability (SA) , i.e., intentional degradation of the GPS signal by the US military that would lead to a positioning error of ±100 m. However, in May 2000, the then president of the United States Bill Clinton, officially discontinued this process.

In establishing a proper reference frame of geodetic point positioning, namely by the Global Positioning System (GPS) - the Global Problem Solver - we are in need to establish a proper model for the Topography of the Earth, the Moon, the Sun or planets.By the theory of equilibrium figures, we are informed that an ellipsoid, two-axes or three-axes is an excellent approximation of the Topography. For planets similar to the Earth the biaxial ellipsoid, also called “ellipsoid-of-revolution” is the best approximation.

Throughout history, position determination has been one of the fundamental task undertaken by man on daily basis. Each day, one has to know where one is, and where one is going. To mountaineers, pilots, sailors etc., the knowledge of position is of great importance. The traditional way of locating one’s position has been the use of maps or campus to determine directions. In modern times, the entry into the game by Global Navigation Satellite Systems GNSS that comprise the Global Positioning System (GPS), Russian based GLONASS and the proposed European’s GALILEO have revolutionized the art of positioning.

In Chap. 12, ranging method for positioning was presented where distances were measured to known targets. In this chapter, an alternative positioning technique which uses direction measurements as opposed to distances is presented. This positioning approach is known as the resection. Unlike in ranging where measured distances are affected by atmospheric refraction, resection methods have the advantage that the measurements are angles or directions which are not affected by refraction.

The similarity between resection methods presented in the previous chapter and intersection methods discussed herein is their application of angular observations. The distinction between the two however, is that for resection, the unknown station is occupied while for intersection, the unknown station is observed. Resection uses measuring devices (e.g., theodolite, total station, camera etc.) which occupy the unknown station. Angular (direction) observations are then measured to three or more known stations as we saw in the preceding chapter. Intersection approach on the contrary measures angular (direction) observations to the unknown station; with the measuring device occupying each of the three or more known stations. It has the advantage of being able to position an unknown station which can not be physically occupied. Such cases are encountered for instance during engineering constructions or cadastral surveying. During civil engineering construction for example, it may occur that a station can not be occupied because of swampiness or risk of sinking ground. In such a case, intersection approach can be used. The method is also widely applicable in photogrammetry. In aero-triangulation process, simultaneous resection and intersection are carried out where common rays from two or more overlapping photographs intersect at a common ground point (see e.g., Fig. 12.1).

In 1997, the Kyoto protocol to the United Nation’s framework convention on climate change spelt out measures that were to be taken to reduce the greenhouse gas emission that has contributed to global warming. Global warming is just but one of the many challenges facing our environment today. The rapid increase in desertification on one hand and flooding on the other hand are environmental issues that are increasingly becoming of concern. For instance, the torrential rains that caused havoc and destroyed properties in USA in 1993 is estimated to have totalled to $15 billion, 50 people died and thousands of people were evacuated, some for months [261]. Today, the threat from torrential rains and flooding still remains real as was seen in 1997 El’nino rains that swept roads and bridges in Kenya, the 2000 Mozambique flood disaster, 2002 Germany flood disaster or the Hurricane Isabel in the US coast¹. The melting of polar ice thus raising the sea level is creating fear of submersion of beaches and cities surrounded by the oceans and those already below sea level. In-order to be able to predict and model these occurrences so as to minimize damages such as those indicated by [261], atmospheric studies have to be undertaken with the aim of improving on mechanism for providing reliable, accurate and timely data. These data are useful in Numerical Weather Prediction (NWP) models for weather forecasting and climatic models for monitoring climatic changes. Besides, accurate and reliable information on weather is essential for other applications such as agriculture, flight navigation, etc.

In Chap. 7, we introduced parameter estimation from observational data sample and defined the models applicable to linear and nonlinear cases.

The 7-parameter datum transformation \({\mathbb C}_{7}(3)\) problem involves the determination of seven parameters required to transform coordinates from one system to another. The transformation of coordinates is a computational procedure that maps one set of coordinates in a given system onto another. This is achieved by translating the given system so as to cater for its origin with respect to the final system, and rotating the system about its own axes so as to orient it to the final system. In addition to the translation and rotation, scaling is performed in order to match the corresponding baseline lengths in the two systems. The three translation parameters, three rotation parameters and the scale element comprise the 7 parameters of the datum transformation \( {\mathbb C}_{7}(3)\) problem, where one understands \({\mathbb C}_{7}(3)\) to be the notion of the seven parameter conformal group in \(\mathbb R^{3}\), leaving “space angles” and “distance ratios” equivariant (invariant). A mathematical introduction to conformal field theory is given by [141,357], while a systematic approach of geodetic datum transformation, including geometrical and physical terms, is presented by [188]. For a given network, it suffices to compute the transformation parameters using three or more coordinates in both systems. These parameters are then later used for subsequent conversions.