Semi-implicit time discretization of the atmospheric primitive equations results in a modified Helmholtz equation for the pressure. Eigen-mode decomposition of the vertical structure matrix then gives rise to independent problems for each vertical coordinate level. Second-order finite differences are employed in the vertical and high-order finite-elements in the horizontal direction. The independent linear systems on each level are solved using Krylov iteration. Several preconditioning strategies are investigated. An optimized Schwarz method is compared to a new scheme related to the cell discretization algorithm of Greenstadt. The latter yields dramatically improved convergence rates and a reduction in computation time by eliminating communication in matrix-vector products. The link with penalty and discontinuous Galerkin methods for elliptic problems is established.