Developer Reference for Intel® oneAPI Math Kernel Library for Fortran
Convolution and Correlation Data Allocation
This section explains the relation between:
mathematical finite functions \(u\), \(v\), \(w\) introduced in Mathematical Notation and Definitions ;
multi-dimensional input and output data vectors representing the functions \(u\), \(v\), \(w\) ;
arrays x, y, x used to store the input and output data vectors in computer memory
The convolution and correlation routine parameters that determine the allocation of input and output data are the following:
Data arrays x, y, z
Shape arrays xshape, yshape, zshape
Strides within arrays xstride, ystride, zstride
Parameters start, decimation
Finite Functions and Data Vectors
The finite functions \(u(p)\), \(v(q)\), and \(w(r)\) introduced above are represented as multi-dimensional vectors of input and output data:
\(input_u(i_{1}, \dots,i_{\text{dims}})\) for \(u(p_{1}, \dots,p_{N})\)
\(input_v(j_{1}, \dots,j_{\text{dims}})\) for \(v(q_{1}, \dots,q_{N})\)
\(output(k_{1}, \dots,k_{\text{dims}})\) for \(w(r_{1}, \dots,r_{N}).\)
Parameter dims represents the number of dimensions and is equal to \(N\).
The parameters xshape, yshape, and zshape define the shapes of input/output vectors:
\(input_u(i_{1}, \dots,i_{\text{dims}})\) is defined if \(1 \le i_{n} \le \text{xshape}[n]\) for every \(n = 1, \dots, \text{dims}\)
\(input_v(j_{1}, \dots, j_{\text{dims}})\) is defined if \(1 \le j_{n} \le \text{yshape}[n]\) for every \(n = 1, \dots, \text{dims}\)
\(output(k_{1}, \dots, k_{\text{dims}})\) is defined if \(1 \le k_{n} \le \text{zhape}[n]\) for every \(n = 1, \dots, \text{dims}\).
Relation between the input vectors and the functions \(u\) and \(v\) is defined by the following formulas:
\(input_u(i_{1}, \dots, i_{\text{dims}}) = u(p_{1}, \dots, p_{N})\), where \(p_{n} = P_{n}^{min} + (i_{n} - 1)\) for every \(n\)
\(input_v(j_{1}, \dots, j_{\text{dims}}) = v(q_{1}, \dots, q_{N})\), where \(q_{n} = Q_{n}^{min} + (j_{n} - 1)\) for every \(n\).
The relation between the output vector and the function \(w(r)\) is similar (but only in the case when parameters start and decimation are not defined):
\(output(k_{1}, \dots, k_{\text{dims}}) = w(r_{1}, \dots, r_{N})\), where \(r_{n} = R_{n}^{min} + (k_{n} - 1)\) for every \(n\).
If the parameter start is defined, it must belong to the interval \(R_{n}^{min} \le \text{start}[n] \le R_{n}^{max}\). If defined, the start parameter replaces \(R^{min}\) in the formula:
\(output(k_{1}, \dots, k_{\text{dims}}) = w(r_{1}, \dots, r_{N})\), where \(r_{n} = \text{start}[n] + (k_{n}-1)\)
If the parameter decimation is defined, it changes the relation according to the following formula:
\(output(k_{1}, \dots, k_{\text{dims}}) = w(r_{1}, \dots, r_{N})\), where \(r_{n} = R_{n}^{min} + (k_{n} - 1) \times \text{decimation}[n]\)
If both parameters start and decimation are defined, the formula is as follows:
\(output(k_{1}, \dots, k_{\text{dims}}) = w(r_{1}, \dots, r_{N})\), where \(r_{n} = \text{start}[n] + (k_{n}-1) \times \text{decimation}[n]\)
The convolution and correlation software checks the values of zshape, start, and decimation during task commitment. If \(r_{n}\) exceeds \(R_{n}^{max}\) for some \(k_{n}\) for any \(n \in \{1, \dots, \text{dims}\}\), an error is raised.
Allocation of Data Vectors
Both parameter arrays x and y contain input data vectors in memory, while array z is intended for storing output data vector. To access the memory, the convolution and correlation software uses only pointers to these arrays and ignores the array shapes.
For parameters x, y, and z, you can provide one-dimensional arrays with the requirement that actual length of these arrays be sufficient to store the data vectors.
The allocation of the input and output data inside the arrays x, y, and z is described below assuming that the arrays are one-dimensional. Given multi-dimensional indices \(i, j, k \in \mathbb{Z}^{N}\), one-dimensional indices \(e, f, g \in \mathbb{Z}\) are defined such that:
\(input_u(i_{1}, \dots, i_{\text{dims}})\) is allocated at x[e]
\(input_v(j_{1}, \dots, j_{\text{dims}})\) is allocated at y[f]
\(output(k_{1}, \dots, k_{\text{dims}})\) is allocated at z[g].
The indices \(e\), \(f\), and \(g\) are defined as follows:
\[e = 1 + \sum_{n=1}^{\text{dims}} \text{xstride}[n] \times dx(n) f = 1 + \sum_{n=1}^{\text{dims}} \text{ystride}[n] \times dy(n) g = 1 + \sum_{n=1}^{\text{dims}} \text{zstride}[n] \times dz(n)\]
The distances \(dx(n)\), \(dy(n)\), and \(dz(n)\) depend on the signum of the stride:
\(dx(n) = i_{n} - 1\) if \(\text{xstride}[n] > 0\), or \(dx(n) = i_{n} - \text{xshape}[n]\) if \(\text{xstride}[n] < 0\)
\(dy(n) = j_{n} - 1\) if \(\text{ystride}[n] > 0\), or \(dy(n) = j_{n} - \text{yshape}[n]\) if \(\text{ystride}[n] < 0\)
\(dz(n) = k_{n} - 1\) if \(\text{zstride}[n] > 0\), or \(dz(n) = k_{n} - \text{zhape}[n]\) if \(\text{zstride}[n] < 0\)
The definitions of indices \(e\), \(f\), and \(g\) assume that indexes for arrays x, y, and z are started from unity:
x[e] is defined for \(e = 1, \dots, length(x)\)
y[f] is defined for \(f = 1, \dots, length(y)\)
z[g] is defined for \(g = 1, \dots, length(z)\)
Below is a detailed explanation about how elements of the multi-dimensional output vector are stored in the array z for one-dimensional and two-dimensional cases.
One-dimensional case. If dims = 1, then zshape is the number of the output values to be stored in the array z. The actual length of array z may be greater than zshape elements.
If zstride > 1, output values are stored with the stride: \(output(1)\) is stored to z[1], \(output(2)\) is stored to z[1 + zstride], and so on. Hence, the actual length of z must be at least 1 + zstride * (zshape - 1) elements or more.
If zstride < 0, it still defines the stride between elements of array z. However, the order of the used elements is the opposite. For the \(k-\)th output value, \(output(k)\) is stored in z[1 + abs(zstride) * (zshape - k)), where abs(zstride) is the absolute value of zstride. The actual length of the array z must be at least 1 + abs(zstride) * (zshape - 1) elements.
Two-dimensional case. If dims = 2, the output data is a two-dimensional matrix. The value zstride[1] defines the stride inside matrix columns, that is, the stride between the \(output(k_{1}, k_{2})\) and \(output(k_{1} + 1, k_{2})\) for every pair of indices \(k_{1}, k_{2}\). On the other hand, zstride[2] defines the stride between columns, that is, the stride between \(output(k_{1}, k_{2})\) and \(output(k_{1}, k_{2} + 1)\).
If zstride[2] is greater than zshape[1], this causes sparse allocation of columns. If the value of zstride[2] is smaller than zshape(1), this may result in the transposition of the output matrix. For example, if zshape = [2, 3], you can define zstride = [3, 1] to allocate output values like transposed matrix of the shape \(3 \times 2\).
Whether zstride assumes this kind of transformations or not, you need to ensure that different elements output \((k_{1}, \dots, k_{\text{dims}}\)) will be stored in different locations z[g].