The Yoshimine sort[1] is an algorithm that is used in quantum chemistryto order lists of two electron repulsion integrals. It is implemented in the IBM Alchemy program suite [2] and in the UK R-matrix package for electron and positron scattering by molecules[3] which is based on the early versions of the IBM Alchemy program suite.
In quantum chemistry, it is common practice to represent one electron functions in terms of an expansion over a basis set,
\chii
The Schrödinger equation, for a system with two or more electrons, includes the Coulomb repulsion operator. In the basis set expansion approach this leads to the requirement to compute two electronrepulsion integrals involving four basis functions. Any given basis set may be ordered so that each function can assigned a unique index. So, for any given basis set, each two electron integral can be described by four indices, that is the indices of the four basis functions involved.It is customary to denote these indices as p,q,r and s and the integral as (pq|rs). Assuming that
\chii
(pq|rs)=\int\int
| \chip(r1) \chiq(r1) \chir(r2) \chis(r2) | |
| \midr1-r2\mid |
dr1 dr2
The number of two electron integrals that must be computed for any basis set depends on the number of functions in the basis set and on the symmetry point group of the molecule being studied.
The computed two electron integrals are real numbers,
(pq|rs)\inR
In the case of real orbitals, p can be swapped with q without changing the integral value,or independently r with s. in addition pq as a pair can be swapped with rs as a pair withoutchanging the integral. Putting these interchanges together means that
\begin{matrix} (pq|rs)=&(qp|rs)\\ &(pq|sr)\\ &(qp|sr)\\ &(rs|pq)\\ &(sr|pq)\\ &(rs|qp)\\ &(sr|qp) \end{matrix}
which is eightfold symmetry. If the molecule has no spatial symmetry, in other words it belongs to the
C1
The Schrödinger Hamiltonian commutes with the operations of the point symmetry group of the nuclear framework of the molecule. This means that a two electron integral can be non-zero only if the product of the four functions transforms, or contains a component which transforms,as the totally symmetric irreducible representation of the symmetry point group to which themolecule belongs.
This means that a computer program for two electron integral processing can precompute the list of basis function symmetry combinations (symmetry blocks) for which integrals may be non zero and ignore all other symmetry combinations. The list of symmetry blocks canalso be ordered. Frequently, the totally symmetric irreducible representation is assignedthe lowest index in the list, typically 1 in Fortran or 0 in the C programming language. Within any given symmetry block, the permutational symmetry of the integrals stillapplies and the integrals can be ordered within that block. For example if the molecule belongs to the
C2
A
B
\begin{matrix} ( A A | A A )\\ ( B B | B B )\\ ( A A | B B )\\ ( A B | A B )\\ \end{matrix}
This means that given the four indices pqrs defining a two electron integral, a unique index may be computed.This is the essence of the Yoshimine procedure.
When the integrals are computed by the integrals program they are written out to a sequential file along with the p,q,r,s indices which define them. The order in which the integrals are computed is defined by the algorithm used in the integration program. The most efficient algorithms do not compute the integrals in order, that is such that the p,q,r and s indices are ordered.
This would not be a problem is all of the integrals could be held in CPU memory simultaneously.In that case the computed integral can be assigned into its position in the array oftwo electron integrals by computing the required index from the p,q,r and s indices.In the 1960s it was essentially impossible to hold all of the two electron integrals inmemory simultaneously. Therefore, M Yoshimine developed a sorting algorithm for two-electron integrals which reads the unordered list of integrals from a files and transforms it into an ordered list which is then written to another file. A by-product of this is that the filestoring the ordered integrals does not need to contain the p,q,r,s indices for each integral.The ordering process uses a direct access file but the input and output files of integralsare sequential.
At the start of the 21st century, computer memory is much larger and for small moleculesand/or small basis sets it is sometimes possible to hold all two electron integrals in memory.In general however, the Yoshimine algorithm is still required.