Linear scaling algorithms based on Fermi operator expansions (FOE) have been considered significantly slower than other alternative approaches in evaluating the density matrix in Kohn-Sham density functional theory, despite their attractive simplicity. In this work, two new improvements to the FOE method are introduced. First, novel fast summation methods are employed to evaluate a matrix polynomial or Chebyshev matrix polynomial with matrix multiplications totalling roughly twice the square root of the degree of the polynomial. Second, six different representations of the Fermi operators are compared to assess the smallest possible degree of polynomial expansion for a given target precision. The optimal choice appears to be the complementary error function. Together, these advances make the FOE method competitive with the best existing alternatives. (C) 2003 American Institute of Physics.