IEEE Robotics & Automation Magazine - September 2014 - 74

matrices. The use of variable reordering significantly improves the computation and
1
1
1
1
1
2
memory requirements for matrix decom1
position methods [65], [66].
1
2
2
1
The nested dissection variable reor1
2
1
1
1
1
dering
scheme was initially proposed for
1
solving
a system of equations for n # n
1
3
3
1
grid problems arising from finite-element
1
2
1
1
1
1
discretization of a mesh [64]. It partitions
1
1
the graph with "+" shapes, as shown in
2
2
1
Figure
13. Each resulting block is then
1
2
recursively partitioned with a "+" shape.
1
1
1
1
1
1
The number on each partition corre(a)
(b)
sponds to the entry in the coefficient
matrix. Helmert's proposal to divide a triFigure 13. The nested dissection and the corresponding matrix arrangement. The four
angulation net recursively along latitudes
higher blocks with nodes numbered 1 and 2 are independent given the separator 3. All
and longitudes was used by Avila and
subblocks numbered 1 are independent given the subblock numbered 2. (a) A planar
mesh partitioned according to nested dissection and (b) the corresponding matrix
Tomlin [67] for solving large least squares
picture for this net.
using the ILLIAC IV parallel processor
for optimizing geodetic networks. Later,
Golub and Plemmons [68] used the Helmert blocking variable ordering strategy for solving a large system of equations
1
2
using orthogonal decomposition techniques, such as QR
decomposition for the system of equations arising from the
geodetic network.
3
4
Given that Helmert's proposal and the nested dissection
algorithm are so similar, researchers performed a study to
(a)
understand the best way to create the separators and to join
the blocks given a four-way partitioning for NAD 83 [5]. Figure 14 shows four ways of joining a block partitioned into
four subblocks. The partitioning can be done using either
4
Helmert's strategy or nested dissection. The key design
choice is whether to use a deep tree or broad tree strategy, as
3
shown in Figure 15. The deep tree strategy creates smaller
and denser final blocks, while broad trees result in larger and
1
2
1
2
3
4
sparser blocks. This can be observed from Figure 15(a) and
(b) for a simple example. The large sparse matrix in the
(b)
(c)
broad tree strategy implies further variable reordering to
minimize the matrix fill-in. In the deep tree strategy, parallelism can be better exploited, but it requires more matrix allocations. In the simple example shown in Figure 15, seven
4
matrices are allocated for the deep tree compared with five
allocations for the broad tree strategy. Hence, the deep tree
strategy was preferred for NAD 83 to enable more parallel1
2
3
1
2
3
4
ism and because the created, dense subblocks do not require
(d)
(e)
further reordering.
1

Figure 14. Possible different ways for joining four Helmert blocks
according to [5]. (a) A rectangular area partitioned into four blocks, which
can be joined in four ways (b) deep tree, (c), (d), and (e) broad tree.

in Figure 4(d) and (e). The proposed method is simple but
effective, since the triangulation network is built roughly as a
planar graph and the density of the net was approximately similar across different locations. Helmert's approach to partition the
triangle nets also shares similarities to the nested dissection variable reordering strategies [64] used to efficiently factorize sparse
74

IEEE ROBOTICS & AUTOMATION MAGAZINE

september 2014

Removing Outliers for Geodetic Mapping
The task of traditional geodetic mapping involves hundreds
of surveyors working in parallel to obtain measurements.
This also results in many faulty constraints [5]. The typical
sources of faulty constraints are human errors, errors in
instruments, and sometimes errors when transferring
entries from physical journals into the database management systems. For NAD 83, erroneous constraints are
detected and removed through a block validation process.

Table of Contents for the Digital Edition of IEEE Robotics & Automation Magazine - September 2014