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
|
<HTML><title>Performance Notes</title>
<BODY>
<h1>Matrix Performance Notes</h1>
<p>While the matrix interface is always identical, performance characteristics
are implementation dependent. In general, performance of a matrix operation
is a function of <i>{data structure, density, type and kind of method arguments}</i>.
This library takes great care about performance. When in doubt about the detailed
character of an operation, have a look at the source code. </p>
<p>In practice, sparse matrices are used for one of two reasons: To safe memory
or to speed up computation. Hash based sparse matrices (<a href="../impl/SparseDoubleMatrix2D.html">SparseDoubleMatrix2D</a>)
are neither the smallest possible matrix representation nor the fastest. They
implement a reasonable trade-off between performance and memory: Very good average
performance on get/set operations at quite small memory footprint. They are
also suited for special-purpose algorithms exploiting explicit knowledge about
what regions are zero and non-zero, but not quite as good as other sparse matrix
representations. For example, sparse linear algebraic matrix multiplies, inversions,
etc. better work on sparse row compressed (<a href="../impl/RCDoubleMatrix2D.html">RCDoubleMatrix2D</a>).
However, alternative sparse matrix representations are really only usable for
special purposes, because their get/set performance can be very bad. In contrast,
hash based sparse matrices are more generally applicable data structures. </p>
<p> Here is a list describing which combinations are particularly optimized. (<tt>F</tt>
is used as shortcut for <samp>cern.jet.math.Functions</samp>)</p>
<h3>General Remarks</h3>
Matrix-matrix and matrix-vector multiplication <tt>C = alpha*AxB + beta*C</tt>
:
<blockquote>
<p>For good performance B,C may have any type. For A={SparseDoubleMatrix2D,RCDoubleMatrix2D}
this is only fast if the density of A is small. For A={DenseDoubleMatrix2D}
density does not matter. If A is dense and B is sparse, this is no problem,
because even then the quick sparse mult is used.</p>
</blockquote>
<h3>DenseDoubleMatrix2D</h3>
<p></p>
<p></p>
<i>Dense row major format</i>. Essentially all methods highly optimized. This
is almost always the implementation type to go for. It is also most easily to
understand. The types below are only useful for very specific use cases.
<h3>RCDoubleMatrix2D</h3>
<p></p>
<p></p>
<i>Sparse row-compressed format</i>. Special-purpose implementation. Thus some
operations very efficient, others quite slow. Essentially designed to support
the fastest possible sparse matrix-matrix and matrix-vector multiplications as
well as sparse linear algebra. Efficient methods are:
<table width="100%" border="1" cellspacing="0">
<tr bgcolor="#339933">
<td width="19%">Operation</td>
<td width="35%">Method</td>
<td width="46%">Comment</td>
</tr>
<tr>
<td width="19%">read</td>
<td width="35%">get,getQuick</td>
<td width="46%">always</td>
</tr>
<tr>
<td width="19%">write</td>
<td width="35%">set,setQuick</td>
<td width="46%">
<p>only fast if the matrix is really sparse and in a loop iterating upwards:<br>
<tt>for (int i=0; i<rows; i++) { for (int j=0; j<columns; j++) {
setQuick(i,j,...) ... }}</tt></p>
</td>
</tr>
<tr>
<td width="19%">matrix-matrix and matrix-vector multiplication</td>
<td width="35%">zMult</td>
<td width="46%">see above in Section "General"</td>
</tr>
<tr>
<td width="19%">elementwise scaling</td>
<td width="35%">assign(f) where f is one of {F.mult(a),F.div(a)}</td>
<td width="46%"><tt>x[i,j] = x[i,j] {*,/} a</tt></td>
</tr>
<tr>
<td width="19%">elementwise scaling</td>
<td width="35%">assign(y,f) where f is one of {F.plus,F.minus, F.mult,F.div,
F.plusMult(a),F.minusMult(a)}</td>
<td width="46%"><tt>x[i,j] = x[i,j] {+,-,*,/} y[i,j]<br>
x[i,j] = x[i,j] {+,-} y[i,j] {*,/} a</tt></td>
</tr>
<tr>
<td width="19%">copying</td>
<td width="35%">assign(othermatrix)</td>
<td width="46%">always fast, best if othermatrix is a RCDoubleMatrix2D</td>
</tr>
<tr>
<td width="19%">iteration</td>
<td width="35%">forEachNonzero(function)</td>
<td width="46%">most of the time the preferred way for iteration and modification</td>
</tr>
<tr>
<td width="19%"> </td>
<td width="35%"> </td>
<td width="46%"> </td>
</tr>
</table>
<table width="75%" border="1">
</table>
<h3>SparseDoubleMatrix2D</h3>
<p></p>
<p></p>
<i>Sparse hash format</i>. General-purpose sparse implementation. Designed for
efficient random access to sparse structures. Thus, performance more balanced
than RCDoubleMatrix2D. Never really slow, often faster than RCDoubleMatrix2D,
sometimes slightly slower. Efficient methods are:
<table width="100%" border="1" cellspacing="0">
<tr bgcolor="#339933">
<td width="20%">Operation</td>
<td width="35%">Method</td>
<td width="45%">Comment</td>
</tr>
<tr>
<td width="20%">read</td>
<td width="35%">get,getQuick</td>
<td width="45%">always</td>
</tr>
<tr>
<td width="20%">write</td>
<td width="35%">set,setQuick</td>
<td width="45%">
<p>always</p>
</td>
</tr>
<tr>
<td width="20%">matrix-matrix and matrix-vector multiplication</td>
<td width="35%">zMult</td>
<td width="45%">slightly slower than RCDoubleMatrix when size is large</td>
</tr>
<tr>
<td width="20%">elementwise scaling</td>
<td width="35%">assign(f) where f is one of {F.mult(a),F.div(a)}</td>
<td width="45%"><tt>x[i,j] = x[i,j] {*,/} a</tt></td>
</tr>
<tr>
<td width="20%">elementwise scaling</td>
<td width="35%">assign(y,f) where f is one of {F.plus,F.minus, F.mult,F.div,
F.plusMult(a),F.minusMult(a)}</td>
<td width="45%"><tt>x[i,j] = x[i,j] {+,-,*,/} y[i,j]<br>
x[i,j] = x[i,j] {+,-} y[i,j] {*,/} a</tt></td>
</tr>
<tr>
<td width="20%">copying</td>
<td width="35%">assign(othermatrix)</td>
<td width="45%">best if othermatrix is a SparseDoubleMatrix2D</td>
</tr>
<tr>
<td width="20%">iteration</td>
<td width="35%">forEachNonzero(function)</td>
<td width="45%">often the preferred way for iteration and modification</td>
</tr>
<tr>
<td width="20%"> </td>
<td width="35%"> </td>
<td width="45%"> </td>
</tr>
</table>
</BODY>
</HTML>
|
