A SCALABLE DIVIDE-AND-CONQUER ALGORITHM COMBINING COARSE AND FINE-GRAIN PARALLELIZATION

We describe an efficient algorithm for carrying out a ''divide-and-con quer'' fit of a molecule's electronic density on massively parallel co mputers. Near linear speedups are achieved with up to 48 processors on a Gray T3E, and our results indicate that similar efficiencies could be attained on an even greater number of processors. To achieve optimu m efficiency, the algorithm combines coarse and fine-grain paralleliza tion and adapts itself to the existing ratio of processors to subsyste ms. The subsystems employed in our divide-and-conquer approach can als o be made smaller or bigger, depending on the number of processors ava ilable. This allows us to further reduce the wallclock time and improv e the method's overall efficiency. The strategies implemented in this paper can be extended to any other divide-and-conquer method used with in an ab initio, density functional, or semi-empirical quantum mechani cal program.