# Kernel Density Derivative Estimation of Euler Solutions
## 2 Materials and Methods
### Multivariate KDE of the Euler Solution Datasets
#### 2.2.1 Computational Algorithm for Multivariate KDE
For a given estimation grid \(\mathbf{\chi}\) with a size of \(\mathbf{M}=\mathbf{M}_{1}\mathbf{M}_{2}\), the grid count \(\epsilon_{1,1,2}\) at \(\mathbf{\chi}_{1,1,2}\) due to \(\mathbf{X}\) is given by  
\[\epsilon_{1,1,2}=\sum_{i=1}^{n}\overline{c}_{i,1,2}(X_{i}) \tag{10}\]  
where, \(l_{k}=1,\cdots,M_{k}\), \(1\leq k\leq d\), and the function \(\overline{c}_{i,1,2}(X_{i})\) is a natural coordinate value due \(X_{i}\) on \(\mathbf{\chi}_{1,1,2}\). Following [PERSON] (2007) and [PERSON] (2006), the fast linear binning approximation of Equation (6) at a grid point \(\mathbf{\chi}_{j_{1},j_{2}}\) is the discrete convolution of grid counts and the kernel evaluations:  
\[\
abla\overline{F}_{\text{bin}}\big{(}\mathbf{\chi}_{j_{1},j_{2}}\big{)}=\sum_{l_ {1}=1}^{M_{1}}\sum_{l_{2}=1}^{M_{2}}\mathbf{c}_{l_{1},l_{2}}\
abla K_{\mathbf{H}}\big{(} \mathbf{\chi}_{l_{1},j_{2}}-\mathbf{\chi}_{l_{1},l_{2}}\big{)} \tag{11}\]  
The second step is to evaluate the kernel function on the same grid \(\mathbf{\chi}\). Equation (11) is rewritten in the bi-dimensional convolution form, as introduced by [PERSON] (2006):  
\[\
abla\overline{F}_{\text{bin}}(\mathbf{\chi}_{j_{1},j_{2}})=\sum_{l_{1}=-(M_{1}- 1)}^{M_{1}-1}\sum_{l_{2}=-(M_{2}-1)}^{M_{2}-1}\mathbf{c}_{j_{1}-l_{1},j_{2}-l_{2} }\mathbf{k}_{l_{1},l_{2}} \tag{12}\]  
where \(\mathbf{k}_{l_{1},l_{2}}=n^{-1}\
abla K_{\mathbf{H}}(\mathbf{H}_{1}\mathbf{l}_{1},\mathbf{H}_{2}\bm {l}_{2})\), and \(\mathbf{c}_{l_{1},l_{2}}=0\), for \((l_{1},l_{2})\
otin\{1,\ldots,M_{1}\}\times\{1,\ldots,M_{2}\}\). The third step is to carry Equation (12) out by nested for-loops. However, its computational complexity is \(O\big{(}\mathbf{M}^{2}\big{)}\) time. Many fast algorithms of computing convolution were proposed, such as the Cook-Toom algorithm ([PERSON] and [PERSON], 1970), the Agarwal-Cooley algorithm ([PERSON] and [PERSON], 1970), and the Winograd algorithm ([PERSON], 1970), to reduce the computational complexity significantly. In fact, KDE can also be considered a convolution ([PERSON] and [PERSON], 1970; [PERSON], 1970). The Winograd algorithm is known as a fast convolution to improve computational efficiency and save computational costs through the FFT ([PERSON], 1970). This approach does not impose any restrictions on the kernel. The convolution between \(\epsilon_{1,1,2}\) and \(\mathbf{k}_{l_{1},l_{2}}\) can be carried out quickly by the FFT with only the operation \(O\big{(}\mathbf{M}\mathbb{I}_{j=1}^{d}\big{(}\log\mathbf{M}_{j}\big{)}\big{)}\). The convolution can be rewritten as ([PERSON], 1970; [PERSON], 1970):  
\[\mathbf{Y}=\varphi^{-1}(\varphi(\mathbf{C})\varphi(\mathbf{K})) \tag{13}\]  
where \(\varphi\) is the discrete Fourier transform and \(\varphi^{-1}\) is its inverse transform. Letting \(P_{k}\) be a power of 2 greater than size \(M_{k}\), and \(\mathbf{Y}\) be a \(P_{1}\times P_{2}\) matrix. Writing \(\mathbf{\theta}_{m;n}\) for the \((m\times n)\) zero matrix. The zero-padded version of the binning counts \(\mathbf{C}\) is  
\[\mathbf{C}=\left[\begin{array}{cccc}\mathbf{0}_{M_{1}-1;M_{2}-1}&&\mathbf{0}_{M_{1}-1;M_ {2}}&&\mathbf{0}_{M_{1}-1;P_{2}-2M_{2}+1}\\ &c_{1,1}&\cdots&c_{1,M_{2}}\\ \mathbf{0}_{M_{1};M_{2}-1}&\vdots&&\vdots&\mathbf{0}_{M_{1};P_{2}-2M_{2}+1}\\ &c_{M_{1},1}&\cdots&c_{M_{1},M_{2}}\\ \mathbf{0}  
and of the kernel evaluations \(\mathbf{K}\) is  
\[\mathbf{K}=\left[ \begin{array}{cccccc}k_{-M_{1},-M_{2}}&\cdots&k_{-M_{1},0}& \cdots&k_{-M_{1},M_{2}}\\ \vdots&&\vdots&&\vdots&\\ k_{0,-M_{2}}&\cdots&k_{0,0}&\cdots&k_{0,M_{2}}&\boldsymbol{0}_{2M_{1}+1;P_{2}-2 M_{2}+1}\\ \vdots&&\vdots&&\vdots&\\ k_{M_{1},-M_{2}}&\cdots&k_{M_{1},0}&\cdots&k_{M_{1},M_{2}}\\ &&\boldsymbol{0}_{P_{1}-2M_{1}+1;P_{2}-2M_{2}+1}&&\boldsymbol{0}_{P_{1}-2M_{1} +1;P_{2}-2M_{2}+1}\end{array} \right] \tag{15}\]  
Details about zero-padding versions of involved matrices for performing the FFT operation can be found instance in [PERSON] et al. (1992, Chapter 13) [87] and [PERSON] (2010, Chapter 22) [88].