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
|
<!DOCTYPE html>
<html>
<!-- Created by GNU Texinfo 7.1.1, https://www.gnu.org/software/texinfo/ -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Creating Sparse Matrices in Oct-Files (GNU Octave (version 10.3.0))</title>
<meta name="description" content="Creating Sparse Matrices in Oct-Files (GNU Octave (version 10.3.0))">
<meta name="keywords" content="Creating Sparse Matrices in Oct-Files (GNU Octave (version 10.3.0))">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<meta name="viewport" content="width=device-width,initial-scale=1">
<link href="index.html" rel="start" title="Top">
<link href="Concept-Index.html" 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" rel="up" title="Sparse Matrices in Oct-Files">
<link href="Using-Sparse-Matrices-in-Oct_002dFiles.html" rel="next" title="Using Sparse Matrices in Oct-Files">
<link href="Array-and-Sparse-Class-Differences.html" rel="prev" title="Array and Sparse Class Differences">
<style type="text/css">
<!--
a.copiable-link {visibility: hidden; text-decoration: none; line-height: 0em}
div.example {margin-left: 3.2em}
span:hover a.copiable-link {visibility: visible}
-->
</style>
<link rel="stylesheet" type="text/css" href="octave.css">
</head>
<body lang="en">
<div class="subsubsection-level-extent" id="Creating-Sparse-Matrices-in-Oct_002dFiles">
<div class="nav-panel">
<p>
Next: <a href="Using-Sparse-Matrices-in-Oct_002dFiles.html" accesskey="n" rel="next">Using Sparse Matrices in Oct-Files</a>, Previous: <a href="Array-and-Sparse-Class-Differences.html" accesskey="p" rel="prev">Array and Sparse Class Differences</a>, Up: <a href="Sparse-Matrices-in-Oct_002dFiles.html" 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" title="Index" rel="index">Index</a>]</p>
</div>
<hr>
<h4 class="subsubsection" id="Creating-Sparse-Matrices-in-Oct_002dFiles-1"><span>A.1.6.2 Creating Sparse Matrices in Oct-Files<a class="copiable-link" href="#Creating-Sparse-Matrices-in-Oct_002dFiles-1"> ¶</a></span></h4>
<p>There are two useful strategies 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">
<div class="group"><pre class="example-preformatted">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></div>
<p>which creates the matrix given in section <a class="ref" href="Storage-of-Sparse-Matrices.html">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
nonzero elements and then later fill those elements in. Sample code:
</p>
<div class="example">
<div class="group"><pre class="example-preformatted">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></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 indices 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">
<div class="group"><pre class="example-preformatted">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></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. It is possible to create a sparse
matrix with excess storage, so having <var class="var">nz</var> greater than 4 in this example
is also valid. The disadvantage is that the matrix occupies more memory than
strictly needed.
</p>
<p>Of course, it is not always possible to know the number of nonzero 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 class="code">maybe_compress</code>
function. In addition to deallocating unused storage, <code class="code">maybe_compress</code>
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 class="code">maybe_compress</code> function to be <code class="code">true</code>. However, the cost of
removing the zeros is high because it implies re-sorting the elements. If
possible, it is better for the user to avoid adding the unnecessary zeros in
the first place. An example of the use of <code class="code">maybe_compress</code> is
</p>
<div class="example">
<div class="group"><pre class="example-preformatted">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></div>
<p>The use of the <code class="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 advanced technique might be
</p>
<div class="example">
<pre class="example-preformatted">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 = 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 may sometimes arise that the amount of storage initially created is
insufficient to completely store the sparse matrix. Therefore, the method
<code class="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-preformatted">octave_value arg;
...
int nz, nr, nc;
nz = 6, nr = 3, nc = 4; // Guess the number of nz elements
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 = 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_compress (); // If don't know a priori the final # of nz.
</pre></div>
<p>Note that both increasing and decreasing the number of nonzero elements in a
sparse matrix is expensive as it involves memory reallocation. Also because
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 avoid
changing capacity.
</p>
</div>
<hr>
<div class="nav-panel">
<p>
Next: <a href="Using-Sparse-Matrices-in-Oct_002dFiles.html">Using Sparse Matrices in Oct-Files</a>, Previous: <a href="Array-and-Sparse-Class-Differences.html">Array and Sparse Class Differences</a>, Up: <a href="Sparse-Matrices-in-Oct_002dFiles.html">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" title="Index" rel="index">Index</a>]</p>
</div>
</body>
</html>
|
