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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- Created by GNU Texinfo 5.2, http://www.gnu.org/software/texinfo/ -->
<head>
<title>GNU Octave: Creating Sparse Matrices in Oct-Files</title>
<meta name="description" content="GNU Octave: Creating Sparse Matrices in Oct-Files">
<meta name="keywords" content="GNU Octave: Creating Sparse Matrices in Oct-Files">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<link href="index.html#Top" rel="start" title="Top">
<link href="Concept-Index.html#Concept-Index" rel="index" title="Concept Index">
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
<link href="Sparse-Matrices-in-Oct_002dFiles.html#Sparse-Matrices-in-Oct_002dFiles" rel="up" title="Sparse Matrices in Oct-Files">
<link href="Using-Sparse-Matrices-in-Oct_002dFiles.html#Using-Sparse-Matrices-in-Oct_002dFiles" rel="next" title="Using Sparse Matrices in Oct-Files">
<link href="Array-and-Sparse-Class-Differences.html#Array-and-Sparse-Class-Differences" rel="prev" title="Array and Sparse Class Differences">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.indentedblock {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smallindentedblock {margin-left: 3.2em; font-size: smaller}
div.smalllisp {margin-left: 3.2em}
kbd {font-style:oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nocodebreak {white-space:nowrap}
span.nolinebreak {white-space:nowrap}
span.roman {font-family:serif; font-weight:normal}
span.sansserif {font-family:sans-serif; font-weight:normal}
ul.no-bullet {list-style: none}
-->
</style>
</head>
<body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
<a name="Creating-Sparse-Matrices-in-Oct_002dFiles"></a>
<div class="header">
<p>
Next: <a href="Using-Sparse-Matrices-in-Oct_002dFiles.html#Using-Sparse-Matrices-in-Oct_002dFiles" accesskey="n" rel="next">Using Sparse Matrices in Oct-Files</a>, Previous: <a href="Array-and-Sparse-Class-Differences.html#Array-and-Sparse-Class-Differences" accesskey="p" rel="prev">Array and Sparse Class Differences</a>, Up: <a href="Sparse-Matrices-in-Oct_002dFiles.html#Sparse-Matrices-in-Oct_002dFiles" accesskey="u" rel="up">Sparse Matrices in Oct-Files</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<a name="Creating-Sparse-Matrices-in-Oct_002dFiles-1"></a>
<h4 class="subsubsection">A.1.6.2 Creating Sparse Matrices in Oct-Files</h4>
<p>There are several useful alternatives for creating a sparse matrix.
The first is to create three vectors representing the row index, column index,
and data values, and from these create the matrix.
The second alternative is to create a sparse matrix with the appropriate
amount of space and then fill in the values. Both techniques have their
advantages and disadvantages.
</p>
<p>Below is an example of creating a small sparse matrix using the first
technique
</p>
<div class="example">
<pre class="example">int nz, nr, nc;
nz = 4, nr = 3, nc = 4;
ColumnVector ridx (nz);
ColumnVector cidx (nz);
ColumnVector data (nz);
ridx(0) = 1; cidx(0) = 1; data(0) = 1;
ridx(1) = 2; cidx(1) = 2; data(1) = 2;
ridx(2) = 2; cidx(2) = 4; data(2) = 3;
ridx(3) = 3; cidx(3) = 4; data(3) = 4;
SparseMatrix sm (data, ridx, cidx, nr, nc);
</pre></div>
<p>which creates the matrix given in section
<a href="Storage-of-Sparse-Matrices.html#Storage-of-Sparse-Matrices">Storage of Sparse Matrices</a>. Note that the compressed matrix
format is not used at the time of the creation of the matrix itself,
but is used internally.
</p>
<p>As discussed in the chapter on Sparse Matrices, the values of the sparse
matrix are stored in increasing column-major ordering. Although the data
passed by the user need not respect this requirement, pre-sorting the
data will significantly speed up creation of the sparse matrix.
</p>
<p>The disadvantage of this technique for creating a sparse matrix is
that there is a brief time when two copies of the data exist. For
extremely memory constrained problems this may not be the best
technique for creating a sparse matrix.
</p>
<p>The alternative is to first create a sparse matrix with the desired
number of non-zero elements and then later fill those elements in.
Sample code:
</p>
<div class="example">
<pre class="example">int nz, nr, nc;
nz = 4, nr = 3, nc = 4;
SparseMatrix sm (nr, nc, nz);
sm(0,0) = 1; sm(0,1) = 2; sm(1,3) = 3; sm(2,3) = 4;
</pre></div>
<p>This creates the same matrix as previously. Again, although not
strictly necessary, it is significantly faster if the sparse matrix is
created and the elements are added in column-major ordering. The reason
for this is that when elements are inserted at the end of the current list
of known elements then no element in the matrix needs to be moved to allow
the new element to be inserted; Only the column indexes need to be updated.
</p>
<p>There are a few further points to note about this method of creating
a sparse matrix. First, it is possible to create a sparse matrix
with fewer elements than are actually inserted in the matrix. Therefore,
</p>
<div class="example">
<pre class="example">int nr, nc;
nr = 3, nc = 4;
SparseMatrix sm (nr, nc, 0);
sm(0,0) = 1; sm(0,1) = 2; sm(1,3) = 3; sm(2,3) = 4;
</pre></div>
<p>is perfectly valid. However, it is a very bad idea because as each new
element is added to the sparse matrix the matrix needs to request more
space and reallocate memory. This is an expensive operation, that will
significantly slow this means of creating a sparse matrix. Furthermore,
it is possible to create a sparse matrix with too much storage, so having
<var>nz</var> greater than 4 is also valid. The disadvantage is that the matrix
occupies more memory than strictly needed.
</p>
<p>It is not always possible to know the number of non-zero elements prior
to filling a matrix. For this reason the additional unused storage of
a sparse matrix can be removed after its creation with the
<code>maybe_compress</code> function. In addition, <code>maybe_compress</code> can
deallocate the unused storage, but it can also remove zero elements
from the matrix. The removal of zero elements from the matrix is
controlled by setting the argument of the <code>maybe_compress</code> function
to be <code>true</code>. However, the cost of removing the zeros is high because it
implies re-sorting the elements. If possible, it is better
if the user does not add the unnecessary zeros in the first place.
An example of the use of <code>maybe_compress</code> is
</p>
<div class="example">
<pre class="example">int nz, nr, nc;
nz = 6, nr = 3, nc = 4;
SparseMatrix sm1 (nr, nc, nz);
sm1(0,0) = 1; sm1(0,1) = 2; sm1(1,3) = 3; sm1(2,3) = 4;
sm1.maybe_compress (); // No zero elements were added
SparseMatrix sm2 (nr, nc, nz);
sm2(0,0) = 1; sm2(0,1) = 2; sm(0,2) = 0; sm(1,2) = 0;
sm1(1,3) = 3; sm1(2,3) = 4;
sm2.maybe_compress (true); // Zero elements were added
</pre></div>
<p>The use of the <code>maybe_compress</code> function should be avoided if
possible as it will slow the creation of the matrix.
</p>
<p>A third means of creating a sparse matrix is to work directly with
the data in compressed row format. An example of this technique might
be
</p>
<div class="example">
<pre class="example">octave_value arg;
…
int nz, nr, nc;
nz = 6, nr = 3, nc = 4; // Assume we know the max # nz
SparseMatrix sm (nr, nc, nz);
Matrix m = arg.matrix_value ();
int ii = 0;
sm.cidx (0) = 0;
for (int j = 1; j < nc; j++)
{
for (int i = 0; i < nr; i++)
{
double tmp = foo (m(i,j));
if (tmp != 0.)
{
sm.data(ii) = tmp;
sm.ridx(ii) = i;
ii++;
}
}
sm.cidx(j+1) = ii;
}
sm.maybe_compress (); // If don't know a priori the final # of nz.
</pre></div>
<p>which is probably the most efficient means of creating a sparse matrix.
</p>
<p>Finally, it might sometimes arise that the amount of storage initially
created is insufficient to completely store the sparse matrix. Therefore,
the method <code>change_capacity</code> exists to reallocate the sparse memory.
The above example would then be modified as
</p>
<div class="example">
<pre class="example">octave_value arg;
…
int nz, nr, nc;
nz = 6, nr = 3, nc = 4; // Assume we know the max # nz
SparseMatrix sm (nr, nc, nz);
Matrix m = arg.matrix_value ();
int ii = 0;
sm.cidx (0) = 0;
for (int j = 1; j < nc; j++)
{
for (int i = 0; i < nr; i++)
{
double tmp = foo (m(i,j));
if (tmp != 0.)
{
if (ii == nz)
{
nz += 2; // Add 2 more elements
sm.change_capacity (nz);
}
sm.data(ii) = tmp;
sm.ridx(ii) = i;
ii++;
}
}
sm.cidx(j+1) = ii;
}
sm.maybe_mutate (); // If don't know a priori the final # of nz.
</pre></div>
<p>Note that both increasing and decreasing the number of non-zero elements in
a sparse matrix is expensive as it involves memory reallocation. Also as
parts of the matrix, though not its entirety, exist as old and new copies
at the same time, additional memory is needed. Therefore, if possible this
should be avoided.
</p>
<hr>
<div class="header">
<p>
Next: <a href="Using-Sparse-Matrices-in-Oct_002dFiles.html#Using-Sparse-Matrices-in-Oct_002dFiles" accesskey="n" rel="next">Using Sparse Matrices in Oct-Files</a>, Previous: <a href="Array-and-Sparse-Class-Differences.html#Array-and-Sparse-Class-Differences" accesskey="p" rel="prev">Array and Sparse Class Differences</a>, Up: <a href="Sparse-Matrices-in-Oct_002dFiles.html#Sparse-Matrices-in-Oct_002dFiles" accesskey="u" rel="up">Sparse Matrices in Oct-Files</a> [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>][<a href="Concept-Index.html#Concept-Index" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
