We consider applying the preconditioned conjugate gradient (PCG) method to solving linear systems Ax = b where the matrix A comes from the discretization of second-order elliptic operators with Dirichlet boundary conditions. Let (L+ ) -1 (L t + ) denote the block Cholesky factorization of A with lower block triangular matrix L and diagonal block matrix . We propose a preconditioner M = ( L + Λ ) Λ -1 ( Lt + Λ ) with block diagonal matrix Λ and lower block triangular matrix L. The diagonal blocks of Λ and the subdiagonal blocks of L are respectively the optimal sine transform approximations to the diagonal blocks of and the subdiagonal blocks of L. We show that for two-dimensional domains, the construction cost of M and the cost for each iteration of the PCG algorithm are of order O(n 2 log n). Furthermore, for rectangular regions, we show that the condition number of the preconditioned system M -1 A is of order O(1). In contrast, the system preconditioned by the MILU and MINV methods are of order O(n). We will also show that M can be obtained from A by taking the optimal sine transform approximations of each sub-block of A. Thus, the construction of M is similar to that of Level-1 circulant preconditioners. Our numerical results on two-dimensional square and L-shaped domains show that our method converges faster than the MILU and MINV methods. Extension to higher-dimensional domains will also be discussed.