Niggli reduction#

This page describe the algorithm implemented in the wulfric.cell.niggli(). An implementation directly follows the papers [1], [2]. If you use results obtain with this function of wulfric, please acknowledge those papers as the original source of the algorithm.

For an alternative implementation, that was available long before wulfric and is not associated with wulfric package or its authors see Niggli-cell.

The algorithm is given a cell \(\boldsymbol{A}\), that is properly defined in Basic notation.

Niggli reduction algorithm is implemented and tested exactly as in [1]. On this page we recall the algorithm itself and the testing procedure with the notation of wulfric. We advise you to read the original papers for better understanding of it. Parameters

\[\begin{split}A & = a^2 \\ B & = b^2 \\ C & = c^2 \\ \xi & = 2bc \cos(\alpha) \\ \eta & = 2ac \cos(\beta) \\ \zeta & = 2ab \cos(\gamma)\end{split}\]

are derived from standard cell parameters \(a,b,c,\alpha,\beta,\gamma\) and organized in a metric matrix as

\[\begin{split}\boldsymbol{G} = \boldsymbol{A} \boldsymbol{A}^T = \begin{pmatrix} A & \zeta/2 & \eta/2 \\ \zeta/2 & B & \xi/2 \\ \eta/2 & \xi/2 & C \\ \end{pmatrix}\end{split}\]

which is transformed by the transformation matrix as

\[\boldsymbol{\tilde{G}} = \boldsymbol{P}^T \boldsymbol{G} \boldsymbol{P}\]

Algorithm#

Steps of an algorithm from the paper [1] with the transformation matrices from the paper [2].

Each step of the algorithm transforms the metric matrix if the condition is met. If the algorithm generates \(N\) trtansformations with the transformation matrices \(\boldsymbol{P}_1, ..., \boldsymbol{P}_N\), then the full transformation matrix is \(\boldsymbol{P} = \boldsymbol{P}_1 \cdot ... \cdot \boldsymbol{P}_N\).

Step 1#

If \(A > B\) or (\(A = B\) and \(|\xi| > |\eta|\)), then swap \((A, \xi) \leftrightarrow (B,\eta)\).

\[\begin{split}\boldsymbol{P} = \begin{pmatrix} 0 & -1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & -1 \\ \end{pmatrix}\end{split}\]

Step 2#

If \(B > C\) or (\(B = C\) and \(|\eta| > |\zeta|\)), then swap \((B, \eta) \leftrightarrow (C,\zeta)\)

\[\begin{split}\boldsymbol{P} = \begin{pmatrix} -1 & 0 & 0 \\ 0 & 0 & -1 \\ 0 & -1 & 0 \\ \end{pmatrix}\end{split}\]

and go to step 1.

Step 3#

If \(\xi \eta \zeta > 0\), then put \((|\xi|, |\eta|, |\zeta|) \rightarrow (\xi, \eta, \zeta)\).

Note: in the original publication [1] there was a typo: \(\xi \eta \xi > 0\) instead of \(\xi \eta \zeta > 0\).

\[\begin{split}\boldsymbol{P} = \begin{pmatrix} i & 0 & 0 \\ 0 & j & 0 \\ 0 & 0 & k \\ \end{pmatrix}\end{split}\]

where

  • \(i = 1\) if \(\xi > 0\), otherwise \(i = -1\).

  • \(j = 1\) if \(\eta > 0\), otherwise \(j = -1\).

  • \(k = 1\) if \(\zeta > 0\), otherwise \(k = -1\).

Step 4#

If \(\xi \eta \zeta \leq 0\), then put \((-|\xi|, -|\eta|, -|\zeta|) \rightarrow (\xi, \eta, \zeta)\).

\[\begin{split}\boldsymbol{P} = \begin{pmatrix} i & 0 & 0 \\ 0 & j & 0 \\ 0 & 0 & k \\ \end{pmatrix}\end{split}\]

