What is the best alternative to diagonalization of the Hamiltonian in large scale semiempirical calculations?

Recently, several linear scaling approaches have been introduced which replace the time dominating diagonalization step in semiempirical methods, enabling practical calculations to be performed on very large molecules. This paper compares the accuracy and performance of pseudodiagonalization (PD), conjugate gradient density matrix search (CG-DMS), the Chebyshev polynomial expansion method (CEM), and purification of the density matrix (PDM) as linear scaling substitutions for diagonalization. The scaling, speed, and reliability of these methods are compared for AM1 single point energy calculations on polyglycine chains (up to 20 000 atoms), water clusters (up to 12 300 atoms), and nucleic acids (up to 6300 atoms).