Optimal Trigonometric Preconditioners for Elliptic and Queueing Problems

We consider using the preconditioned conjugate gradient PCG method to solve linear systems Ax = b arising from second-order elliptic problems and queueing problems. The preconditioners are matrices that can be diagonalized by either sine or cosine transform matrices. For 2-dimensional elliptic problems with slowly variating coefficients, the condition numbers of our preconditioned system is of order O(1) whereas the system preconditioned by the MILU and MINV methods are of order O(n), where n is the number of mesh points in one direction For queueing problems our method is also significantly faster than the point-SOR method.