Project Proposal: Study and Optimization of Algorithms for Parallel Integral Transformation in Computational Quantum Chemistry

Omololu Akin-Ojo, Alston J. Misquitta, Garold Murdachaew, Nirmal Seenu, and Zhao-Hui ``Joe'' Yang

Departments of Physics & Astronomy  and Computer & Information Sciences

University of Delaware

September 21, 2000

Contents

• Contents
• Motivation
• Background
• Problem statement
• Plan of investigation
• Bibliography

Motivation

Computational quantum chemistry can now give accurate results for small molecules and clusters. However, accurate calculations for larger systems (e.g., biological and pharmaceutical molecules and clusters) are still largely intractable due to the speed, memory, and storage limitations of present-day computers. The advent of cheaper and more accessible supercomputing power through the development of parallel workstation networks calls for similar advances in the parallelization of quantum chemical codes and the development of new algorithms to allow medium problems to be treated faster and in more detail and some larger problems to be addressed for the first time. Since its time and memory/storage requirements vary with problem size as O(N⁵) and O(N⁴), respectively, a significant bottleneck in such calculations and a good candidate for algorithmic optimization is the 2-electron integral transformation.

Background

Computational quantum chemists (or chemical physicists) model many-electron atoms, molecules, or clusters and make predictions of their properties. Examples of such properties may be the equilibrium and transition state structures of molecules or clusters, and their ground and excited electronic states. In the Born-Oppenheimer approximation which separates the motion of light electrons from those of heavy nuclei, the determination of all such properties requires first of all the solution of the electronic Schrödinger equation. Many-electron systems do not allow an analytic solution and thus a numerical method must be used. The molecular wavefunction is written as a finite expansion with adjustable coefficients in the atomic wavefunctions of the atoms comprising the molecule. The problem would neatly separate into individual problems for each electron but for the terms such as 1/r₁₂ describing the repulsion between electrons 1 and 2. As a zeroth order approximation, we can treat such terms in an average way and obtain a self-consistent solution. This approach is known as the Hartree-Fock (HF) method for its originators. Since it treats the instantaneous electron-electron repulsion in a self-consistent or average way, it is also known as the self-consistent field (SCF) method.

The resulting problem may be solved iteratively to obtain the molecular energy and corresponding molecular wavefunction (i.e., the values of the expansion coefficients) at the HF level. However, this zeroth order approximation to the solution in most cases does not give results of sufficient accuracy. What is required is a higher ``correlation'' treatment of the electron-electron interaction which properly correlates the instantaneous repulsion between any two electrons. Correlation corrections can be obtained in a number of ways. For example, perturbation theory can be used to correct the molecular HF energy and wavefunction. An important intermediate step in obtaining any correlation corrections past the HF level is the ``integral transformation''.

Problem statement

In the course of obtaining the HF solution, two basic types of integrals are calculated. These are the integrals involving a product of a 1-electron operator between two atomic wavefunctions (1-electron integrals) and the integrals involving a product of a 2-electron operator between four atomic wavefunctions (2-electron integrals). The former integrals can be identified by two indices (and thus form a matrix or a tensor of rank 2) and the latter by four indices (and thus form a tensor of rank 4). Post-HF methods require that these integrals over atomic wavefunctions be transformed into integrals over molecular wavefunctions.

The 1-electron transformation is relatively straightforward and not so time-consuming: 

$$(i\vert j) = \sum_{a,b} C_{ai} C_{bj} (a\vert b)\ \ \ \mbox{or} \ \ \I_{ij} = \sum_{a,b} C_{ai} C_{bj} I'_{ab}.$$ (1)

The 2-electron transformation is the one that presents difficulty in practice:

$$(ij\vert kl) = \sum_{a,b,c,d} C_{ai} C_{bj} C_{ck} C_{dl} (ab......{ijkl} = \sum_{a,b,c,d} C_{ai} C_{bj} C_{ck} C_{dl} I'_{abcd}.$$ (2)

Plan of investigation

For a reasonable-sized problem (N order of 100 atomic wavefunctions), the most direct application of the 2-electron transformation involves N⁸ multiplications and additions. A relatively simple change in the algorithm (breaking the problem into parts) transforms it into 4N⁵ operations, a significant improvement. This is called the N5 algorithm. To reduce the time such a transformation may take in practice, we can parallelize the N5 algorithm. The question is how to do it most efficiently for a given computer architecture and problem size.

Some initial group discussions make it clear that the following factors have to be considered. The data set obtained from the previous stage (HF calculation) should be converted into the format most suitable to be accessed in the transformation algorithm. If the matrices/tensors input are sparse, we need to consider the advantages and disadvantages of the sparse matrix representation and decide upon whether we need to follow the sparse matrix compression. The load distribution should be designed in such a way that the memory requirement on each node is the minimal possible. The load should be balanced equally between the nodes and the algorithm made as linearly scalable as possible.

Guidance for this project will come from the literature and from discussions. [1,2,3,4,5,6,7,8]

Bibliography

1

W. J. Hehre, L. Radom, P. v.R Schleyer, and J. A. Pople, Ab initio Molecular Orbital Theory (Wiley, New York, 1986).

2

A. Szabo and N. S. Ostlund, Modern Quantum Chemistry (Dover, Mineola, NY, 1996).

3

R. Bukowski, discussions.

4

M. Schütz and R. Lindh, Theor. Chim. Acta. 95, 13 (1997).

5

T. L. Windus, M. W. Schmidt, and M. S. Gordon, in Parallel Computing in Computational Chemistry, Vol. 592 of ACS Symposium, edited by T. G. Mattson (American Chemical Society, Washington, DC, 1995), p. 16.

6

T. L. Windus, M. W. Schmidt, and M. S. Gordon, Theor. Chim. Acta. 89, 77 (1994).

7

T. L. Windus, M. W. Schmidt, and M. S. Gordon, Chem. Phys. Lett. 216, 375 (1993).

8

A. M. Márquez and M. Dupuis, J. Comp. Chem. 16, 395 (1995).

Footnotes

... time-consuming:

The (a|b) and (ab|cd) are integrals which may be written as I'_ab and I'_abcd respectively. They, together with the coefficients (the C matrices) are inputs (in the form of double precision numbers stored in some fashion) to the transformation program. The goal is to obtain the transformed integrals (i|j) and (ij|kl) (another set of double precision numbers to be stored in some fashion) which may be written as I_ij and I_ijkl respectively.

About this document ...

Project proposal: Study and optimization of algorithms for parallel integral transformation in computational quantum chemistry

 This document was generated using the LaTeX2HTML translator Version 98.1p1 release (March 2nd, 1998)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 proposal2.

The translation was initiated by Garold Murdachaew on 2000-09-21

2000-09-21