Recent progress in first principles O(N) methods

We describe recent progress in developing practical first principles method s for which the computer effort is proportional to the number of atoms: lin ear scaling or O(N) methods. It is shown that the locality property of the density matrix gives a general framework for constructing such methods. We then outline some of the main technical problems which must be solved in or der to develop a practical O(N) method based on density functional theory a nd the pseudopotential method. Recent progress in solving these problems is presented, and we show that the spatial cut-off distances needed to achiev e good accuracy are small enough to make the calculations feasible. Paralle l implementation of the O(N) methods in the CONQUEST code is outlined, and it is shown that the: code exhibits excellent linear-scaling behaviour on t est systems of several thousand atoms. It is pointed out that the most impo rtant remaining problem concerns the optimal strategy for seeking the groun d state. It is argued that there are three different mechanisms of ill-cond itioning which cause present search methods to be inefficient, and some par tial solutions are suggested.