# Integral Prescreening in calculation of Electron Repulsion Integrals?

I am trying to write a basic Hartree-Fock program that can calculate the total energy and molecular orbitals of any molecule at arbitrary basis sets largely as a self-taught effort.

I am able to calculate the required integrals, but the computational effort required to evaluate ERIs is prohibitively expensive even for benzene at a slightly larger basis set of 6-31g(d). I tried printing out the ERI matrix and saw that many of the integrals are very close to zero.

I understand that ERIs can be screened using the Schwartz inequality $$(ab|cd) \le \sqrt(ab|ab)*\sqrt(cd|cd)$$.

By my understanding, $$(ab|ab)$$ term is the ERI for the basis functions centered at $$a$$ and $$b$$. So, this should only save calculation costs of one ERI integral, right?

The exact number saved will depend on the system size and geometry, but apart from for very small systems it will be many more than 1. Consider the two methods for a system that contain $$N$$ basis functions

Firstly the naive method: Simply calculate $$(ab|cd) \space \forall \space a,b,c,d$$. This will clearly require $$O(N^4)$$ integrals to be evaluated.

Secondly this time with screening:

• First calculate and store in memory $$(ab|ab) \space \forall \space a,b$$ This clearly is $$O(N^2)$$ integrals, which is insignificant with the $$O(N^4)$$ results we have to finally calculate
• Next calculate the biggest value of $$|(ab|ab)| \space \forall \space a,b$$. Call it $$I_{max}$$ . This again requires an insignificant $$O(N^2)$$ operations
• Now make a list of $$a,b$$ for which $$|(ab|ab)| * I_{max} > tolerance$$. These are the only integrals which you need to consider to be non-zero. Again this is at worst an insignificant $$O(N^2)$$ operations.
• Now calculate the integrals $$(ab|cd)$$ where $$a,b$$ are taken from the list just generated and $$c,d$$ are also taken from that list. All other integrals are (close to) zero
• In the limit of a very large system this reduces the number of integrals from $$O(N^4)$$ to $$O(N^2)$$. This is a huge reduction, many, many orders of magnitude.

What physically is going on is the list you generate is the list of basis functions which have a significant overlap. Thus for a given $$a$$ the list of associated $$b$$ will be those basis functions in some sense close to $$a$$ in space. For a very large system this is independent of the total system size - each basis function only overlaps with a small subsection of the system, and increasing the system size does not increase the number of basis functions that $$a$$ interacts with. Thus for a given $$a$$ the number of overlaps in a large system is $$O(1)$$. There are $$N$$ $$a$$ hence the size of the list is $$O(N)$$. And you have a nested loop over the list, so the total work is $$O(N^2)$$

However note this is the limit for large systems, for small systems the savings will be smaller, and for very small systems there may be no measurable saving at all. This is simply because $$a$$ now overlaps with all the other basis functions, so no screening is possible.

Note also it is possible to reduce the limit to $$O(N)$$. But that requires more advanced methods.

• Thanks for the explanation. |(ab|ab)| is the set of all (ab|ab) integrals right? I did not quite understand the reason for calculating the maximum of that set. Are you speaking of batch processing of ERI integrals? Commented Nov 23, 2022 at 2:20
• Imax is useful as you can very quickly answer whether the a,b basis set pair is involved in any integrals - if |(ab|ab)|*Imax is less than your integral tolerance you can instantly ignore every integral that is of the form (ab|**) (and permutational symmetry related) Commented Nov 23, 2022 at 9:31
• Note the above is just an outline of the ideas and one possible way of implementing the scheme. It's not the only way, but other ways will all be closely related conceptually to the above. Commented Nov 23, 2022 at 9:32