We present an optimized linear-scaling purification method for calculation of the density matrix. Traditional purification polynomials, including those proposed by McWeeny and Holas, are monotonic and have stable fixed points at 0 and 1. We relax these conditions and develop optimized purification polynomials which achieve maximum reduction in the LUMO eigenvalue and maximum increase in the HOMO eigenvalue, while heading towards idempotency. We demonstrate that optimized purification achieves appreciable speedup over traditional purification, which increases with decreasing band-gap. We also show improvement over non-monotonic purification proposed by Rubensson, while having identical performance for polynomials of degree 3. (C) 2012 Elsevier B. V. All rights reserved.