# Multithreading-Based Algorithm for High-Performance Tchebichef Polynomials with Higher Orders
## 2 Background and Literature Review
### Literature Review  
The challenge in the computation of the Tchebichef polynomials emerged from the utilization of the hypergeometric series. This has led to two main issues, which are numerical instability and computational cost. This is because the hypergeometric series shows fluctuations, which lead to significant numerical instability in the results, especially for high-order polynomials. Moreover, the computational complexity of the hypergeometric series is high because of the gamma functions, and this surely results in an increase in the computation time as well as the resources. Toward this end, the three-term recurrence relation (TTRR) has been presented as a solution [43; 44]. The TTRR is considered as an efficient solution that is able to mitigate the computation complexity and to some extent the instability issue, which, in turn, makes the utilization of the Tchebichef polynomials more practical in different applications and fields. Therefore, the recurrence relations in the literature are presented together with a discussion of their limitations. [PERSON] et al. [20] were the first researchers to introduce the set of moment features derived from discrete Tchebichef polynomials for analyzing images. In [20], a new method for the Tchebichef polynomials that eliminates the need for numerical approximation is proposed. The proposed method shows superior development to conventional orthogonal moments like Legendre and Zernike moments. In addition, the Tchebichef moments have been proved to have better feature representation capability. To this end, the TTRR with respect to the variable \(n\) is presented; for the sake of simplicity, we use TTRRn for the TTRR with respect to the variable \(n\). The mathematical steps for computing the TPs coefficients using the TTRRn are shown in Figure 1.  
The TTRRn computes the higher-order coefficients using the lower-order ones recursively as follows:  
\[\mathcal{T}_{n}^{N}(x) =A_{1}\,\mathcal{T}_{n-1}^{N}(x)+A_{2}\,\mathcal{T}_{n-2}^{N}(x) \tag{8}\] \[n =2,3,\ldots,N-1\] \[x =0,1,\ldots,K\]  
where \(K=\frac{N}{2}-1\) and the values of the coefficients \(A_{1}\) and \(A_{2}\) are given by \[A_{1}=\frac{1-N+2x}{n}\sqrt{\frac{4n^{2}-1}{N^{2}-n^{2}}} \tag{9}\] \[A_{2}=-\frac{n-1}{n}\sqrt{\frac{(2n+1)(N^{2}-(n-1)^{2})}{(2n-3)(N^{ 2}-n^{2})}} \tag{10}\]  
The TTRRn requires initial values as depicted in Figure 1, which are \(\mathcal{T}_{0}^{N}(x)\) and \(\mathcal{T}_{1}^{N}(x)\). These initial values are defined as follows:  
\[\mathcal{T}_{0}^{N}(x)=\frac{1}{\sqrt{N}} \tag{11}\] \[\mathcal{T}_{1}^{N}(x)=(2x+1-N)\sqrt{\frac{3}{N(N^{2}-1)}} \tag{12}\]  
where the initials are computed for \(x=0,1,\ldots,K\). As illustrated from the TTRRn, 50% of the coefficients are computed. By leveraging the symmetry relation, the rest of the coefficient values are computed by  
\[\mathcal{T}_{n}^{N}(N-1-x)=(-1)^{n}\mathcal{T}_{n}^{N}(x) \tag{13}\]  
where the symmetry relation is exploited over the range \(n=0,1,\ldots,N-1\) and \(x=L,L+1,\ldots,N-1\). Note that \(L=\frac{N}{2}\). The TTRRn computes polynomial coefficients for the \(n\)th order by exploiting the previous two orders (\(n-1\) and \(n-2\)). However, this algorithm becomes impractical when dealing with a signal size greater than 81 samples because the value of \(\mathcal{T}_{n}^{N}(x)\) grows rapidly with \(N\). As a result, this algorithm is very limited and impractical. To overcome the issue in the TTRRn, the \(x\)-direction recurrence relation (TTRRx) is proposed in [30]. The TTRRx improved the computational efficiency of Tchebichef polynomial coefficients.