# Niggli reduce cell of 2D and 3D lattice

## Code

https://github.com/unkcpz/pniggli

## Introduction

Correct identification of the Bravais lattice of a crystal is an important early step in structure solution. Niggli reduction is a commonly used technique.

Examples in two dimensional lattice. An infinite variety of unit cells, vastly different in appearance and specification, can generate the same mathematical lattice.

## Algorithm to determin Niggli cell(2D)

The following variables used in this algorithm are initialized for step A1-A4.

Define following variables as:

$$A=\bf{a\cdot a}$$ $$B=\bf{b\cdot b}$$ $$Y = \gamma = 2\bf{a\cdot b}$$

They are elements of metric tensor of $G$: $$G=\begin{pmatrix} A & \gamma/2 \\ \gamma/2 & B \\ \end{pmatrix}$$

$M$ represent the transformation matrix that is applied to basis vectors. The lattice vectors is represented as row vectors: $$L= \begin{pmatrix} \bf{a} \\ \bf{b} \end{pmatrix} = \begin{pmatrix} a_x & a_y \\ b_x & b_y \end{pmatrix}$$

$M$ operated as left transformation matrix to lattice vector $L$: $$\mathrm{new}\quad L = M \cdot L$$ that is, $$\begin{pmatrix} \bf{a'} \\ \bf{b'} \end{pmatrix} = M_{2\times 2} \cdot \begin{pmatrix} \bf{a} \\ \bf{b} \end{pmatrix}$$

### Step 1

Ensure that basis length, $|\bf{a}| < |\bf{b}|$ that is $A < B$

If $A>B+eps$, let $(\bf{a'}, \bf{b'}) = (\bf{b}, \bf{a})$

$$M = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$

### Step 2

Ensure that angle between $\bf{a}$ and $\bf{b}$ is obtuse:

If $Y > 0$, let $(\bf{a'}, \bf{b'}) = (\bf{a}, \bf{-b})$

$$M = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}$$

### Step 3 and Step 4

Repeatedly overlapping basis $\bf{a}$ and $\bf{b}$ until that the angle between $\bf{a}$ and $\bf{b}$ reaches fullness.

Step 3:

If $abs(Y) > A + eps$, let $(\bf{a'}, \bf{b'}) = (\bf{a}, \bf{a+b})$

$$M = \begin{pmatrix} 1 & 0 \\ -sign(Y) & 1 \end{pmatrix}$$

Step 4:

If $abs(Y) > B + eps$, let $(\bf{a'}, \bf{b'}) = (\bf{a+b}, \bf{b})$

$$M = \begin{pmatrix} 1 & -sign(Y) \\ 0 & 1 \end{pmatrix}$$

### Goto Step 1

Break the loop until A1-A4 are satisfied.

## Algorithm to determin Niggli cell(3D)

The following variables used in this algorithm are initialized for step A1-A8.

Define following variables as:

$$A=\bf{a\cdot a}$$ $$B=\bf{b\cdot b}$$ $$C=\bf{c\cdot c}$$ $$X = \xi = 2\bf{a\cdot b}$$ $$E = \eta = 2\bf{c\cdot a}$$ $$Z = \zeta = 2\bf{b\cdot c}$$

They are elements of metric tensor of $G$: $$G=\begin{pmatrix} A & \xi/2 & \eta/2 \\ \xi/2 & B & \zeta/2 \\ \eta/2 & \xi/2 & C \end{pmatrix}$$

$M$ represent the transformation matrix that is applied to basis vectors. The lattice vectors is represented as row vectors: $$L= \begin{pmatrix} \bf{a} \\ \bf{b} \\ \bf{c} \end{pmatrix} = \begin{pmatrix} a_x & a_y & a_z \\ b_x & b_y & b_z \\ c_x & c_y & c_z \end{pmatrix}$$

