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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
.TH bandwr 1 "September 1996" "Scilab Group" "Scilab function"
.so ../sci.an
.SH NAME
bandwr - bandwidth reduction for a sparse matrix
.SH CALLING SEQUENCE
.nf
[iperm,mrepi,profile,ierr] = bandwr(sp,[iopt])
[iperm,mrepi,profile,ierr] = bandwr(lp,ls,n,[iopt])
.fi
.SH PARAMETERS
.TP 3
sp
: sparse matrix
.TP 3
lp
: integer row vector
.TP 3
ls
: integer row vector
.TP 2
n
: integer
.TP 5
iopt
: integer
.TP 6
iperm
: integer row vector
.TP 6
mrepi
: integer row vector
.TP 8
profile
: integer row vector
.TP 5
ierr
: integer
.SH DESCRIPTION
\fVbandwr\fR 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).
.LP
In the first calling sequence, \fVsp\fR denotes a
sparse matrix; the optional argument \fViopt\fR 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.
.LP
The second calling sequence corresponds to the description of a graph:
\fVlp\fR 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);
\fVls\fR is a row vector, 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 corresponding sparse matrix).
\fVn\fR is the number of nodes (dimension of \fVsp\fR).
.LP
\fViperm\fR 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);
\fVmrepi\fR is the inverse permutation (mrepi(iperm) is the identity).
\fVprofile\fR is the array giving the profile of the sparse matrix
after the bandwidth reduction if \fViopt\fR is 1. If \fViopt\fR is 0
this array is zero except for the first term giving the bandwidth.
The simple command \fVmax(profile(2:$)-profile(1:($-1)))\fR returns
the bandwidth of the matrix.
\fVierr\fR is an integer indicating an error if its value is not zero.
.SH EXAMPLE
.nf
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');
.fi
|
