Fast transforms for tridiagonal linear equations (Q1343044)

This paper studies the use of Fourier, sine and cosine transformations for solving (in the 1D case) or preconditioning (in the 2D case) linear systems, which arise from the discretization of elliptic problems. In view of the connections between the circulant matrix by congruence transformation with the Fourier or the sine matrices, a direct solver is given in the 1D case, using only FFT and the Sherman-Morrison-Woodbury formula. By taking the Kronecker product of the one-dimensional transformations, for the 2D case, a good preconditioner for the conjugate gradient method is suggested. Numerical examples show that these new methods are fast and highly parallelizable.