Summary: Recently, a linearly scaling method for the calculation of the electronic structure based on the Korringa-Kohn-Rostoker Green function method has been proposed. The method uses the transpose free quasi minimal residual method (TFQMR) to solve linear systems with multiple right hand sides. These linear systems depend on the energy-level under consideration and the convergence rate deteriorates for some of these energy points. While traditional preconditioners like ILU are fairly useful for the problem, the computation of the preconditioner itself is often relatively hard to parallelize. To overcome these difficulties, we develop a new preconditioner that exploits the strong structure of the underlying systems. The resulting preconditioner is block-circulant and thus easy to compute, invert and parallelize. The resulting method yields a dramatic speedup of the computation compared to the unpreconditioned solver, especially for critical energy levels.