# Multithreading-Based Algorithm for High-Performance Tchebichef Polynomials with Higher Orders
## 3 The Proposed Multithreaded Algorithm  
This section provides a detailed explanation of the proposed algorithm, which efficiently computes Tchebichef polynomials by leveraging multithreading and a recurrence approach. By migrating single-thread processing to multithreading processing, we adopt parallel execution and multithread-based fast TP coefficient calculation for the large-scale dimensional problem. We are able to achieve parallelization, where multiple threads execute distinct tasks concurrently, utilizing multiple processing cores or resources. We have identified the independence of the recurrence relation in coefficient computation, enabling parallelism. This allows threads to be distributed across cores, resulting in accelerated computations through simultaneous execution. The algorithm begins with Region 1 (see Figure 5), where the aim is to compute the initial sets for the rest of the algorithm. The initial sets are computed over the range \(x=0,1\) and \(n=0,1,\ldots,Q\). This region is processed in a single thread. To compute these values, the following steps are followed:  
1. Compute the value of \(\mathcal{T}_{0}^{N}(0)\) using (17). 2. Compute the coefficient values of \(\mathcal{T}_{n}^{N}(0)\) over the range \(x=0\) and \(n=1,2,\ldots,Q\) using (18), where \(Q=\frac{N}{4}-1\). 3. Compute the value of \(\mathcal{T}_{n}^{N}(1)\) over the range \(x=1\) and \(n=0,1,\ldots,Q\) using (19). Once the computation of the initial sets is carried out, the rest of the polynomials can be computed. In Region 2, the algorithm applies multithreading to process the data in parallel. The number of threads (\(T\)) is set, and each thread is assigned a portion of the rows to be processed, which are \(Th_{1}\), \(Th_{2}\), up to \(Th_{T}\). Each thread processes a number of rows, referred to as the bunch size \(BS1\), which is calculated as \(BS1=(Q+1)/T\). The algorithm uses a recurrence relation in the \(x\)-direction for the computation of the values in this region. This means that the computation in this region depends on the previous values of \(x\). By using multithreading, the algorithm can process multiple rows (bunch size) simultaneously, which means speeding up the computation. Figure 4: The steps of the sequential TTRRnxa algorithm. In Region 3, the algorithm computes the coefficients using \(T\) threads using the TTRR in the x-direction. Each thread is assigned a portion of the columns (bunch size \(BS2\)) to be processed, the number of columns processed by each thread \(BS2=\left(N/2-L_{x}\right)/T\), where \(L_{x}\) is computed using (20). The algorithm uses a recurrence relation in the \(x\)-direction for computing the coefficients in this region. This means that the computation in this region depends on the previous coefficient values of \(x\). In Region 4, the algorithm computes the parameters using multithreading, a recurrence relation in the \(n\)-direction, and an adaptive threshold. Each thread is assigned a portion of the rows (bunch size \(BS3\)) to be processed, with the number of rows processed by each thread \(BS3=\left(N-1-L\right)/T\), where \(L=N/4+1\). The algorithm uses a recurrence relation in the \(n\)-direction, but this time in reverse order. This means that the computation in this region depends on the previous values of \(n\), but in a reverse manner. The algorithm  
Figure 5: Multithreading-based algorithm for fast TTRRnxa calculation. (**a**) Regions of the multithreaded algorithm, and (**b**) distribution of the threads in the multithreaded algorithm. also employs an adaptive threshold, which ensures stability of computing the coefficients and detects the first occurrence of instability in the coefficient value at the \(n\)th order. The adaptive threshold condition is  
\[|\mathcal{T}_{n+1}^{N}(x-1)|>\mathcal{T}_{n+1}^{N}(x) \tag{21}\]  
When this condition is true, the coefficients are set to 0 (region 5) and the recurrence relation is stopped at this row. This means that the algorithm effectively prunes the computation.