The nodes are numbered following the next
order of the sets of the partition
Ki, ecc (Ep; KC,1,; 9 e , KC,/2,17 .... ‚KC1,10g(r)
where log(r) is log, .
First partition.
During this step, a partition of V into
(K4,K5, ,Ky,I) is determined such that
an edge connecting two nodes belonging to
two different Kj , Ky, (k,h-1..r and k #
h) doesn' t exist.
Definition 1.2. Given a graph G-(V,E),
we define "first partition" of V the sets
(Ky, Ky, rKn:1)50 that
1) (Kı,K2, ‚Kn-I) is a partition of V
2) not 3 (n;,n,)eE and k,h-1..r, kzh,
so that: n;eK,, n,eK,
The effects in terms of the structure of
the matrix A, are visible in figure 3.
Lk
Figure 3
The restriction produced by the definition
1.2 is obvious: the request that there
isn't an edge that connects two nodes
belonging to two different sets K; and Ky
produces a diagonal of blocks; in fact,
there aren' t equations between
corresponding variables and so, over and
under each K, diagonal block all matrix
coefficients are zero. Block I, on the
right side, gathers the equations related
to those edges which connect one node of I
and one of K; (the part away all diagonals
blocks), or two nodes of I (the part below
Kr);
Second partition.
During the second step, the matrix block I
is also structured in some way. The idea
is to locate a partition into the set I. A
good way, particularly favourable for the
QR decomposition method, is to transform
this block "into diagonals of blocks
placed side by side. We don' t explain the
reasons of this conjecture because it
would be necessary to known how OR
factorization transforms the structured
matrix A in the triangular form R.
Definition 1.3 Given the first partition
(K4,K5, Enr!) Of V, we define "second
partition" the sets:
Ki; 6 Ka BCL 1474 BC 2 11 ++ RC, Yog(r)
so that:
- V nj£KCp k ke1..log,(r), h«1..20c7D
—- V n,eK
p=1..n
the edge (n;,n;)
belongs to E and
p = int( (p-1)/2* ) #1
105
where the function int() returns the value
truncated to the integer part of the
division. In terms of matrix structure,
the consequence of this definition is
visible in the figure 4. On the right side
of the first diagonal of blocks, obtained
at the previous step, there are log,r new
diagonals in which the number of blocks
halves proceeding to the right side.
400
[|
Ej
Figure 4
El lf
Note that the lower part of the matrix is
a block triangular; actually, this
definition is misleaded. Now, having a
look at figure 11, where the structure of
the matrix relative to the experiment
discussed at the end of this paper, is
reported. The lower part of the matrix is
similar, although not equal, to the upper
one; to discriminate there are the few
blocks (bad blocks) not present in the
right matrix of the figure 11. During QR
factorization these blocks produce very
bad effects increasing the costs (flops
and memory); if possible, the best thing
to do is to eliminate them ensuring a
repetition of the upper structure into the
lower part too (compatibility of blocks
location).
Arrangement.
Bad blocks can be eliminated simply
shifting on the right side, to a greater
level, some nodes. This operation can be
made only when the second partition is
determined; in the same way, the second
partition can be done when the first one
is completed. It' s sufficient to scan all
the nodes belonging to KC,,, and to verify
if they produce a 'bad' block; in this
case, the node must be moved to an
appropriate block of major level. In order
to make this process working correctly,
it' s important for the scan operation to
proceed from the first to the last level;
so, transfering nodes to an upper level
doesn' t damage previous block diagonal
structure. The only consequence is that
the blocks of the last level become larger
and larger. As this blocks are sparse and
have got great dimension, this effect is
unpleasant. If a lot of nodes should be
moved, some blocks can disappear and the
level structure may become more deficient.
At the end, the coefficient matrix, so
structured, assumes the form reported in
the figure 5.
