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