$M$ operated as left transformation matrix to lattice vector $L$: $$\mathrm{new}\quad L = M \cdot L$$ that is, $$\begin{pmatrix} \bf{a'} \\ \bf{b'} \\ \bf{c'} \end{pmatrix} = M_{3\times 3} \cdot \begin{pmatrix} \bf{a} \\ \bf{b} \\ \bf{c} \end{pmatrix}$$

### Step 1 and Step 2

Specification of the basis length sorting and basis angle sorting in G. Ensure that basis length, $|\bf{a}| < |\bf{b}| < |\bf{c}|$ that is

1. Ensure that basis length, $|\bf{a}| < |\bf{b}| < |\bf{c}|$, $A < B < C$,
2. and $abs(X) < abs(E) < abs(Z)$

If A > B + eps or (abs(A - B) < eps and abs(X) > abs(E) + eps) :

$$M = \begin{pmatrix} 0 & -1 & 0 \\ -1 & 0 & 0 \\ 0 & 0 & -1 \end{pmatrix}$$

### Step 3 and step 4

Ensure that angle between $\bf{a}$ and $\bf{b}$ and $\bf{c}$ is obtuse:

$l, m, n$ represent angle type of $\xi, \eta, \zeta$.

• 1 for acute,
• -1 for obtuse
• and 0 for right respectively.

Step 3:

if $lmn=1$:

$$M = \begin{pmatrix} l & 0 & 0 \\ 0 & n & 0 \\ 0 & 0 & m \end{pmatrix}$$

Step 4:

Reference http://atztogo.github.io/niggli/#a4

If $l=-1, m=-1, n=-1$, do nothing.

If $lmn=0$ or $lmn=-1$:

Set $i=j=k=1$. $r$ is used as a reference to $i, j, \mathrm{or} k$, and is initially undefined.

• $i=-1$ if $l=1$
• $r\rightarrow i$ if $i=0$
• $j=-1$ if $m=1$
• $r\rightarrow j$ if $j=0$
• $k=-1$ if $n=1$
• $r\rightarrow k$ if $k=0$

if $ijk=-1$:

• $i, j, k$ refered by $r$ is set to -1.

$$M = \begin{pmatrix} i & 0 & 0 \\ 0 & j & 0 \\ 0 & 0 & k \end{pmatrix}$$

### Step 5, 6 and 7

Repeatedly overlapping basis $\bf{a}$ and $\bf{b}$ until that the angle between $\bf{a}$ and $\bf{b}$ reaches fullness.

Step 5:

if (
abs(X) > B + eps
or (abs(X - B) < eps and 2 * E < Z - eps)
or (abs(X + B) < eps and Z < -eps)
):


$$M = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -sign(X) & 1 \end{pmatrix}$$

Step 6:

if (
abs(E) > A + eps
or (abs(A - E) < eps and 2 * X < Z - eps)
or (abs(A + E) < eps and Z < -eps)
):


$$M = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -sign(E) & 0 & 1 \end{pmatrix}$$

Step 7

if ( abs(X) > B + eps
or (abs(X - B) < eps and 2 * E < Z - eps)
or (abs(X + B) < eps and Z < -eps)
):


$$M = \begin{pmatrix} 1 & 0 & 0 \\ -sign(Z) & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$

### Step 8

Get the basis metric element $C$ use $A$ and $B$.

If $\xi+\eta+\zeta+A+B<-\varepsilon$ or $abs(\xi+\eta+\zeta+A+B)<\varepsilon<\zeta+2(A+\eta)$

$$M = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 1 & 1 \end{pmatrix}$$

### Goto Step 1

Break the loop until A1-A4 are satisfied.

## Reference

1. A Unified Algorithm for Determining the Reduced (Niggli) Cell, I. Krivý and B. Gruber, Acta Cryst., A32, 297-298 (1976)
2. The Relationship between Reduced Cells in a General Bravais lattice, B. Gruber, Acta Cryst., A29, 433-440 (1973)
3. Numerically stable algorithms for the computation of reduced unit cells, R. W. Grosse-Kunstleve, N. K. Sauter and P. D. Adams, Acta Cryst., A60, 1-6 (2004)
4. The geometry of Niggli reduction: BGAOL – embedding Niggli reduction and analysis of boundaries. Erratum . Journal of Applied Crystallography, 47(4), 1477–1477. Andrews, L. C., & Bernstein, H. J. (2014).
5. Selling reduction versus Niggli reduction for crystallographic lattices. Acta Crystallographica Section A: Foundations and Advances, 75(1), 115–120. Andrews, L. C., Bernstein, H. J., & Sauter, N. K. (2019).
6. https://nvlpubs.nist.gov/nistpubs/sp958-lide/188-190.pdf 