where \(i,j,k\) are defined via an algorithm:

  • Step 1

    Set \(i = 1\), \(j = 1\), \(k = 1\)

  • Step 2

    If \(\xi > 0\), then \(i = -1\) else if not \(\xi < 0\), set \(p \rightarrow i\).

    Note: in the original publication [2] there was a typo: \(\zeta\) instead of \(\xi\).

  • Step 3

    If \(\eta > 0\), then \(j = -1\) else if not \(\eta < 0\), set \(p \rightarrow j\).

  • Step 4

    If \(\zeta > 0\), then \(k = -1\) else if not \(\zeta < 0\), set \(p \rightarrow k\).

  • Step 5

    If \(i \cdot j \cdot k < 0\) and \(p \rightarrow i\), then \(i = -1\).

    If \(i \cdot j \cdot k < 0\) and \(p \rightarrow j\), then \(j = -1\).

    If \(i \cdot j \cdot k < 0\) and \(p \rightarrow k\), then \(k = -1\)

Below we include a diagram that might help to comprehend how this algorithm works (click to enlarge).

Application of transformation matrix to the metric tensor have the general form:

\[\begin{split}\boldsymbol{P}^T \boldsymbol{G} \boldsymbol{P} = \begin{pmatrix} i^2 A & ij \zeta/2 & ik \eta/2 \\ ji \zeta/2 & j^2 B & jk \xi/2 \\ ki \eta/2 & kj \xi/2 & j^2 C \\ \end{pmatrix}\end{split}\]
../../_images/niggli-step-4.png

Step 5#

If \(|\xi| > B\) or (\(\xi = B\) and \(2\eta < \zeta\)) or (\(\xi = -B\) and \(\zeta < 0\)), then set

\[\begin{split}C & = B + C - \xi \,\text{sign}(\xi) \\ \eta & = \eta - \zeta \,\text{sign}(\xi) \\ \xi & = \xi - 2B \,\text{sign}(\xi)\end{split}\]
\[\begin{split}\boldsymbol{P} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & -\text{sign}(\xi) \\ 0 & 0 & 1 \\ \end{pmatrix}\end{split}\]

and go to step 1.

Step 6#

If \(|\eta| > A\) or (\(\eta = A\) and \(2\xi < \zeta\)) or (\(\eta = -A\) and \(\zeta < 0\)), then set

\[\begin{split}C & = A + C - \eta \,\text{sign}(\eta) \\ \xi & = \xi - \zeta \,\text{sign}(\eta) \\ \eta & = \eta - 2A \,\text{sign}(\eta)\end{split}\]
\[\begin{split}\boldsymbol{P} = \begin{pmatrix} 1 & 0 & -\text{sign}(\eta) \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix}\end{split}\]

and go to step 1.

Step 7#

If \(|\zeta| > A\) or (\(\zeta = A\) and \(2\xi < \eta\)) or (\(\zeta = -A\) and \(\eta < 0\)), then set

\[\begin{split}B & = A + B - \zeta \,\text{sign}(\zeta) \\ \xi & = \xi - \eta \,\text{sign}(\zeta) \\ \zeta & = \zeta - 2A \,\text{sign}(\zeta)\end{split}\]
\[\begin{split}\boldsymbol{P} = \begin{pmatrix} 1 & -\text{sign}(\zeta) & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{pmatrix}\end{split}\]

and go to step 1.

Step 8#

If \(\xi + \eta + \zeta + A + B < 0\) or (\(\xi + \eta + \zeta + A + B = 0\) and \(2(A + \eta) + \zeta > 0\)), then set

\[\begin{split}C & = A + B + C + \xi + \eta + \zeta \\ \xi & = 2B + \xi + \zeta \\ \eta & = 2A + \eta + \zeta\end{split}\]
\[\begin{split}\boldsymbol{P} = \begin{pmatrix} 1 & 0 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \\ \end{pmatrix}\end{split}\]

and go to step 1.

Testing procedure#

TODO

References#