2. Theory
The set of programs in FS98 were originally written to solve two-dimensional surface structure problems, but also do a good job with two-dimensional bulk transmission electron diffraction data. The basic idea is to find phases for the diffracted beams which are consistent with the fact that the diffraction (x-ray or transmission electron) comes from atoms. This is the idea behind what are called "Direct Methods", and for the three-dimensional x-ray case there is an extensive literature (e.g. [6]) as well as Public Domain or commercial software available.
For the case of a two-dimensional surface structure, there are some subtle differences from the more standard three-dimensional case which makes the problem harder [1]. The most important of these is the fact that some of the surface reflections lie underneath bulk beams, and the intensity of the latter is often orders of magnitude larger. It is therefore difficult if not impossible to determine the intensities of these reflections. The surface component of these reflections may be very large (relative to the other surface reflections). Without some method of taking these unmeasured reflections into account, the problem may be unsolvable.
Where FS98 differs from conventional Direct Methods code, and how it takes account of these reflections depends upon what is called a "Feasible Set" approach [2]. To explain this, we need to think about the problem in terms of sets. One set we know is the set of all possible (complex) values for the structure factors whose moduli are the measurements, SM. We also know that the charge density (for x-rays) or electrostatic potential (for electrons) in real space is real and positive; we have a second set for all possible positive values SP. Finally, there are certain probabilistic relationships between the phases due to the fact that the scattering comes from atoms, which we can call SA. The real phases for the structure factors must belong to all these three sets, so the set of possible values or Feasible set is defined as the intersection of these:
SF = SM .and. SA .and. SP
The important point is that the unmeasured reflection must also be such that the charge density (electrostatic potential) is positive, and well as coming from atoms. Therefore their amplitudes and phases cannot be totally random, and can in most cases be interpolated rather well. (While interpolation of the amplitudes is only fair, interpolation of the phases is rather good in most cases and the phase is more important than the amplitude.) The method for determining SP uses a minimum relative entropy operator (related to the relative entropy functional or Kullback-Leiber metric [7]) and is somewhat similar to a Maximum Entropy approach (e.g. [8]).
To go a little deeper and introduce a couple of concepts that are required later, the idea of a projection is relevant. A projection takes some given values (e.g. for the charge density in real space) and moves them to the closest values which obey a given constraint, i.e. belongs to a particular set. For instance, projection onto the set of positive charge density (positivity) is done by setting all negative values to zero. Writing such a projection operator as P, one can also define an relaxed operator T by
T =lambda P + (1-lambda)
The term lambda here is called the relaxation parameter and in general should be between 1 and 2 for best result. The algorithm combines such operators in a parallel fashion together with over-relaxation. Unfortunately the "best" value of labmda is rather problem specific, as is the best parallel combination! The default parameters (see section 3) do a fairly good job, although if you are having trouble you can adjust some of them. (It is probably best to do this first with a test case.) In the FS98 programs, the phase and amplitude prediction is achieved by an iterative process of projecting onto the sets SM, SA and SP. The cycle of projections is continued as long as the Figure of Merit (see below) decreases with each cycle.
With phases for the measured reflections, and amplitudes and phases for the unmeasured ones estimated one can calculate a "map". This map will show peaks at probable sites of the atoms. The exact positions of these peaks may not be very accurate (0.1-0.2 Angstroms off), and the peaks may be too large/high or too small/low and there can be extra, erroneous peaks. However, they are good enough for the structure to be determined in almost all cases, and subsequently refined.
For any given map, one can associate a Figure of Merit or FOM which is a measure of how well the phases obey the condition for intersection of the three sets mentioned above. In the ideal case this FOM will be zero for the true phases, but there are always experimental measurement errors and the probability relationships are probabilities only, not mathematical identities. The smaller the FOM, the more probable it is that the phases are correct.
To search for the smallest FOM values, the program uses a genetic algorithm [3]. A certain number of the reflections (determined by what is called a divergence analysis) are permuted in relatively coarse steps (45 degrees in the default case, 180 degrees for centrosymmetric reflections). These initial phases determine a "starting point" for the phase extension. For each set of initial phases, the rest of the phases are determined using projection onto sets (in which the initial reflections are also allowed to relax - i.e. change from their initial values). Each "individual" in the genetic algorithm represents a particular starting set. The genetic algorithm runs through a number of populations, similar for instance to breeding mice, at each stage selecting for the individuals (phase values) for which smaller FOMs are obtained from the iterative projection process. It retains as members of the feasible set a number of solutions which give small FOMs. While in certain cases all of these end up as being only minor variations upon a given structure, this need not be the case. Sometimes a number of different structures (3-5) will come out. These are all feasible solutions, and will all have to be subsequently tested by some sort of refinement.
The current programs only go as far as determining the set of feasible solutions, and allowing output of these either as hkl F and phase, images which can be read by SEMPER or as GIF files. (A prototype Fortran structure completion code is included, although this is not complete and some additional work by the user will almost always be required, for instance to ensure that the solution is chemically reasonable.) Software is available for completing the structure using SEMPER, and one can probably use the output phases in other programs. However, there is generally enough information available for a structure determination. As an important point, it should be appreciated that, provided that a good search has been done, if a structure is not part of the output feasible set it is probably not correct. Hence, rather than guessing structures then refining them against experimental data as is currently done in surface science, all that is needed is to test the members of the feasible set.
In terms of application of the code to bulk transmission electron diffraction data, one has to go back to the concept of feasible sets. Unlike x-ray diffraction, transmission electron diffraction data is not kinematical beyond typical thicknesses of about 20 Angstroms. However, in many cases |1- y(r)| (where y(r) is the exit wavefunction) has peaks at the atomic sites and is flat in between them [4,5]. As a consequence, |1- y(r)| behaves rather like the kinematical potential and can be recovered using experimental TED amplitudes. In some cases this can be done without any other information, although it will work better if some phases are already known from, for instance, a high resolution image. Note that the heights of the peaks will not be the same, and in many cases for realistic samples (100-200 Angstroms thick) the lighter atoms will be more apparent. Caveat: the code works well with kinematical data, but is not so good for dynamical data. Here the issue is to find an appropriate dynamical projection operator which is a topic of current work.