A new approach to linear scaling construction of the density matrix is proposed, based on trace resetting purification of an effective Hamiltonian. Trace resetting is related to the trace preserving canonical purification scheme of Palser and Manolopoulos [Phys. Rev. B 58, 12704 (1999)] in that they both work with a predefined occupation number and do not require adjustment or prior knowledge of the chemical potential. In the trace resetting approach, trace conservation is not strictly enforced, allowing greater flexibility in the choice of purification polynomial and improved performance for Hamiltonian systems with high or low filling. However, optimal polynomials may in some cases admit unstable solutions, requiring a resetting mechanism to bring the solution back into the domain of convergent purification. A quartic trace resetting method is developed, along with analysis of stability and error accumulation due to incomplete sparse-matrix methods that employ a threshold tau to achieve sparsity. It is argued that threshold metered purification errors in the density matrix are O(tauDeltag(-1)) at worst, where Deltag is the gap at the chemical potential. In the low filling regime, purification derived total energies are shown to converge smoothly with tau(2) for RPBE/STO-6G C60 and a RPBE0/STO-3G Ti substituted zeolite. For the zeolite, the quartic trace resetting method is found to be both faster and over an order of magnitude more accurate than the Palser-Manolopoulos method. In the low filling limit, true linear scaling is demonstrated for RHF/6-31G** water clusters, and the trace resetting method is found to be both faster and an order of magnitude more accurate than the Palser-Manolopoulos scheme. Basis set progression of RPBE chlorophyll reveals the quartic trace resetting to be up to four orders of magnitude more accurate than the Palser-Manolopoulos algorithm in the limit of low filling. Furthermore, the ability of trace resetting and trace preserving algorithms to deal with degeneracy and fractional occupation is discussed. (C) 2003 American Institute of Physics.