Sine transform based preconditioners for solving constant-coefficient first-order PDEs (Q1874672)

The authors consider the first order partial differential equation with constant coefficients \[ {\partial u\over\partial t}+\sigma_1{\partial u\over\partial x} +\sigma_2{\partial u\over\partial y}=g(x,y,t)\tag{*} \] with appropriate initial and boundary values. Equation (*) is discretized using a central finite difference method on a uniform rectangular mesh with \(m_x\) rectangles in the \(x\)-direction and \(m_y\) rectangles in the \(y\)-direction. The matrix \(A\) resulting from this discretization will be diagonally dominant only for special choices of temporal and spatial increments and, indeed, the failure of this condition is of particular interest. A preconditioning matrix is presented, based on a discretization along the \(x\)-direction. This matrix is close to a Toeplitz matrix and multiplication by the preconditioner can be efficiently implemented using a sine transform. Using this preconditioner, the GMRES method is shown to converge in not more than \(m_y+1\) iterations in exact arithmetic. The proof is based on a spectral analysis of the preconditioned matrix, showing that it has \((m_x-1)m_y\) unit eigenvalues and providing an explicit formula for the remaining \(m_y\) eigenvalues. Approximate expressions are provided for the non-unit eigenvalues to illustrate how they are distributed and to show that they remain bounded away from the origin. Numerical experiments are provided that illustrate the superiority of the preconditioner when compared with one presented earlier by \textit{L. Hemmingsson} and \textit{K. Otto} [SIAM J. Sci. Comput. 17, 47-64 (1996; Zbl 0843.65063)].