NUMERICAL SOLUTION OF A BLOCK ADJUSTMENT BY STABLE QR FACTORIZATION 
Fabio Crosilla, Ivano Iob 
Istituto di Urbanistica e Pianificazione 
Università di Udine 
Via Larga 42, 33100 Udine, Italia 
ABSTRACT 
The solution of a great, sparse, 
equations needs euristics such as 
over-determined linear or linearized 
minimum degree’ 
system of 
and 'dissection' to control fill-in 
so to reduce costs and resources. Euristics applied up to now are general and have been 
studied to be coupled with the method of solution of a normal system of equations. The 
purpose of this paper is double: to present a new euristic for a sub-class of problems 
including adjustment procedures and solve the matrix block structure so obtained by a 
modified version of the classic 
completely confined into blocks that, 
parallel implementations. 
OR factorization. 
In: this way, fill-in results 
: according to their location within the matrix, 
allow to obtain a method of solution that is stable, 
less expensive and efficient for 
KEY WORDS: fill-in, euristic, QR factorization. 
Introduction 
Sparse systems of equations are often 
solved with indirect methods which don't 
cause fill-in (i.e. elements previously 
equal to zero become not null). The 
sequence of points computed during the 
interactive process can diverge for a 
general initial point which is frequently 
difficult or impossible to find in order 
to ensure the convergence to the solution. 
On the contrary, direct methods permit to 
compute the solution in one step ‘but they 
produce  fill-in which has unpleasant 
effects on the efficiency of the 
algorithms. Since the problem of minimum 
fill-in is NP-complete, several euristics 
have been studied and proposed up to now 
to reduce it. These euristics alter the 
position of not null coefficients in a way 
suitable with the particular method chosen 
to compute the solution. In practice, they 
are algorithms for the rows and columns 
permutation of the linear or linearized 
system of equations; but, since 
permutations done with matrix products can 
cost  enought in terms of operations 
(0(n3)), they are implemented by an 
opportune graph connected with the matrix 
structure. Given the linear system Ax-b, 
the graph G-(V,E) is defined as follows: 
- Xe(nj.....Dng] each variable =x; is 
represented within the graph by the node 
ni; 
- E={(n;,n;)| 81,4750; a,,3€A), every not 
null coefficient produces one edge. 
The biunivocal correspondence between the 
node n, and the variable x; permits to 
number nodes from 1 to n and to transfer 
the order to the variables so that these 
one are arranged without an explicit 
matrix product. * 
In this paper the authors propose a new 
euristic with the double aim of improving 
the efficiency compared to classical 
procedures and of resuming the OR 
factorization method to solve over- 
determined linear systems of equations. 
The first purpose is pursued considering a 
sub-class of problems for which a new type 
of graph will be defined in order to take 
advantage of the restrictions imposed. 
Relating to the second purpose, it is well 
101 
known that an  over-determined linear 
system of equations doesn' t admit exact 
solutions and, alternately, it is 
generally computed the vector x which 
minimizes | | Ax-b| |2 (least squares 
problem). The literature suggests 
different direct methods of solution such 
as: 
- normal equations : A*tAx - Atb; 
- OR decomposition min||Ax-b||; = 
min| |Rx-Qtb| |, with A=QR; 
- Single Value Decomposition ( S.V.D.). 
Neglecting the last one, used for very bad 
conditioned problems, the QR factorization 
works well in our case. In practice, it is 
rarely utilized because it requires more 
floating point operations (flops) than 
normal equations method. That's true for 
general matrices, but a good management of 
the sparsity can significantly reduce the 
number of flops giving, at the same time, 
all advantages derived from the stable 
process which transforms matrix A in the 
triangular matrix R. 
1 MATRIX STRUCTURING 
1.1 The sub-class problems’ 
Let' s consider the sub-class of problems 
whose sets of the variables X and the 
equations verify the following hypothesis: 
Hypothesis 1.1. Let X be the set of 
variables, X;,X,,...X, subsets of X and 
suppose that: 
1) the set of variables X is partitionable 
into Xi, X», + Xp 
2) all equations are: 
i,j51... m. 
£(X;,X,)-0 ; 9for 
The first request is simply to understand; 
it imposes that the set of variables X can 
be divided in 'n' sets X;, Xj, +X, 80 
that : 
- Ua X7 
— X; zt e 
- X, intersects X, # J. 
The second request needs more 
specifications because £(X;,X;)=0 
represents a generic equation where the 
not null coefficients belong only to the 
sets X; and X,. In other words, the