2.1. Searching for the crystal system

The SVD-Index algorithm copes with a moderate amount of random absences. With regard to systematic absences, it is sufficient to apply SVD-Index consecutively with hkl values corresponding to minimum-symmetry Bravais lattices from each crystal system and in decreasing order of symmetry. Monoclinic lattices are treated differently: a search is performed using the six unique sets of hkl values corresponding to the space groups P2, P2₁, Pc, P2₁/c, C2 and Cc, and not just the Bravais lattices. On a 600 MHz personal computer, SVD-Index searches all crystal systems down to triclinic in approximately 3 min.

2.2. Enhancing the chances of success - a weighting function W_hkl

It has been assumed that high d-spacings are more likely to be assigned correct hkl values than low d-spacings; the reason is that there are fewer lower order hkl values than higher order hkl values. It has also been assumed that large differences 2_hkl between the observed d-spacing and the d-spacing assigned in step (iii) of Table 1 should be weighted more than small 2_hkl differences. With these considerations in mind, the weighting function

has been formulated and applied to both sides of equation (1). I_o corresponds to the integrated intensity under the Bragg peaks and its use assists in the determination of impurity lines. An optimum setting for m occurs around m = 4; however, as will be demonstrated below, randomizing m between 0 and 4 produces better results. Proof of this is difficult to obtain; at present it can only be speculated that a degree of randomness introduced into the weighting helps the SVD process search more parameter space.

2.3. Including a zero error

For a zero error Ze in 2°, the following relation in terms of the radiation wavelength can be written:

Using small-angle approximations and ignoring second-order terms, equation (5) can be approximated without significant loss as

Since the 1/d ² in equation (6) represents the left-hand side of equation (1), we can substitute for the 1/d ² in equation (5) to obtain

Equation (7) is therefore used when a zero error is included, but not in an immediate sense. When solving the equations represented by equation (7), the absolute value of Ze as returned by SVD [step (iv) of Table 1] is often too large (>0.1° 2). This is due to grossly incorrect hkl assignments in step (iii) of Table 1 occurring in the early iterations of Table 1. To avoid this situation, the process of Table 1 is first performed without a zero error and then a second time with a zero error. With this strategy, the finding of the correct solution is not hindered with zero errors of up to ±0.05° (2).

2.4. Considering the effects of d-spacing errors

Apart from a zero error, d-spacings obtained from powder diffraction data by means of non-linear least-squares fitting of peaks include an error term often in the range of ±0.0025° (2) for well resolved peaks to ±0.03° (2) for overlapping peaks. Errors of this magnitude do not significantly hinder the SVD-Index algorithm, except for a bias towards fitting high d-spacings introduced by the weighting function of equation (4). A more probable estimate of the lattice parameters is obtained when the equations (7) are all given the same weighting by setting W_hkl = d_o ². Immediate assignment of this weighting, however, reduces the chances of getting close to the correct solution, and thus, similar to the zero-error procedure, the process of Table 1 is first executed with the weighting shown in equation (4) and then a second time with the weighting of d_o ².

The final SVD-Index algorithm for the case of a zero error and errors in the d-spacings executes the process of Table 1 three times for each randomly chosen set of X_nn parameters. The first call is made with the weighting function of equation (4) and no zero error, the second is made with the weighting function of equation (4) and a zero error included, and the third is made with a zero error included but with the weighting function W_hkl = d_o ². The first execution of Table 1 executes step (iv) approximately five times on average before convergence; the second and third executions of Table 1 execute step (iv) approximately once. During the third execution of Table 1, observed d-spacings that have closest calculated d-spacings that are more than 0.05 2° away are ignored and thus un-indexed. This reduces the possibility of impurity lines being included in the SVD process.

3.1. Analysing the behaviour of Table 1 and the weighting function W_hkl

