Cycles: Improve denoising speed on GPUs with small tile sizes
[blender.git] / intern / cycles / util / util_math_matrix.h
1 /*
2  * Copyright 2011-2017 Blender Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16
17 #ifndef __UTIL_MATH_MATRIX_H__
18 #define __UTIL_MATH_MATRIX_H__
19
20 CCL_NAMESPACE_BEGIN
21
22 #define MAT(A, size, row, col) A[(row)*(size)+(col)]
23
24 /* Variants that use a constant stride on GPUS. */
25 #ifdef __KERNEL_GPU__
26 #  define MATS(A, n, r, c, s) A[((r)*(n)+(c))*(s)]
27 /* Element access when only the lower-triangular elements are stored. */
28 #  define MATHS(A, r, c, s) A[((r)*((r)+1)/2+(c))*(s)]
29 #  define VECS(V, i, s) V[(i)*(s)]
30 #else
31 #  define MATS(A, n, r, c, s) MAT(A, n, r, c)
32 #  define MATHS(A, r, c, s) A[(r)*((r)+1)/2+(c)]
33 #  define VECS(V, i, s) V[i]
34 #endif
35
36 /* Zeroing helpers. */
37
38 ccl_device_inline void math_vector_zero(float *v, int n)
39 {
40         for(int i = 0; i < n; i++) {
41                 v[i] = 0.0f;
42         }
43 }
44
45 ccl_device_inline void math_matrix_zero(float *A, int n)
46 {
47         for(int row = 0; row < n; row++) {
48                 for(int col = 0; col <= row; col++) {
49                         MAT(A, n, row, col) = 0.0f;
50                 }
51         }
52 }
53
54 /* Elementary vector operations. */
55
56 ccl_device_inline void math_vector_add(float *a, const float *ccl_restrict b, int n)
57 {
58         for(int i = 0; i < n; i++) {
59                 a[i] += b[i];
60         }
61 }
62
63 ccl_device_inline void math_vector_mul(float *a, const float *ccl_restrict b, int n)
64 {
65         for(int i = 0; i < n; i++) {
66                 a[i] *= b[i];
67         }
68 }
69
70 ccl_device_inline void math_vector_mul_strided(ccl_global float *a, const float *ccl_restrict b, int astride, int n)
71 {
72         for(int i = 0; i < n; i++) {
73                 a[i*astride] *= b[i];
74         }
75 }
76
77 ccl_device_inline void math_vector_scale(float *a, float b, int n)
78 {
79         for(int i = 0; i < n; i++) {
80                 a[i] *= b;
81         }
82 }
83
84 ccl_device_inline void math_vector_max(float *a, const float *ccl_restrict b, int n)
85 {
86         for(int i = 0; i < n; i++) {
87                 a[i] = max(a[i], b[i]);
88         }
89 }
90
91 ccl_device_inline void math_vec3_add(float3 *v, int n, float *x, float3 w)
92 {
93         for(int i = 0; i < n; i++) {
94                 v[i] += w*x[i];
95         }
96 }
97
98 ccl_device_inline void math_vec3_add_strided(ccl_global float3 *v, int n, float *x, float3 w, int stride)
99 {
100         for(int i = 0; i < n; i++) {
101                 ccl_global float *elem = (ccl_global float*) (v + i*stride);
102                 atomic_add_and_fetch_float(elem+0, w.x*x[i]);
103                 atomic_add_and_fetch_float(elem+1, w.y*x[i]);
104                 atomic_add_and_fetch_float(elem+2, w.z*x[i]);
105         }
106 }
107
108 /* Elementary matrix operations.
109  * Note: TriMatrix refers to a square matrix that is symmetric, and therefore its upper-triangular part isn't stored. */
110
111 ccl_device_inline void math_trimatrix_add_diagonal(ccl_global float *A, int n, float val, int stride)
112 {
113         for(int row = 0; row < n; row++) {
114                 MATHS(A, row, row, stride) += val;
115         }
116 }
117
118 /* Add Gramian matrix of v to A.
119  * The Gramian matrix of v is vt*v, so element (i,j) is v[i]*v[j]. */
120 ccl_device_inline void math_matrix_add_gramian(float *A,
121                                                   int n,
122                                                   const float *ccl_restrict v,
123                                                   float weight)
124 {
125         for(int row = 0; row < n; row++) {
126                 for(int col = 0; col <= row; col++) {
127                         MAT(A, n, row, col) += v[row]*v[col]*weight;
128                 }
129         }
130 }
131
132 /* Add Gramian matrix of v to A.
133  * The Gramian matrix of v is vt*v, so element (i,j) is v[i]*v[j]. */
134 ccl_device_inline void math_trimatrix_add_gramian_strided(ccl_global float *A,
135                                                           int n,
136                                                           const float *ccl_restrict v,
137                                                           float weight,
138                                                           int stride)
139 {
140         for(int row = 0; row < n; row++) {
141                 for(int col = 0; col <= row; col++) {
142                         atomic_add_and_fetch_float(&MATHS(A, row, col, stride), v[row]*v[col]*weight);
143                 }
144         }
145 }
146
147 /* Transpose matrix A inplace. */
148 ccl_device_inline void math_matrix_transpose(ccl_global float *A, int n, int stride)
149 {
150         for(int i = 0; i < n; i++) {
151                 for(int j = 0; j < i; j++) {
152                         float temp = MATS(A, n, i, j, stride);
153                         MATS(A, n, i, j, stride) = MATS(A, n, j, i, stride);
154                         MATS(A, n, j, i, stride) = temp;
155                 }
156         }
157 }
158
159 /* Solvers for matrix problems */
160
161 /* In-place Cholesky-Banachiewicz decomposition of the square, positive-definite matrix A
162  * into a lower triangular matrix L so that A = L*L^T. A is being overwritten by L.
163  * Also, only the lower triangular part of A is ever accessed. */
164 ccl_device void math_trimatrix_cholesky(ccl_global float *A, int n, int stride)
165 {
166         for(int row = 0; row < n; row++) {
167                 for(int col = 0; col <= row; col++) {
168                         float sum_col = MATHS(A, row, col, stride);
169                         for(int k = 0; k < col; k++) {
170                                 sum_col -= MATHS(A, row, k, stride) * MATHS(A, col, k, stride);
171                         }
172                         if(row == col) {
173                                 sum_col = sqrtf(max(sum_col, 0.0f));
174                         }
175                         else {
176                                 sum_col /= MATHS(A, col, col, stride);
177                         }
178                         MATHS(A, row, col, stride) = sum_col;
179                 }
180         }
181 }
182
183 /* Solve A*S=y for S given A and y, where A is symmetrical positive-semidefinite and both inputs are destroyed in the process.
184  *
185  * We can apply Cholesky decomposition to find a lower triangular L so that L*Lt = A.
186  * With that we get (L*Lt)*S = L*(Lt*S) = L*b = y, defining b as Lt*S.
187  * Since L is lower triangular, finding b is relatively easy since y is known.
188  * Then, the remaining problem is Lt*S = b, which again can be solved easily.
189  *
190  * This is useful for solving the normal equation S=inv(Xt*W*X)*Xt*W*y, since Xt*W*X is
191  * symmetrical positive-semidefinite by construction, so we can just use this function with A=Xt*W*X and y=Xt*W*y. */
192 ccl_device_inline void math_trimatrix_vec3_solve(ccl_global float *A, ccl_global float3 *y, int n, int stride)
193 {
194         /* Since the first entry of the design row is always 1, the upper-left element of XtWX is a good
195          * heuristic for the amount of pixels considered (with weighting), therefore the amount of correction
196          * is scaled based on it. */
197         math_trimatrix_add_diagonal(A, n, 3e-7f*A[0], stride); /* Improve the numerical stability. */
198         math_trimatrix_cholesky(A, n, stride); /* Replace A with L so that L*Lt = A. */
199
200         /* Use forward substitution to solve L*b = y, replacing y by b. */
201         for(int row = 0; row < n; row++) {
202                 float3 sum = VECS(y, row, stride);
203                 for(int col = 0; col < row; col++)
204                         sum -= MATHS(A, row, col, stride) * VECS(y, col, stride);
205                 VECS(y, row, stride) = sum / MATHS(A, row, row, stride);
206         }
207
208         /* Use backward substitution to solve Lt*S = b, replacing b by S. */
209         for(int row = n-1; row >= 0; row--) {
210                 float3 sum = VECS(y, row, stride);
211                 for(int col = row+1; col < n; col++)
212                         sum -= MATHS(A, col, row, stride) * VECS(y, col, stride);
213                 VECS(y, row, stride) = sum / MATHS(A, row, row, stride);
214         }
215 }
216
217 /* Perform the Jacobi Eigenvalue Methon on matrix A.
218  * A is assumed to be a symmetrical matrix, therefore only the lower-triangular part is ever accessed.
219  * The algorithm overwrites the contents of A.
220  *
221  * After returning, A will be overwritten with D, which is (almost) diagonal,
222  * and V will contain the eigenvectors of the original A in its rows (!),
223  * so that A = V^T*D*V. Therefore, the diagonal elements of D are the (sorted) eigenvalues of A.
224  */
225 ccl_device void math_matrix_jacobi_eigendecomposition(float *A, ccl_global float *V, int n, int v_stride)
226 {
227         const float singular_epsilon = 1e-9f;
228
229         for(int row = 0; row < n; row++) {
230                 for(int col = 0; col < n; col++) {
231                         MATS(V, n, row, col, v_stride) = (col == row) ? 1.0f : 0.0f;
232                 }
233         }
234
235         for(int sweep = 0; sweep < 8; sweep++) {
236                 float off_diagonal = 0.0f;
237                 for(int row = 1; row < n; row++) {
238                         for(int col = 0; col < row; col++) {
239                                 off_diagonal += fabsf(MAT(A, n, row, col));
240                         }
241                 }
242                 if(off_diagonal < 1e-7f) {
243                         /* The matrix has nearly reached diagonal form.
244                          * Since the eigenvalues are only used to determine truncation, their exact values aren't required - a relative error of a few ULPs won't matter at all. */
245                         break;
246                 }
247
248                 /* Set the threshold for the small element rotation skip in the first sweep:
249                  * Skip all elements that are less than a tenth of the average off-diagonal element. */
250                 float threshold = 0.2f*off_diagonal / (n*n);
251
252                 for(int row = 1; row < n; row++) {
253                         for(int col = 0; col < row; col++) {
254                                 /* Perform a Jacobi rotation on this element that reduces it to zero. */
255                                 float element = MAT(A, n, row, col);
256                                 float abs_element = fabsf(element);
257
258                                 /* If we're in a later sweep and the element already is very small, just set it to zero and skip the rotation. */
259                                 if(sweep > 3 && abs_element <= singular_epsilon*fabsf(MAT(A, n, row, row)) && abs_element <= singular_epsilon*fabsf(MAT(A, n, col, col))) {
260                                         MAT(A, n, row, col) = 0.0f;
261                                         continue;
262                                 }
263
264                                 if(element == 0.0f) {
265                                         continue;
266                                 }
267
268                                 /* If we're in one of the first sweeps and the element is smaller than the threshold, skip it. */
269                                 if(sweep < 3 && (abs_element < threshold)) {
270                                         continue;
271                                 }
272
273                                 /* Determine rotation: The rotation is characterized by its angle phi - or, in the actual implementation, sin(phi) and cos(phi).
274                                  * To find those, we first compute their ratio - that might be unstable if the angle approaches 90°, so there's a fallback for that case.
275                                  * Then, we compute sin(phi) and cos(phi) themselves. */
276                                 float singular_diff = MAT(A, n, row, row) - MAT(A, n, col, col);
277                                 float ratio;
278                                 if(abs_element > singular_epsilon*fabsf(singular_diff)) {
279                                         float cot_2phi = 0.5f*singular_diff / element;
280                                         ratio = 1.0f / (fabsf(cot_2phi) + sqrtf(1.0f + cot_2phi*cot_2phi));
281                                         if(cot_2phi < 0.0f) ratio = -ratio; /* Copy sign. */
282                                 }
283                                 else {
284                                         ratio = element / singular_diff;
285                                 }
286
287                                 float c = 1.0f / sqrtf(1.0f + ratio*ratio);
288                                 float s = ratio*c;
289                                 /* To improve numerical stability by avoiding cancellation, the update equations are reformulized to use sin(phi) and tan(phi/2) instead. */
290                                 float tan_phi_2 = s / (1.0f + c);
291
292                                 /* Update the singular values in the diagonal. */
293                                 float singular_delta = ratio*element;
294                                 MAT(A, n, row, row) += singular_delta;
295                                 MAT(A, n, col, col) -= singular_delta;
296
297                                 /* Set the element itself to zero. */
298                                 MAT(A, n, row, col) = 0.0f;
299
300                                 /* Perform the actual rotations on the matrices. */
301 #define ROT(M, r1, c1, r2, c2, stride)                                   \
302                                 {                                                        \
303                                         float M1 = MATS(M, n, r1, c1, stride);               \
304                                         float M2 = MATS(M, n, r2, c2, stride);               \
305                                         MATS(M, n, r1, c1, stride) -= s*(M2 + tan_phi_2*M1); \
306                                         MATS(M, n, r2, c2, stride) += s*(M1 - tan_phi_2*M2); \
307                                 }
308
309                                 /* Split into three parts to ensure correct accesses since we only store the lower-triangular part of A. */
310                                 for(int i = 0    ; i < col; i++) ROT(A, col, i, row, i, 1);
311                                 for(int i = col+1; i < row; i++) ROT(A, i, col, row, i, 1);
312                                 for(int i = row+1; i < n  ; i++) ROT(A, i, col, i, row, 1);
313
314                                 for(int i = 0    ; i < n  ; i++) ROT(V, col, i, row, i, v_stride);
315 #undef ROT
316                         }
317                 }
318         }
319
320         /* Sort eigenvalues and the associated eigenvectors. */
321         for(int i = 0; i < n - 1; i++) {
322                 float v = MAT(A, n, i, i);
323                 int k = i;
324                 for(int j = i; j < n; j++) {
325                         if(MAT(A, n, j, j) >= v) {
326                                 v = MAT(A, n, j, j);
327                                 k = j;
328                         }
329                 }
330                 if(k != i) {
331                         /* Swap eigenvalues. */
332                         MAT(A, n, k, k) = MAT(A, n, i, i);
333                         MAT(A, n, i, i) = v;
334                         /* Swap eigenvectors. */
335                         for(int j = 0; j < n; j++) {
336                                 float v = MATS(V, n, i, j, v_stride);
337                                 MATS(V, n, i, j, v_stride) = MATS(V, n, k, j, v_stride);
338                                 MATS(V, n, k, j, v_stride) = v;
339                         }
340                 }
341         }
342 }
343
344 #ifdef __KERNEL_SSE3__
345 ccl_device_inline void math_vector_zero_sse(float4 *A, int n)
346 {
347         for(int i = 0; i < n; i++) {
348                 A[i] = make_float4(0.0f);
349         }
350 }
351
352 ccl_device_inline void math_matrix_zero_sse(float4 *A, int n)
353 {
354         for(int row = 0; row < n; row++) {
355                 for(int col = 0; col <= row; col++) {
356                         MAT(A, n, row, col) = make_float4(0.0f);
357                 }
358         }
359 }
360
361 /* Add Gramian matrix of v to A.
362  * The Gramian matrix of v is v^T*v, so element (i,j) is v[i]*v[j]. */
363 ccl_device_inline void math_matrix_add_gramian_sse(float4 *A, int n, const float4 *ccl_restrict v, float4 weight)
364 {
365         for(int row = 0; row < n; row++) {
366                 for(int col = 0; col <= row; col++) {
367                         MAT(A, n, row, col) = MAT(A, n, row, col) + v[row] * v[col] * weight;
368                 }
369         }
370 }
371
372 ccl_device_inline void math_vector_add_sse(float4 *V, int n, const float4 *ccl_restrict a)
373 {
374         for(int i = 0; i < n; i++) {
375                 V[i] += a[i];
376         }
377 }
378
379 ccl_device_inline void math_vector_mul_sse(float4 *V, int n, const float4 *ccl_restrict a)
380 {
381         for(int i = 0; i < n; i++) {
382                 V[i] *= a[i];
383         }
384 }
385
386 ccl_device_inline void math_vector_max_sse(float4 *a, const float4 *ccl_restrict b, int n)
387 {
388         for(int i = 0; i < n; i++) {
389                 a[i] = max(a[i], b[i]);
390         }
391 }
392
393 ccl_device_inline void math_matrix_hsum(float *A, int n, const float4 *ccl_restrict B)
394 {
395         for(int row = 0; row < n; row++) {
396                 for(int col = 0; col <= row; col++) {
397                         MAT(A, n, row, col) = reduce_add(MAT(B, n, row, col))[0];
398                 }
399         }
400 }
401 #endif
402
403 #undef MAT
404
405 CCL_NAMESPACE_END
406
407 #endif  /* __UTIL_MATH_MATRIX_H__ */