A study of parallel implicit solvers for accelerating convergence to steady state solutions of the compressible Navier-Stokes equations with finite-rate chemistry is presented. The solvers in question are pertinent to applications of hypersonic flows that can be modeled as laminar, or to turbulent flows that can be simulated using the Reynolds averaged (RANS) equations. The current state-of-the-art method, the Data-Parallel Line Relaxation (DPLR), is examined. Its convergence properties are evaluated for a class of challenging external aerodynamics problems. A more sophisticated method based on the GMRES linear system solver is built around the DPLR method, where the DPLR is used as a preconditioner. The convergence characteristics of the augmented method are studied for model problems of practical interest. Results show that the more sophisticated method has better convergence properties, but exhibits higher cost and should be used selectively.