For 1000 triclinic input test lattices, sets of 15 input d-spacings were generated and corresponding X_nn values from these X_nn,true were varied according to the formulation X_nn,start = X_nn,true(1 + R), where R is a uniform deviate random number between -1 and 1. For each of the test input lattices, the corresponding X_nn,start values were used in the process of Table 1. Fig. 1 shows the results for the cases with and without the weighting function of equation (4) where it is seen that the weighting function significantly increases the chances of finding the correct solution. Also shown is that the SVD process of Table 1 determines the correct X_nn values 16.5% of the time for deviations of ±10% ( = 0.1) of the input X_nn values; this is a significant success rate considering that the process of Table 1 was executed only once. With the weighting function of equation (4), similar tests on primitive monoclinic and orthorhombic lattices of lowest symmetry produced success rates of 75.1 and 57.3%, respectively, for = 0.3; this contrasts with the triclinic case of 4.4%. Using hkl values from the lower-symmetry Bravais types, but introducing more symmetry into the test input lattices using the space groups P2₁/c and P2₁2₁2₁ for the monoclinic and orthorhombic cases, respectively, produced success rates of 69.8 and 54.5% for = 0.3. Thus the systematic absences reduced the percentage success rates, but not by much. However, because there are only six unique sets of monoclinic hkl values, SVD-Index uses these when searching for monoclinic solutions.

Figure 1 For 1000 input test triclinic lattices, the number of times the correct solution is found expressed as a percentage after executing the process of Table 1 versus random changes in the true Xnn values of the input test lattices as determined by . R corresponds to a uniform deviate random number between -1 and 1. The test lattices were generated with randomly chosen volumes between 100 and 4000 Å3.

Setting W_hkl of equation (4) to d_o ^m, m was varied from 0 to 10 and at each value the process defined in Table 2 was executed 10000 times with differing sets of d-spacings corresponding to different test input lattice parameters. N₁ and N₂ of Table 2 were set to 1 and the process of Table 2 terminated when V₁ > 4000 Å³; a single pass of Table 2. Fig. 2 shows percentage results indicating the number of times the correct solution was found. The process of Table 1 was least effective at finding the correct solution at m = 0; at m 4 the chances are significantly improved. Instead of constant m values, the m values were randomly varied between 0 and 6, producing a significant increase of the percentage success rate to 8.4%. Using W_hkl as defined in equation (4) and executing the process of Table 1 a further 10000 times with different sets of d-spacings, resulted in a percentage success rate of 11.8%. This shows that the inclusion of an appropriate term that considers the differences between the calculated and input 2 positions increases the chances of finding the correct solution. Further investigation into weighting schemes may well yield even better success rates.

Figure 2 For triclinic lattices, percentage success rate of finding the correct input test lattices after performing the process of Table 2 10000 times as a function of m of the weighting function Whkl of equation (4). N1 and N2 of Table 2 were both set to 1.

3.2. Examining the process of Table 2

Table 5 shows statistics obtained from solving test input lattices comprising 10 and 20 input d-spacings. Here it is seen that the average number of calls to Table 1 is relatively small for the three crystal systems listed and that the maximum number of calls to Table 1 before the correct solution is found is approximately an order of magnitude greater than the average. Also seen is that the case of 20 input d-spacings requires fewer calls to Table 1.

Table 5 Statistics obtained from executing the process of Table 2 for various lattice types for 10 and 20 input d-spacings Each column comprises data resulting in 400 solvable test input lattices. The first row gives the percentage of lattices that are either unsolvable or do not have a unique solution.   Orthorhombic Monoclinic Triclinic   10 d-spacings 20 d-spacings 10 d-spacings 20 d-spacings 10 d-spacings 20 d-spacings % Unsolvable 25 1.5 40 9 70 12 Average number of calls to Table 1 before correct solution is found 74 63 87 78 304 105 Maximum number of calls to Table 1 before correct solution is found 1346 1412 2053 1154 7401 1168

