1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
|
bandwr(1) Scilab function bandwr(1)
NAME
bandwr - bandwidth reduction for a sparse matrix
CALLING SEQUENCE
[iperm,mrepi,profile,ierr] = bandwr(sp,[iopt])
[iperm,mrepi,profile,ierr] = bandwr(lp,ls,n,[iopt])
PARAMETERS
sp : sparse matrix
lp : integer row vector
ls : integer row vector
n : integer
iopt : integer
iperm : integer row vector
mrepi : integer row vector
profile : integer row vector
ierr : integer
DESCRIPTION
bandwr solves the problem of bandwidth reduction for a sparse matrix: the
matrix is supposed to be upper triangular with a full diagonal (it is easy
to complete a non symmetric matrix, and then discards the added terms).
In the first calling sequence, sp denotes a sparse matrix; the optional
argument iopt is 0 or 1: 1 if reducing the profile of the matrix is more
important than reducing the bandwidth and 0 if bandwidth reduction is most
important.
The second calling sequence corresponds to the description of a graph: lp
is a row vector, pointer array of the adjacency lists description of a
graph (its size is the number of nodes of the graph + 1); ls is a row vec-
tor, node array of the adjacency lists description (its size is the number
of edges of the graph i.e. the number of non-zero terms of the correspond-
ing sparse matrix). n is the number of nodes (dimension of sp).
iperm is the permutation vector for reordering the rows and columns which
reduces the bandwidth and/or profile (new numbering of the nodes of the
graph); mrepi is the inverse permutation (mrepi(iperm) is the identity).
profile is the array giving the profile of the sparse matrix after the
bandwidth reduction if iopt is 1. If iopt is 0 this array is zero except
for the first term giving the bandwidth. The simple command
max(profile(2:$)-profile(1:($-1))) returns the bandwidth of the matrix.
ierr is an integer indicating an error if its value is not zero.
EXAMPLE
ta=[2 1 3 2 2 4 4 5 6 7 8 8 9 10 10 10 10 11 12 13 13 14 15 16 16 17 17];
he=[1 10 2 5 7 3 2 4 5 8 6 9 7 7 11 13 15 12 13 9 14 11 16 1 17 14 15];
g=make_graph('foo',0,17,ta,he);
g('node_x')=[283 163 63 57 164 164 273 271 339 384 504 513 439 623 631 757 642];
g('node_y')=[59 133 223 318 227 319 221 324 432 141 209 319 428 443 187 151 301];
// THE GRAPH
show_graph(g);
a=graph_2_mat(g,'node-node');
ww=tril(a)'+eye;
ww1=full(ww);
xset('window',0)
hist3d((ww1+tril(ww1',-1)+tril(ww1,-1)'),52,85);
// BANDWIDTH REDUCTION FOR THE MATRIX
[iperm,mrepi,profile,ierr]=bandwr(ww);
max(profile(2:$)-profile(1:($-1)))
// GRAPH WITH THE NEW NUMBERING
g2=g;g2('node_name')=string(iperm);
show_graph(g2,'new')
// NEW MATRIX
n=g('node_number');
yy=ww1(mrepi,mrepi);
xset('window',1)
hist3d((yy+tril(yy',-1)+tril(yy,-1)'),52,85);
// STARTING WITH THE SAME MATRIX
[ij,v,mn]=spget(ww);
g1=make_graph('foo',0,n,ij(:,1)',ij(:,2)');
g1('node_x')=g('node_x');g1('node_y')=g('node_y');
// GRAPH
//show_graph(g1,'rep');
[lp,la,ls] = adj_lists(1,n,g1('tail'),g1('head'));
[iperm,mrepi,profile,ierr]=bandwr(lp,ls,n,0);
g2=g;g2('node_name')=string(iperm);
show_graph(g2,'new');
|
