LAUSR

Abstract We develop a fast solver for the spectral element method (SEM) applied to the two-sided fractional diffusion equation on uniform, geometric and graded meshes. By approximating the singular kernel with a degenerate kernel we construct a hierarchical matrix (H-matrix) to represent the stiffness matrix of the SEM and provide error estimates, which we verify numerically. We can solve efficiently the H-matrix approximation problem using a hierarchical LU (H-LU) decomposition method, which reduces the computational cost to O ( r 2 N d log 2 N ) + O ( r 3 N d log N ) , where r is the rank of the H-LU decomposition, N d is the total number of degrees of freedom and N is the number of elements. However, we lose the high accuracy of the SEM. To prevent this, we solve the corresponding preconditioned system by using the H-matrix approximation problem as a preconditioner, hence, recovering the high-order accuracy of the SEM. Numerical results show that the condition number of the preconditioned system is independent of the polynomial degree P and grows with the number of elements, but at modest values of the rank R (here R is the rank of submatrices of the H-matrix approximation) it is below order 10 in our experiments, which represents a reduction of more than 11 orders of magnitude from the unpreconditioned system. This reduction is higher in the two-sided fractional derivative compared to one-sided fractional derivative. The corresponding cost is O ( r 2 N d log 2 N ) + O ( r 3 N d log N ) + O ( N d 2 ) . Moreover, by using a structured mesh (uniform or geometric mesh), we can further reduce the computational cost to O ( r 2 N d log 2 N ) + O ( r 3 N d log N ) + O ( P 2 N log N ) for the preconditioned system. Furthermore, we compare the present method with the adaptive cross approximation (ACA), which is kernel independent and relies on the coefficient matrix. The comparison shows that the accuracy using the present algorithm is better than the one using ACA for the H-matrix approximation problem, and furthermore, we have observed that the ACA method may fail to converge in some cases.