Preconditionings based on incomplete block odd-even cyclic reduction for the Chebyshev and conjugate gradient polynomial iterative methods have been shown to be effective for accelerating the convergence of the solution of linear systems that arise from discrete approximations of elliptic partial differential equations. The main contribution of this paper is to extend these methods to the important case of red/black partitioning of equations and unknowns and to demonstrate that a significant reduction in computations can be realized by applying preconditioned polynomial methods to the “reduced systems” obtained from the original systems by eliminating approximately half of the unknowns.This paper also compares the performance of several preconditioned polynomial methods for solving a two-dimensional elliptic equation on the CYBER 205 vector computer. The most effective methods tested are shown to be (i) the new reduced system conjugate gradient method with preconditioner based on incomplete block odd-even cyclic reduction, and (ii) the classical reduced system conjugate gradient method with preconditioner $D_B $, the tridiagonal matrix associated with the black unknowns. Of these methods, the former is better in most cases, especially for some slowly converging problems.