The data of Table 5 are the result of a general randomization of lattice parameters and do not highlight difficulties encountered when one or two of the lattice-parameter lengths are small. This is illustrated in Figs. 3(a)-3(c), which show the average number of calls to Table 1 before finding the correct test input lattice versus the ratio of the largest lattice-parameter length on the smallest lattice-parameter length. Lines labeled `1 Short' correspond to test input lattices generated with one short lattice-parameter length and one long lattice-parameter length with the third lattice-parameter length being half of the long and the short. Uniform deviate random variations in the subsequent lattice-parameter lengths from -0.5 to 0.5 Å were introduced and 20 test input d-spacings were generated according to the removal scheme of Table 4. The lines labeled `2 Short' are similar except that two of the test input lattice-parameter lengths are short. The absence of data for ratios > 6 for triclinic lattices is due to the fact that for 20 input d-spacings it is difficult to generate the test input lattices as approximately 90% are unsolvable and therefore rejected. For the `1 Short' lattice-parameter case, the maximum ratio possible for a triclinic lattice is also around 6 as larger ratios result in volumes greater than 4000 Å³.

Figure 3 Using the strategy of Table 2, plots (a) to (c) show the average number of calls to Table 1 before finding the correct test input lattice versus the ratio of the largest lattice-parameter length to the smallest lattice-parameter length. Each data point corresponds to results obtained from 400 test input lattices.

Figs. 3(a)-3(c) show that the average number of calls to Table 1 required in order to find the correct input lattice increases as a function of the ratio of the largest to the smallest lattice-parameter length. This is expected as the larger ratios have hkl values that are dependent on the small lattice-parameter lengths only, and these are intermixed with hkl values that are dependent on the larger lattice-parameter length. The smooth nature of the plots of Figs. 3(a)-3(c) demonstrates the predictable nature of SVD-Index and thus larger ratios should be possible for cases in which more input d-spacings are available or when larger volumes are being searched.

3.3. Removing the first- and second-highest d-spacings - triclinic lattices

Instead of keeping the two highest d-spacings from test input lattices, as defined in Table 4, a further analysis was performed with the removal of the highest d-spacing and with a further one in three of the rest randomly removed. For 400 sets of triclinic d-spacings, SVD-Index found the correct solution 100% of the time with the average number of calls to the process of Table 1 being 404. Removing the second-highest d-spacing and keeping the first yielded 156 as the average number of calls to the process of Table 1. In both analyses, up to three d-spacings are removed from the first six d-spacings. Removing the third-highest d-spacing and keeping the first two as described in Table 4 yields 105 as the average number of calls to the process of Table 1. Thus, the trend seen in the three sets of analyses shows that as higher d-spacings are removed, SVD-Index requires more computational effort in order to index the test input lattices successfully. Even though the present analyses produced a 100% success rate, the control parameters of Table 3 were chosen with the d-spacing removal scheme of Table 4 in mind.

3.4. Comparisons with ITO and TREOR90

For the case of Cu K radiation, 200 test input sets of d-spacings were used as input for ITO and TREOR90 for each of four different volume ranges. d-spacing errors and a zero error were not included. In the following analysis, a d-spacing less than 0.05° (2) from the previously accepted larger d-spacing was removed; no other d-spacings were removed.

ITO (Ito, 1949), last updated in 1998 and written by Visser, a description of the method being given in the paper by Visser (1969), was first tested against triclinic lattices. ITO considers calculated d-spacings to be equal if they differ by an amount corresponding to less than 0.005° (2). The chances of ITO finding a solution were increased by executing ITO six times for each test input lattice with various sets of control parameters. These include NQ1 and NQ2 for the numbers of lines used in combinations for finding zones. For the default values of NQ1 = 3 and NQ2 = 6, two separate runs were performed with tolerances for matching calculated and observed 2 values set to 0.001 and 0.006° (2). Two further sets of NQ1 and NQ2 values were used, with NQ1 = 4 and NQ2 = 8, and NQ1 = 2 and NQ2 = 9, with the two previously stated 2 tolerances used in each case. Because ITO considers d-spacings to be equal if they differ by an amount corresponding to less than 0.005° (2), it has difficulty, regardless of 2 errors, with large volumes where many calculated 2 values differ by small amounts (Werner, 1976). In these cases, ITO outputs a message and stops processing. The present analysis detects this condition, resulting in two sets of results: one with these lattices included in the comparison and one where they are excluded. Fig. 4 line (a) shows percentage success rates of ITO finding the volume of the test input triclinic lattices to within ±1 Å for the case of all test input lattices included; as expected, the success rate decreases markedly at high volumes. Excluding the cases where the equivalence of d-spacings that differ by less than 0.005° (2) causes problems, produced the results shown as line (b); here it is seen that ITO has an approximate 90% success rate below 2000 Å³ and decreases to 75% for volumes up to 4000 Å³. The downward trend seen in the ITO results of line (b) is probably due to the fact that as the volume increases the probability of a short axis relative to the others is greater. This difficulty in dealing with extreme geometries in also witnessed in Fig. 3 for SVD-Index. ITO yielded a 77% success rate for test input monoclinic lattice with volumes between 1000 and 2000 Å³.

