= pem 
FS [] a up Tm 
  
Figure 5 
1.4 Some remarks 
The two partitions and the arrangement of 
the third step can be implemented with 
simple procedures and efficient data 
structures (Iob, 1991), so that the cost 
is: 
C =k |E| 5. <k =. 10 
with the constant k depending on the 
particular procedures that can be added to 
improve the structure. Unitary cost is 
assigned to visit a node. The cost is not 
only  polinomial but linear with low 
coefficient. As regards data, it is 
possible to implement simple data type, 
(data structures and operations), that, in 
terms of required memory for storing graph 
and all sets, needs about 
M =(8n + 2m)*sizeof(integer) 
where the function sizeof(integer) returns 
the number of words necessary to store an 
integer. 
2 COMPUTING SOLUTION 
2.1 The OR decomposition 
Once the matrix of the linear or 
linearized system of equations is 
structured as in figure 5, the next step 
is the computation of the solution. As 
mentioned before, the stable OR 
decomposition was chosen, adapting it to 
the structure of the matrix obtained 
previously, instead of the well studied 
and used normal equations method, which is 
less robust against gross errors. The main 
purpose is to show that the euristic of 
the previous paragraph is good enough, 
because it permits to implement efficient 
QR decomposition with low costs and few 
memories. The matrix A is transformed in 
the triangular matrix R by the 'l' meta- 
steps, where 'l' is the number of level, 
of the following procedure: 
procedure OR 
for k=1 to 1 
Ax+1 7 Ok Ak 
Ak+1 7 Pk+1 Ak+1 
end 
endprocedure 
where: Qk7diag(I,,Q4(59,...,05,00,J,), 
b=r/2(k-1), 1, and J, are identity 
matrices, Q;(k), i=1..b, are orthogonal and 
they decompose the corresponding first 
106 
diagonal blocks A,(*) into the products 
R;(E)mQ (),A; (K) (i=1..r/2(4-1)), with R;(%) 
triangular matrices. The following figure 
synthetizes how the first meta-step of the 
OR procedure  modifies the structured 
matrix A=A, of the linear system. 
{1) £1) 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
Ly 0 | 
| | | 
Teen il 
P x 2 X r ul m 
I 
ü ui 
Vil 
a | 
1 
tl 
0 
elements of final elements updated 
SEN [7] elements not updated 
Figure 6 
A? A 
1 
| 
e 
A 
igure 7 
The first meta-step uses 
Q1=diag(0,(1),...,0,(1)J,) to transform the 
first 'r' blocks 2.0, a0 of the 
first upper diagonal into the triangular 
form R,(D,..,R,(1; the blocks on the 
right side of A,(*) are updated and the 
fill-in process take place within them; 
but, as of Q4 structure, it' s confined 
into the blocks . themself. It! s not 
important to know which kind of the 
orthogonal matrices to prefer: the 
projection matrices of Givens or the 
reflection matrices of Householder; the 
choice can be done analyzing blocks and 
studying the fill-in process. J; is the 
identity matrix dimensioned in such a way 
that the lower part of the matrix, below 
the dot line, isn' t modified. Figure 7 
describes the effects of the permutation 
matrix P; P; divides blocks, just 
factorized or updated, in two parts; it 
gathers all the upper pieces and shifts 
‘them upon the others creating the first 
part of the final matrix R. The lower 
parts of the blocks are joined together 
‚with the blocks of the next part of the 
imatrix (under the dot line) and a new 
piece of the matrix A, is ready to be 
submited to the same process. The 
following two figures summarize the second 
step. 
There 
last 
each 
rows 
lines 
trans 
It ic 
Q4 (X) 
inde 
04 (k 
This 
paral 
It! 
trans 
is 
perm 
are c 
To ce 
benef 
decon 
the 
evalu 
matri 
produ 
prod 
althc 
into 
block 
that 
Kj al 
the 
matri 
where 
In « 
gener 
but, 
mode] 
nt: