# Structure Approximation-Based Preconditioning for Solving Tempered Fractional Diffusion Equations
## 3 Structure Approximation-Based Preconditioning  
In this section, we first construct an inverse approximation for the coefficient matrix based on its structure and the row-by-row strategy. In addition, we approximated the involved SPD Toeplitz matrix by the corresponding \(\tau\) matrix, thereby introducing a structure approximation-based preconditioner to address the targeted linear system (5). The row-by-row approximation strategy [25] takes advantage of the fact that \(e_{i}^{T}A=e_{i}^{T}K_{i}\). Here we take the approximation as \(e_{i}^{T}A^{-1}\approx e_{i}^{T}K_{i}^{-1}\), where \(e_{i}\) represents the \(i\)-th column of the identity matrix, \(K_{i}=I+d_{i}G,i=1,2,\ldots,N\). Based on this, we obtain the approximate inverse preconditioner \(P_{1}\)  
\[P_{1}^{-1}=\sum_{i=1}^{N}e_{i}e_{i}^{T}K_{i}^{-1}.\]  
Recognizing that \(G\) exhibits an SPD Toeplitz structure, we employ the \(\tau\)-based matrix to derive an efficient approximation of \(G\)[15]. For convenience, the first column of the \(G\) matrix can be expressed as \(-\frac{\Delta t}{2\hbar^{\beta}}\Big{[}2\Big{(}g_{1}^{(\beta)}-\rho_{\alpha} \Big{)},g_{0}^{(\beta)}+g_{2}^{(\beta)},g_{3}^{(\beta)},\ldots,g_{N}^{(\beta) }\Big{]}^{T}\). According to [15], we can compute the \(\tau\) matrix approximation using Hankel correction  
\[\tau(G)=G-HC(G), \tag{8}\]  
where \(HC(G)\) is a symmetric Hankel matrix, and its anti-diagonal elements can be computed from the corresponding elements in the following first column and last column:  
\[-\frac{\Delta t}{2\hbar^{\beta}}\Big{(}g_{3}^{(\beta)},g_{4}^{(\beta)},\ldots,g_{N}^{(\beta)},0,0\Big{)}^{T},\quad-\frac{\Delta t}{2\hbar^{\beta}}\Big{(} 0,0,g_{N}^{(\beta)},\ldots,g_{4}^{(\beta)},g_{3}^{(\beta)}\Big{)}^{T}. \tag{9}\]  
It is well-known that \(\tau(G)\) defined in (8) admits diagonalization via the discrete sine transform:  
\[\tau(G)=S\Lambda S,\quad S=\left(\sqrt{\frac{2}{N+1}}\cdot\sin\frac{\pi ij}{N +1}\right),\quad i,j=1,2,\ldots,N, \tag{10}\]  
where \(\Lambda=\text{diag}(\lambda_{1},\lambda_{2},\ldots,\lambda_{N})\), and S is the discrete sine transform matrix. Clearly, \(G_{j}=I+d_{j}\tau(G)\) remains a \(\tau\) matrix. Using the \(\tau\) matrix \(G_{j}\) to approximate the SPD Toeplitz matrix \(K_{j}\), we obtain the \(\tau\) matrix-based approximate preconditioner  
\[P_{2}^{-1}=\sum_{i=1}^{N}e_{i}e_{i}^{T}G_{i}^{-1}. \tag{11}\]  
With the preconditioner \(P_{2}^{-1}\), we need to compute \(O(N)\) discrete sine transforms for each iteration, which is still computationally intensive. As carried out in [25], we consider using interpolation methods to reduce computational complexity. Define \(\{x_{i}\}_{i=1}^{N}\) as the set of all discrete points in the interval \([a,b]\), and the function \(q_{k}(x)=\frac{1}{1+\lambda_{k}d(x)}\), where \(\lambda_{k}\in sp(\tau(G))=\{\lambda_{1},\lambda_{2},\ldots,\lambda_{N}\},k=1, 2,\ldots,N\). Select \(l(l\ll N)\)interpolation points \(\{\big{(}\hat{x}_{j},q_{k}(\hat{x}_{j})\big{)}\}_{j=1}^{l}\) in \((x_{i},q_{k}(x_{i}))\}_{i=1}^{N}\), and then piecewise linear interpolation is applied to construct the interpolating function  
\[ \begin{split} p_{k}(x)&=\phi_{1}(x)q_{k}(\hat{x}_{1 })+\phi_{2}(x)q_{k}(\hat{x}_{2})+\dots+\phi_{l}(x)q_{k}(\hat{x}_{l})\\ &=\sum_{s=1}^{l}\phi_{s}(x)q_{k}(\hat{x}_{s}).\end{split}  \tag{12}\]  
By leveraging Equation (10), each \(G_{j}\) is diagonalized into the form \(G_{j}=SA_{j}S\) for \(j=1,2,\dots,N\) where S denotes the discrete sine transform matrix, and \(\Lambda_{j}\) represents a diagonal matrix containing the eigenvalues of \(G_{j}\). Then, applying interpolation (12) to approximate \(G_{j}^{-1}\), we have  
\[G_{j}^{-1}\approx S\Bigg{(}\sum_{s=1}^{l}\phi_{s}(x_{j})\Lambda_{s}^{-1} \Bigg{)}S. \tag{13}\]  
Replacing \(G_{j}^{-1}\) in (11) with approximation values (13), we propose the approximate inverse preconditioner as  
\[