Figure 4 Percentage success rates for finding the volume of test input lattices for (a) ITO with of all test triclinic input lattices included, (b) excluding the cases where the equivalence of dc,hkl is encountered and for (c) TREOR90 in solving monoclinic test input lattices.

TREOR90 was tested against monoclinic lattices to within 1% of the test input volumes; the space groups for the monoclinic lattices were randomly chosen. Triclinic lattices were not considered because of long calculation times. Test input d-spacings that had hkl values larger than the maximum default values set for the monoclinic base lines were rejected. This in fact removes difficult test input lattices where one lattice parameter is relatively short. Increasing the maximum hkl values for the monoclinic base lines significantly increases calculation times and thus was not attempted. The TREOR90 commands `MONOSET = 7' and `SHORT = 1' were used (see TREOR90 manual for details) in order to enhance the chances of finding the correct solution. If the correct solution was not found, then the two commands `D1 = 0.0003' and `D2 = 0.0005' were included and TREOR was again run. In some cases TREOR90 indexed the test input lattices as primitive with volumes that were smaller that the test input lattice. Similarly, volumes were sometimes integral multiples of the test input lattices. Both of these cases were identified as a correct solution. Fig. 4 line (c) shows the TREOR90 percentage success rates of finding the correct solution.

3.5. Comparison with DICVOL91

The comparison performed with DICVOL91 on test triclinic lattices was limited in scope because of long calculation times. Limiting the volume range of the test input lattices to 1000 Å³, and similarly setting the volume range searched by DICVOL91 to this value, 50 sets of 20 d-spacings without random d-spacing errors or a zero error were given to DICVOL91 to solve, with a resulting success rate of 84%.

A further test using monoclinic lattices proved DICVOL91 to be 100% successful. DICVOL91 was also 100% successful with d-spacing errors of 2 = 0.01° (2); of course the DICVOL 2 errors were set to 0.01° (2). Setting the DICVOL91 2 errors to values less that the introduced errors resulted in failure.

The test input d-spacings given to the ITO, TREOR90 and DICVOL1 programs were all successfully solved by SVD-Index.

4.1. Inclusion of d-spacing errors and a zero error

For uniform deviate random errors of 2 = ±0.005, ±0.01 and ±0.03° (2) and with a zero error of 0.03° (2), and with the d-spacing removal scheme of Table 4, sets of test input d-spacings were generated for triclinic, monoclinic and orthorhombic lattices, with corresponding errors included, and were given to the SVD-Index algorithm of Table 2 to solve. A 100% success rate in finding the correct solution was observed for 1000 sets of d-spacings for each of the crystal systems for all cases of 2. The average number of times Table 1 was called before the correct solution was found increased with increasing 2; in the triclinic case, the average increased from 125 at 2 = ±0.01 to 211 at 2 = ±0.03. Increasing 2 to the very large value of ±0.5° (2) for 300 triclinic test input lattices produced a success rate of 92% with the average number of times of calling Table 1 being 1070. The other 8% (24 test input lattices), if at all solvable, require a larger N₁ value. Even though the success rate at 2 = ±0.5° is still high, the difficulty with such bad data becomes one of choosing which solution out of many is the correct solution. It is worth noting that careful peak fitting using the fundamental-parameters approach to X-ray line profile analysis (Cheary & Coelho, 1992) on moderately good data typically results in d-spacing errors in the range ±0.0025 to ±0.005° (2); misplaced peaks due to peak overlap, however, can lead to larger errors.

The average number of times of calling Table 1 for the case of 2 = ±0.005° was, for the triclinic case, 125, which is not much different from the no-zero-error and no-noise case (average 105 calls to Table 1). This indicates that, in the absence of d-spacing errors, a zero error of the magnitude of 0.03° (2) does not significantly increase the computational effort nor hinder SVD-Index in finding the correct solution. In the absence of a zero error and with d-spacing errors of 2 = ±0.03°, the average number of times of calling Table 1 before finding the correct solution becomes 255. Thus d-spacing errors at this level are the dominant factor when solving the test input lattices with a zero error of 0.03° (2).

4.2. Finding all possible solutions - triclinic lattices

For a typical zero error and typical errors in d-spacings, the SVD-Index algorithm has shown that it is capable of finding a particular solution, namely the one matching the test input lattice with allowances made for d-spacing errors. Because of this the SVD-Index algorithm should in principle be capable of finding all solutions within the boundary of an upper limiting volume. This limiting volume is implicit in the constraint of step (iv) part (c) of Table 2.

Fig. 5 shows M₁₅ values obtained during the execution of the SVD-Index algorithm as a function of volume at the calculated M₁₅ values for three randomly chosen triclinic lattices with volumes as indicated. The lattice of Fig. 5(a) has random errors in the d-spacings of magnitude 2 = ±0.003° (2) and, as can be seen, the solution is well defined at the input volume of 2000 Å³. Fig. 5(b) contains random errors in the d-spacings of magnitude 2 = ±0.03° (2) and, even though the input test lattice has the same volume as for Fig. 5(b), it is seen that there are other solutions with better M₁₅ values at volumes around 2200 Å³. These plots show the importance of obtaining precise d-spacings.

Figure 5 SVD-Index M15 results versus volume for an arbitrarily chosen test input triclinic lattice for random d-spacing errors of (a) 2 = ±0.003° (2) and (b) 2 = ±0.03° (2).

A more systematic investigation into the number of solutions possible versus d-spacing errors was performed on randomly chosen triclinic lattices with volumes ranging from 3000 to 4000 Å³. For 2 = ±0.03° (2) the solution with the best M₁₅ value was similar to the input test lattice 94% of the time; this is particularly high considering the limited number of input lines. A corresponding success rate for 2 = ±0.1° (2) was 45%. Thus, the conclusion reached is similar to that reported by Visser (1969) in that d-spacing errors need to be less than 0.03° (2).

4.3. Higher symmetry lattices - tetragonal to cubic

1000 test input lattices were generated for each of the tetragonal, trigonal/hexagonal and cubic crystal systems with space groups randomly selected from their respective crystal systems. Ten d-spacings were generated from these test input lattices and d-spacing errors of 2 = ±0.03° and a zero error of 0.03° were incorporated; the d-spacing removal scheme of Table 4 was applied. Corresponding Bravais lattices of minimum symmetry were then used by SVD-Index to solve for the sets of d-spacings, resulting in a 100% success rate. In the process, the average number of times that Table 1 was called before finding the correct test input lattice was 26.1, 8.3 and 1.3 for the tetragonal, trigonal/hexagonal and cubic crystal systems, respectively. The maximum number of calls to Table 1 was 447, 169 and 15, respectively. This analysis highlights the far simpler nature of these crystal systems.

4.4. Impurity line analysis

Impurity lines were randomly added to test input triclinic, monoclinic and orthorhombic lattices; d-spacing were generated for each test input lattice with a random error of ±0.005° (2) and a zero error of 0.01° (2); the d-spacing removal scheme of Table 4 was employed. d-spacings of the impurity lines were randomly chosen between the smallest d-spacing and 1.5 times the largest. This allows for impurity lines that are at lower 2 angles than the lines of the test input lattice. I_o of equation (4) for the test input d-spacings were set to 1; I_o for the impurity lines were set to 0.2, hence simulating impurity peaks at 20% intensity. Table 6 shows SVD-Index success rates in solving the test input lattices as a function of the number of impurity lines included, N_impurity. High success rates are seen for three impurity lines for the three crystal systems. Also seen is the expected lower success rate for the triclinic system. These results demonstrate the ability of SVD-Index to deal with moderate amounts of impurity peaks.

4.5. Real data analysis

SVD-Index successfully indexed the examples shown in Table 7; data and lattice parameters for these examples are available as supplementary material.¹ The correct solutions were all ranked as the best. Removing a number of highest d-spacings, N_R of Table 7, and rerunning SVD-Index also produced the correct solutions ranked as the best. In the running of SVD-Index, no limits were entered for the lattice-parameter lengths or cell volume.

Table 7 Examples and references N is the number of observed d-spacings. NR is the number of highest d-spacings removed whilst still being able to index successfully with SVD-Index. R is the ratio of the largest to the smallest lattice-parameter length. Example Reference Vol. (Å3) N NR R (1) Tetragonal# Morris et al. (1980, p. 77) (Sr2Cr2O7) 1187 25 9 1.17 (2) Rhombohedral Von Dreele et al. (2000) (data obtained from CCP14; http://gserv1.dl.ac.uk/CCP/CCP14/index.html ) 420727 41 12 1.11 (3) Orthorhombic# Morris et al. (1980, p. 7) (NH4B5O8.4H2O) 1154 25 13 1.23 (4) Monoclinic# Morris et al. (1980, p. 9) [(NH4)2Ni(SO4)2.6H2O] 684 25 10 2.00 (5) Monoclinic# Morris et al. (1980, p. 11) [(NH4)2S2O3] 583 25 2 1.57 (6) Monoclinic+ Swanson et al. (1963) (CdWO4) 149 20 2 1.16 (7) Monoclinic Toraya & Yamazaki (2002) (Ca2SiO4) 785 25 4 1.19 (8) Triclinic# Morris et al. (1980, p. 64) (K2S2O8) 182 25 2 1.37 (9) Triclinic# Morris et al. (1979) 984 25 2 2.52 (10) Triclinic Dinnebier et al. (2002) [Ge(SnMe3)4] 1229 25 1 1.59 (11) Triclinic van Langevelde et al. (2001) (-1,2,3-tri-tetradecanoyl-glycerol 2314 25 2 7.64 (12) Triclinic van Langevelde et al. (2001) (-1,2,3-tri-octadecanoyl-glycerol) 2879 25 0 9.53 #Distributed with TREOR90. +Distributed with DICVOL91.

Example (7) contains six non-trivial impurity peaks; two of them situated at the third- and sixth-highest d-spacing; the highest d-spacing of the main phase also has an intensity near zero and is therefore not observed. In spite of these difficulties, SVD-Index was successful in indexing; this included the case in which the first four peaks were removed. It is worth noting that the existence of impurity phases and their corresponding peak positions are often known. However, for the sake of testing SVD-Index, all observed peaks have been included in the analysis.

Example (10) remained solvable if the highest d-spacing only was removed. Inspection reveals three impurity lines with non-trivial intensities, situated at the third-, fifth- and seventeenth-highest d-spacings.

Example (12) is the most difficult. On removal of the highest d-spacing, N_R = 1, SVD-Index only found the correct solution after running the program three times. The ratio of the largest to the smallest lattice parameter, R, is high and this results in a dominant zone with the highest 30 calculated d-spacings being of type hk0; correspondingly the highest 14 extracted d-spacings are of type hk0. The first peak (010) is also not present in the diffraction pattern and the number of calculated peaks within the reciprocal sphere containing the first 25 observed lines is 51. On inspection of the calculated and observed diffraction patterns it is possible to discern a further three peaks but they are of small intensity and would not normally be included. The M₂₅ versus volume plot of Fig. 6(a) highlights the fact that the solution is not well defined. Visual inspection of the diffraction pattern shows well resolved peaks up to the 40th observed peak. With this number of peaks SVD-Index produces the results shown in Fig. 6(b); here the correct solution is better resolved than in the M₂₅ case.

Figure 6 (a) SVD-Index M25 and (b) M40 results versus volume for example (13).