O(N) Algorithms and HPC
Traditional methods of electronic structure calculation usually take a computational time proportional to N3, or possibly N2, for large numbers, N of atoms in the system. The goal of research in the O(N) field is to develop new methods which take a computer time proportional to N, a so called O(N) method. Theoretically such scaling can be achieved because of the localisation of the one-particle density matrix referred to by Walter Kohn as its "short-sightedness", i.e. the density matrix in one region of the system is insensitive to the atomic positions in very distant regions.
A number of UK groups are involved in research relating to O(N) algorithms (UCL, Daresbury, Bristol). The CCP9 O(N) algorithms group was founded in 1999 in order to make this work more effective by enhanced collaborations and exchanges of ideas.
The project concerns the development - theoretical and computational - of new 0(N) methodologies to tackle the electronic structure of systems in excess of 1,000 atoms. This theme unites the whole of the CCP9 community and harvests their combined expertise. It will draw from all present experiences with TB-orbitals, localized and Wannier functions, screened LMTO's and KKR's to construct a variety of O(N) codes to tackle problems such as chemical reactions at surfaces, magnetics and magnetoelectronics, mechanical properties for high temperature alloys, metal-ceramics interfaces, high Tc superconductivity. As is usual in the arena of ab initio electronic structure calculations no single method or approach can solve all of the above problems and the multipronged approach will ensure substantial progress on these fundamental problems of technological importance.
Of course practical O(N) algorithms must also make efficient use of the latest generation of high performance computing (HPC) machines. In fact O(N) algorithms usually have a high level of paralellism which makes them well suited for modern workstation clusters and massively parallel machines such as the CSAR Cray T3E in Manchester. This CCP9 project will therefore also be concerened with issues of HPC and the application of HPC to the next generation of electronic structure algorithms.
