Graphical Representation of Alpha and Beta Strings

  Any CI program requires some method for assigning a numerical code to each determinant (or configuration). Determinant-based CI's also require an addressing scheme for each alpha and beta string. Such addressing can be facilitated by using graphical representations. This section discusses the construction of simple graphs representing alpha and beta strings, and how the numerical code or address of each string can be calculated from these graphs. Our approach will be based on the work of Duch, who has described [27] the graphical representation of CI spaces in considerable detail.   First, we consider the simple two-slope directed graphs (``digraphs'') which represent alpha or beta strings without consideration of point-group symmetry. Figure 1 presents such a digraph representing all strings with five electrons in seven orbitals (as might be appropriate for the alpha or beta strings of HO in a minimal basis set, neglecting point-group symmetry). Each string is represented by a ``walk'' on the graph, from the head (at e = o = 0) to the tail (at , o = n); the graph should always be traversed in this direction. Moving straight down from vertex to vertex indicates that orbital o + 1 is unoccupied in the current string, while moving down diagonally from vertex to vertex indicates that orbital o + 1 is occupied. Each vertex on the graph is assigned a weight , and each arc connecting two vertices is assigned an arc weight for the arc leaving vertex . Since, in general, two different arcs can leave a given vertex, we write for the arc originating from vertex which leaves orbital o+1 unoccupied, and for the arc which occupies orbital o+1. The index or address of a string or walk is obtained by adding weights for each arc contained in the walk, i.e.\

where is the occupation (0 or 1) of the ith arc, and are the coordinates of the vertices crossed by . The term gives the offset of a given graph, if more than one graph is employed. The index for a determinant is given by , where is the number of alpha strings.   This leads us to write the CI coefficients as a rectangular matrix . Restrictions on the CI space mean that only certain subblocks of the C matrix are allowed to be nonzero.

There are several different methods for assigning the arc weights by which we calculate the index of a string according to equation ( 6.6). Under the lexical ordering scheme,  the tail of an alpha string graph is assigned a weight x=1. Other vertex weights are computed according to the recursive formula

Using lexical ordering, typically all arc weights are set equal to zero, and the arc weights are determined according to

  
Figure 1: Alpha string graph for . Vertex weights are determined according to lexical ordering, and arc weights are given so that the rightmost path has index zero. (a) All unoccupied arc weights are zero. (b) All occupied arc weights are zero.

Figure 1a features vertex and arc weights computed in this manner. A result of the lexical ordering scheme is that paths with a fixed upper part and an arbitrary lower part have contiguous indices. The particular choice of Y values above is appropriate if the rightmost path is to have an index of zero. The same effects can be achieved using

as illustrated in Figure 1b. Any walk has the same index in Figures 1a and 1b. For instance, the walk has an index of 5+4+3+2+2=16 (equation 6.6) from Figure 1a, and an index of 15+1=16 from Figure 1b.

In the so-called ``reverse-lexical'' ordering scheme,   all upper paths for a fixed lower path have contiguous indices. Vertex weights are now determined as

where the overbar indicates reversed-lexical ordering. Figure 2a depicts a reversed-lexical graph with all non-occupied orbital arcs set to zero. The occupied orbital arcs are computed as

Figure 2b is the same except that now all occupied arcs have weights of zero. The non-occupied arc weights are

  
Figure 2: Alpha string graph for . Vertex weights are determined according to reverse-lexical ordering, and arc weights are given so that the rightmost path has index zero. (a) All unoccupied arc weights are zero. (b) Occupied arc weights are set to zero.

Note that string indices for reverse-lexical ordering are not necessarily the same as indices for lexical ordering. For the string considered previously, the index is calculated as 1+1+1+1+6=10 from Figure 2a, or as 5+5=10 from Figure 2b.

The arc weights given in Figures 1 and 2 cause the rightmost path to have an index . If we change the arc weights so that the leftmost path has index , we obtain four more addressing schemes. The two simplest schemes for are

where the overbars indicate that reversed-lexical vertex weights have been used. Alpha strings for 5 electrons in 7 orbitals employing these addressing schemes are depicted in Figure 3.

  
Figure 3: Alpha string graph for , with arc weights determined so that the leftmost path has index zero. (a) Vertex weights for lexical ordering, and arc weights according to , . (b) Vertex weights according to reverse-lexical ordering, and arc weights according to , .

If we add another coordinate to each vertex, we can extend these simple digraphs to include point-group symmetry.