betaFeedback

WorksComputer Science

Lattice reduction by cubification

Abstract

Lattice reduction is a NP-hard problem well known in computer science and cryptography. The Lenstra-Lenstra-Lovasz (LLL) algorithm based on the calculation of orthogonal Gram-Schmidt (GS) bases is efficient and gives a good solution in polynomial time. Here, we present a new approach called cubification that does not require the calculation of the GS bases. It relies on complementary directional and hyperplanar reductions. The deviation from cubicity at each step of the reduction process is evaluated by a parameter called lattice rhombicity, which is simply the sum of the absolute values of the metric tensor. Cubification seems to equal LLL; it even outperforms it in the reduction of columnar matrices. We wrote a Python program that is ten times faster than a reference Python LLL code. This work may open new perspectives for lattice reduction and may have implications and applications beyond crystallography.

Synopsis An algorithm of lattice reduction based directional and hyperplanar projections and driven by the reduction of the lattice rhombicity is proposed. It may have an impact beyond crystallography.

Introduction

In computer science, digital communication and cryptography, lattice problems form a class of intricate NP-hard (non-deterministic polynomial-time) optimization problems, such as the shortest vector problem, the closest vector problem, and the shortest basis problem. Solving one of them would help to solve the others. Lattice reduction algorithms aim at solving the last problem. Given a lattice L\mathcal{L} made of NN free vectors bi\mathbf{b}_i, the algorithm should give new relatively short, nearly orthogonal vectors bi′\mathbf{b}'_i of the same lattice L\mathcal{L}. It consists in finding integers zijz_{ij} such that bi=∑j=1Nzijbj′\mathbf{b}_i = \sum_{j=1}^{N} z_{ij}\mathbf{b}'_j and L={Z bi}={Z bj′}\mathcal{L} = \{\mathbb{Z}\,\mathbf{b}_i\} = \{\mathbb{Z}\,\mathbf{b}'_j\}, where the {Z ⋅}\{\mathbb{Z}\,\cdot\} means all the linear combinations with integer coefficients. The number of vectors cannot be larger the space dimension; often, both are the same. The set of vectors are linked by an integer matrix Z\mathbf{Z} of determinant ±1\pm1. This relation can be written

[b1⋮bi⋮bN]=Z[b1′⋮bj′⋮bN′]\begin{bmatrix} \mathbf{b}_1\\ \vdots\\ \mathbf{b}_i\\ \vdots\\ \mathbf{b}_N \end{bmatrix} = \mathbf{Z} \begin{bmatrix} \mathbf{b}'_1\\ \vdots\\ \mathbf{b}'_j\\ \vdots\\ \mathbf{b}'_N \end{bmatrix}

with Z∈ZN.N\mathbf{Z} \in\mathbb{Z}^{N.N} and Det(Z)=±1Det(\mathbf{Z}) = \pm1, where bi\mathbf{b}_i and bj′\mathbf{b}'_j refer to the vectors themselves, not to their coordinates.

The most popular algorithm to tackle the lattice reduction problem was proposed nearly forty years ago by Lenstra-Lenstra-Lovász (1982) and is still considered as the main reference in the domain. It is so important that a complete book was devoted to it [7]. The reader can also consult [9]. We just give here some key points. One is the Gram-Schmidt orthogonalization routine in which one associates to any basis {b1,…,bk,…,bm}\{\mathbf{b}_1, \ldots, \mathbf{b}_k, \ldots, \mathbf{b}_m\}, m≤Nm \leq N, an orthogonal basis {b1∗,…,bk∗,…,bm∗}\{\mathbf{b}_1^*, \ldots, \mathbf{b}_k^*, \ldots, \mathbf{b}_m^*\} by a series of projections bk∗=bk−∑i<kui,kbi\mathbf{b}_k^* = \mathbf{b}_k - \sum_{i<k} u_{i,k}\mathbf{b}_i with ui,k=bk⋅bi∗bi∗⋅bi∗u_{i,k} = \frac{\mathbf{b}_k\cdot\mathbf{b}_i^*}{\mathbf{b}_i^*\cdot\mathbf{b}_i^*}. The vectors bk∗\mathbf{b}_k^* are not anymore integer (“reticular” in crystallographic language); they remain however rational. The LLL algorithm works in two steps repeated iteratively. The first step is the quasi orthogonalization using values of the coefficients ui,ku_{i,k}. The vectors bi\mathbf{b}_i are replaced by bi−⌊ui,k⌉bk\mathbf{b}_i - \lfloor u_{i,k}\rceil\mathbf{b}_k, for kk between 1 and i−1i - 1, where ⌊ui,k⌉\lfloor u_{i,k}\rceil means the nearest integer of ui,ku_{i,k}. The Gram-Schmidt basis should be actualized during the process. The second step relies on a criterion to determine whether or not the vectors bi\mathbf{b}_i and bi∗\mathbf{b}_i^* should be swapped: the swap is made when

∥bi+1∗+ui,i+1bi∗∥2<α∥bi∗∥2\left\lVert\mathbf{b}_{i+1}^* + u_{i,i+1}\mathbf{b}_i^* \right\rVert^2 < \alpha\lVert\mathbf{b}_i^* \rVert^2

where α\alpha is a constant arbitrarily chosen between ¼ and 1 and fixed once for all. Often, the value α=34\alpha= \frac{3}{4} is chosen. It is usual in lattice reduction problem to present the vectors as rows to form a matrix. In crystallography, we generally write the coordinates in columns and keep the row notation for planes, i.e. for vectors of the reciprocal space. In order to avoid any confusion, we will write bt\mathbf{b}^{\mathrm{t}} a vector b\mathbf{b} written in row, where “t” means “transpose”. In a space of dimension NN, a vector b\mathbf{b} is a N×1N \times1 matrix, and bt\mathbf{b}^{\mathrm{t}} a 1×N1 \times N matrix. In this paper, the scalar product of two vectors p\mathbf{p} and u\mathbf{u} is noted equivalently p⋅u=ptu\mathbf{p}\cdot\mathbf{u} = \mathbf{p}^{\mathrm{t}}\mathbf{u}, but the last notation will be preferred in order to keep the distinction between row and column vectors, between reciprocal and direct space vectors.

A typical low dimensional example of lattice reduction is the set of three vectors in 3 dimensions, b1t=[1,1,1]\mathbf{b}_1^{\mathrm{t}} = [1,1,1], b2t=[−1,0,2]\mathbf{b}_2^{\mathrm{t}} = [-1,0,2], and b3t=[3,5,6]\mathbf{b}_3^{\mathrm{t}} = [3,5,6]. They form the matrix B=[111−102356]\mathbf{B} = \begin{bmatrix} 1 & 1 & 1 \\ -1 & 0 & 2 \\ 3 & 5 & 6 \end{bmatrix}. The reduced lattice is the matrix B′=[010101−102]\mathbf{B}' = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ -1 & 0 & 2 \end{bmatrix}. One can check that b1=b1′+b2′\mathbf{b}_1 = \mathbf{b}'_1 + \mathbf{b}'_2, b2=b3′\mathbf{b}_2 = \mathbf{b}'_3, and b3=5b1′+4b2′+b3′\mathbf{b}_3 = 5\mathbf{b}'_1 + 4\mathbf{b}'_2 + \mathbf{b}'_3. The “t” is not indicated because these linear equations can written equivalently in rows or columns. The integer coefficients of linearity could be found by calculating

Z=B(B′)−1.\mathbf{Z} = \mathbf{B}(\mathbf{B}')^{-1}.

I came to be interested in lattice reduction by a crystallographic study [5] in which a method is proposed to determine a unit cell attached to a hyperplane of dimension N−1N-1 given by a vector of the reciprocal lattice pt\mathbf{p}^{\mathsf{t}}. The unit cell is made of N−1N-1 vectors {b2,…,bi,…,bN}\{\mathbf{b}_2,\ldots,\mathbf{b}_i,\ldots,\mathbf{b}_N\} inside the plane, i.e. such that ptbi=0\mathbf{p}^{\mathsf{t}}\mathbf{b}_i=0, and one vector b1\mathbf{b}_1 in the first layer, i.e. such that ptb1=1\mathbf{p}^{\mathsf{t}}\mathbf{b}_1=1. The initial result obtained in (Cayron, 2021) was not yet fully satisfying because the vectors {b1,…,bi,…,bN}\{\mathbf{b}_1,\ldots,\mathbf{b}_i,\ldots,\mathbf{b}_N\} forming the unit cell were not yet reduced, i.e. other unit cells of same volume based on smaller vectors {b1′,…,bi′,…,bN′}\{\mathbf{b}'_1,\ldots,\mathbf{b}'_i,\ldots,\mathbf{b}'_N\} were clearly possible for the same hyperplane. How to determine them?

This question made us realize that lattice reduction is not as simple as one could think and that LLL could be a good option. However, despite its highly recognized and well-establish status in computer science, some points of the LLL algorithm may seem strange for a crystallographer. First, the calculations in LLL use GS orthogonalized bases, called in crystallography “structure tensors”, but we know that calculations are more effectively performed with the metric tensors

M=(b1,…,bj,…,bN)=[b12⋯b1tbj⋯b1tbN⋮⋯⋮⋯⋮bitb1⋯bitbj⋯bitbN⋮⋯⋮⋯⋮bNtb1⋯bNtbj⋯bN2]\mathcal{M}=(\mathbf{b}_1,\ldots,\mathbf{b}_j,\ldots,\mathbf{b}_N)= \begin{bmatrix} \mathbf{b}_1^{2} & \cdots& \mathbf{b}_1^{\mathsf{t}}\mathbf{b}_j & \cdots& \mathbf{b}_1^{\mathsf{t}}\mathbf{b}_N \\ \vdots& \cdots& \vdots& \cdots& \vdots\\ \mathbf{b}_i^{\mathsf{t}}\mathbf{b}_1 & \cdots& \mathbf{b}_i^{\mathsf{t}}\mathbf{b}_j & \cdots& \mathbf{b}_i^{\mathsf{t}}\mathbf{b}_N \\ \vdots& \cdots& \vdots& \cdots& \vdots\\ \mathbf{b}_N^{\mathsf{t}}\mathbf{b}_1 & \cdots& \mathbf{b}_N^{\mathsf{t}}\mathbf{b}_j & \cdots& \mathbf{b}_N^{2} \end{bmatrix}

Second, the constant α\alpha and the way it should be “arbitrarily” chosen is not explicit. It is like a strength of convergence in the algorithm; greater values lead to stronger reductions; it has an effect on the final norms of the reduced vectors, and more precisely it permits to bound the product of the squared norms ∏i=1N∥bi∥2\prod_{i=1}^{N}\lVert\mathbf{b}_i\rVert^2. This means that even if LLL uses projected vectors and orthogonalizations, the convergence criterion is mainly established on the norms, as if minimizing the norms were equivalent to orthogonalizing the basis. This assumption seems “reasonable” but has never been demonstrated, and it may be actually false. For example, the reader can look at the 20×2020\times20 matrix in Figure 1a representing the list of 20 vectors written in rows. After LLL reduction (Figure 1b) we can notice that the first coordinates (at the left) are highly occupied with ±1\pm1 whereas the last coordinates (at the right) are nearly all null, showing an unbalanced distribution of the coordinates, and thus an excess of “rhombicity”. Consequently, a more general criterion to estimate how much “small and cubic” is a basis should be introduced. There is probably not only a unique way to define it. In the present work, we propose for a basis {b1,…,bi,…,bN}\{\mathbf{b}_1,\ldots,\mathbf{b}_i,\ldots,\mathbf{b}_N\} the simple “crystallographic” parameter based on the metric tensor

Image not extracted

Figure 1. Example of the LLL algorithm with 20×2020 \times20 matrix representing a list of 20 vectors whose coordinates are written in rows. (a) Input list. (b) Output list determined with the function LatticeReduce of Mathematica. Note that the coordinates in output matrix are still unbalanced. The coordinates in columns 13 to 19 are nearly “empty”, they contain only one or two ±1\pm1, whereas the columns 1 to 12 and 20 contain more than four ±1\pm1. Before reduction, in (a), the values of the rhombicity R=∑N∥bi∥2+2∑i<j≤NbitbjR = \sum_{N}\lVert\mathbf{b}_i\rVert^2 + 2\sum_{i<j\leq N}\mathbf{b}_i^{\mathsf{t}}\mathbf{b}_j and of the sum of the squares of the norms S=∑N∥bi∥2S = \sum_{N}\lVert\mathbf{b}_i\rVert^2 are R=453988268R = 453988268, S=61580172S = 61580172. After reduction, in (b), they become R=531R = 531, S=99S = 99.

R=∑i,j∣Mij∣=∑i≤N∥bi∥2+2∑i<j≤Nbitbj(1)R=\sum_{i,j}\lvert\mathcal{M}_{ij}\rvert=\sum_{i\leq N}\lVert\mathbf{b}_i\rVert^2+2\sum_{i<j\leq N}\mathbf{b}_i^{\mathsf{t}}\mathbf{b}_j \tag*{(1)}

We will call it “lattice rhombicity”. This parameter contains the information on both the norms and the orthogonalities between the vectors. A lowest “lattice rhombicity” indicates a smaller and more cubic basis. Please note that the term “rhombicity” as a specific meaning in a branch of mathematics for symmetric second-rank tensors in three-dimensional Euclidean space, but that given in the present paper; that is why we specify “lattice rhombicity”. If one wants to evaluate only the norms, we propose to use the parameter S=∑i≤N∥bi∥2S = \sum_{i \leq N}\lVert\mathbf{b}_i\rVert^2.

Beside our work on the unit cells linked to hyperplanes [5], we thought that some of the mathematical tools used in our research on twins [4] (Cayron 2020), such as the dimension reduction by the use of left inverses could also be applied to the lattice reduction problem. This lead us to attempt a first method called “hyperplanar reduction”. The results were good but not as good as with LLL. It quickly appeared that the process would work better if the basis {b2,…,bi,…,bN}\{\mathbf{b}_2, \ldots, \mathbf{b}_i, \ldots, \mathbf{b}_N\} associated with the hyperplane could be already reduced, even if only partially. Thus, an additional process called “directional reduction” was introduced. Neither directional reduction nor hyperplanar reduction can reach the performance of the LLL algorithm, but working together, they equal and sometimes outperform it.

The principle of directional reduction will be presented in § 2. It helps to obtain a reduced lattice with significantly lower RR and SS values. They remain however higher than with LLL. The hyperplanar reduction will be explained in § 3; it continues to decrease RR and SS, and improves the cubicity. In § 4, it will be shown how cycling directional and hyperplanar reductions permits to obtain RR and SS comparable, and sometimes better than with LLL.

Directional reduction

Lagrange’s division

We consider a basis in NN dimensions made of NN integer vectors {b1,…,bi,…,bN}\{\mathbf{b}_1, \ldots, \mathbf{b}_i, \ldots, \mathbf{b}_N\} initially sorted by norms, from the lowest to the highest norms, i.e. such that ∥b1∥≤⋯≤∥bi∥≤∥bi+1∥…≤∥bN∥\lVert\mathbf{b}_1\rVert\le\cdots\le\lVert\mathbf{b}_i\rVert\le\lVert\mathbf{b}_{i+1}\rVert\ldots\le\lVert\mathbf{b}_N\rVert.

We consider two vectors bi\mathbf{b}_i and bj\mathbf{b}_j in the list such that ∥bi∥≤∥bj∥\lVert\mathbf{b}_i\rVert\le\lVert\mathbf{b}_j\rVert. The vector qbiq\mathbf{b}_i with q=bitbjbitbiq = \frac{\mathbf{b}_i^{t}\mathbf{b}_j}{\mathbf{b}_i^{t}\mathbf{b}_i} is the orthogonal projection of bj\mathbf{b}_j on bi\mathbf{b}_i. It not an integer vector but remains however a rational. It can be approximated by the integer vector ⌊q⌉bi\lfloor q \rceil\mathbf{b}_i, where ⌊q⌉\lfloor q \rceil is the integer closest to qq and computed by ⌊q⌉=int(round(q))\lfloor q \rceil= int(round(q)). If the coordinates of the vectors are such that ∣q∣≥12|q| \ge\frac{1}{2}, i.e. ⌊q⌉≠0\lfloor q \rceil\ne0, the reduced vector r=bj−⌊q⌉bi\mathbf{r} = \mathbf{b}_j - \lfloor q \rceil\mathbf{b}_i belongs to the lattice generated by bi\mathbf{b}_i and bj\mathbf{b}_j and its norm is such that ∥r∥≤∥bj∥\lVert\mathbf{r}\rVert\le\lVert\mathbf{b}_j\rVert.

In the limit case ∣q∣=12|q| = \frac{1}{2}, the triangle made by (bi,bj,r)(\mathbf{b}_i, \mathbf{b}_j, \mathbf{r}) is isosceles, i.e. ∥r∥=∥bj∥\lVert\mathbf{r}\rVert= \lVert\mathbf{b}_j\rVert. Note that in some cases, the norm of r\mathbf{r} may even be lower than that of bi\mathbf{b}_i. Two cases should be distinguished in the algorithm: if ⌊q⌉=0\lfloor q \rceil= 0, nothing changes and a next pair of vectors should be considered; if ⌊q⌉≠0\lfloor q \rceil\ne0, a change should be done, and two algorithm variants are proposed:

Variant Append: the vectors bi\mathbf{b}_i and bj\mathbf{b}_j are deleted from the list, and the vectors r\mathbf{r} and bi\mathbf{b}_i are appended at the end of the list.

Variant Insert: if ∥r∥≤∥bi∥\lVert\mathbf{r}\rVert\le\lVert\mathbf{b}_i\rVert, r\mathbf{r} replaces bi\mathbf{b}_i and bi\mathbf{b}_i replaces bj\mathbf{b}_j in the list; else, r\mathbf{r} replaces bj\mathbf{b}_j in the list.

The process is recursively repeated without sorting the list of vectors until all the values ⌊q⌉\lfloor q \rceil become null for all the pairs of vectors in the basis. The method is quite similar to Lagrange’s division described by Nguyen & Vallée [7], except that for a pair of vectors bi\mathbf{b}_i and bj\mathbf{b}_j the division is made only once and not repeated recursively.

Directional reduction

Figure 2. Directional reduction. Case where (a) ⌊q⌉=∣bitbjbitbi∣=3\lfloor q \rceil= \left\lvert\frac{\mathbf{b}_i^{\mathsf{t}}\mathbf{b}_j}{\mathbf{b}_i^{\mathsf{t}}\mathbf{b}_i} \right\rvert= 3, and (b) ⌊q⌉=1\lfloor q \rceil= 1. The orthogonal projection point is noted H and marked by a little orange star.

The variant Insert gives good results in very short time. The deviation from cubicity and the sum of the squares of the norms of the list in fig:1a that were initially R=453988268R = 453988268, S=61580172S = 61580172 are reduced down to R=540R = 540, S=134S = 134. These values are not far from those obtained with the LLL algorithm, i.e. R=531R = 531, S=99S = 99. However, as it will be discussed in § 4, the good efficiency of the variant Insert is made at the detriment of the hyperplanar reduction because of the “anisotropy” it generates. The variant Append gives better results than Insert for high dimensions, approximatively N≥15N \ge15. The values for the list in fig:1a are reduced “only” to R=1199R = 1199, S=337S = 337, but this will leave more action for the hyperplanar reduction, and better final reduction, as it will be shown in the next sections.

Simplification

Lagrange’s division reduces the vectors by pairs without considering the basis as a whole. Now, if one accepts to possibly slightly but only temporarily degrades the value of SS of the basis, the deviation from cubicity RR can be further decreased as follows. Let us consider again a list of integer vectors {b1,…,bi,…,bN}\{\mathbf{b}_1, \ldots, \mathbf{b}_i, \ldots, \mathbf{b}_N\} sorted by norms from the lowest to the highest norms. For the pairs of vectors bi\mathbf{b}_i and bj\mathbf{b}_j in the list such that ∥bi∥≤∥bj∥\lVert\mathbf{b}_i\rVert\le\lVert\mathbf{b}_j\rVert, we calculate the vector r=bj−sign⁡(bitbj)bi\mathbf{r} = \mathbf{b}_j - \operatorname{sign}(\mathbf{b}_i^{\mathsf{t}}\mathbf{b}_j)\mathbf{b}_i, where sign⁡(bitbj)=1\operatorname{sign}(\mathbf{b}_i^{\mathsf{t}}\mathbf{b}_j) = 1 if bitbj>0\mathbf{b}_i^{\mathsf{t}}\mathbf{b}_j > 0, −1-1 if bitbj<0\mathbf{b}_i^{\mathsf{t}}\mathbf{b}_j < 0, and 00 if bitbj=0\mathbf{b}_i^{\mathsf{t}}\mathbf{b}_j = 0. Then, we calculate whether or not replacing bi\mathbf{b}_i or bj\mathbf{b}_j by r\mathbf{r} allows to decrease the value of RR. If the answer the positive, the change is made, and here again, two algorithm variants are proposed

Variant “Append”: If replacing bi\mathbf{b}_i by r\mathbf{r} allows to decrease the value of RR, the vector bi\mathbf{b}_i is deleted and the vector r\mathbf{r} is appended at the end of the list. If not, the vector bj\mathbf{b}_j is deleted and the vector r\mathbf{r} is appended at the end of the list.

Variant “Insert”: If replacing bi\mathbf{b}_i by r\mathbf{r} allows to decrease the value of RR, the vector bi\mathbf{b}_i is replaced by r\mathbf{r} at the its position ii, else, bj\mathbf{b}_j is replaced by r\mathbf{r} at the its position jj. The new list of vectors is then sorted again following the increasing norms.

The variant “Insert” is chosen by default, except for random matrices for which the variant “Append” should be preferred, as it will be discussed in §4. The process of simplification is repeated recursively until RR cannot be reduced anymore. Simplification permits to decrease a little more the values obtained in §2.1 for the list of Figure 1a, i.e. from R=1199R = 1199, S=337S = 337 down to R=1084R = 1084, $S = 330 with the variant Insert. At this step, no more improvement could be obtained, even by combining Lagrange’s division and simplification. We will call “directional reduction” the result of Lagrange’s division followed by simplification.

Hyperplanar reduction

The hyperplane normal

Let us consider again a list of integer vectors {b1,…,bj,…,bN}\{\mathbf{b}_1, \ldots, \mathbf{b}_j, \ldots, \mathbf{b}_N\} initially sorted by norms, i.e. such that ∥b1∥≤⋯≤∥bi∥≤∥bi+1∥⋯≤∥bN∥\lVert\mathbf{b}_1\rVert\le\cdots\le\lVert\mathbf{b}_i\rVert\le\lVert\mathbf{b}_{i+1}\rVert\cdots\le\lVert\mathbf{b}_N\rVert. We isolate the first vector b1\mathbf{b}_1 from the subspace of dimension N−1N - 1 (hyperplane) constituted of the vectors {b2,…,bj,…,bN}\{\mathbf{b}_2, \ldots, \mathbf{b}_j, \ldots, \mathbf{b}_N\}. The coordinates of the integer vector p1\mathbf{p}_1 that is normal to this hyperplane can be calculated as follows. We write the coordinates of vectors b2,…,bj,…,bN\mathbf{b}_2, \ldots, \mathbf{b}_j, \ldots, \mathbf{b}_N in columns to form the N×N ⁣− ⁣1N \mathbin{\times} N\!-\!1 matrix

S1=[b1,2⋯b1,j⋯b1,N⋮⋯⋮⋯⋮bi,2⋯bi,j⋯bi,N⋮⋯⋮⋯⋮bN,2⋯bN,j⋯bN,N],\mathbf{S}_1 = \begin{bmatrix} b_{1,2} & \cdots& b_{1,j} & \cdots& b_{1,N} \\ \vdots& \cdots& \vdots& \cdots& \vdots\\ b_{i,2} & \cdots& b_{i,j} & \cdots& b_{i,N} \\ \vdots& \cdots& \vdots& \cdots& \vdots\\ b_{N,2} & \cdots& b_{N,j} & \cdots& b_{N,N} \end{bmatrix},

where bi,jb_{i,j} means the ithi^{\text{th}} coordinate of the vector bj\mathbf{b}_j.

If we insert as a first column any vector of the set {b2,…,bj,…,bN}\{\mathbf{b}_2, \ldots, \mathbf{b}_j, \ldots, \mathbf{b}_N\}, let us say the vector bj\mathbf{b}_j, then the new set of vectors becomes linearly dependent and the determinant of the N×NN \mathbin{\times} N matrix is null.

det⁡[b1,jb1,2⋯b1,j⋯b1,N⋮⋮⋯⋮⋯⋮bi,jbi,2⋯bi,j⋯bi,N⋮⋮⋯⋮⋯⋮bN,jbN,2⋯bN,j⋯bN,N]=0.\det\begin{bmatrix} b_{1,j} & b_{1,2} & \cdots& b_{1,j} & \cdots& b_{1,N}\\ \vdots& \vdots& \cdots& \vdots& \cdots& \vdots\\ b_{i,j} & b_{i,2} & \cdots& b_{i,j} & \cdots& b_{i,N}\\ \vdots& \vdots& \cdots& \vdots& \cdots& \vdots\\ b_{N,j} & b_{N,2} & \cdots& b_{N,j} & \cdots& b_{N,N} \end{bmatrix}=0.

Let us write this determinant by its cofactor expansion along the first column. The minors, i.e. the determinants of M1,k\mathbf{M}_{1,k}, the N−1×N−1N-1 \times N-1 submatrices of S1\mathbf{S}_1 obtained by deleting the kthk^{\mathrm{th}} row, form a vector p1=\mathbf{p}_1=

[+det⁡(M1,1)−det⁡(M1,2)⋮(−1)k+1det⁡(M1,k)⋮(−1)N+1det⁡(M1,N)]\begin{bmatrix} +\det(\mathbf{M}_{1,1})\\ -\det(\mathbf{M}_{1,2})\\ \vdots\\ (-1)^{k+1}\det(\mathbf{M}_{1,k})\\ \vdots\\ (-1)^{N+1}\det(\mathbf{M}_{1,N}) \end{bmatrix}

that checks the property p1tbj=0\mathbf{p}_1^{\mathrm{t}}\mathbf{b}_j=0, ∀j∈[2,…,N]\forall j \in[2,\ldots,N]. In other words, p1\mathbf{p}_1 is the normal to the hyperplane {b2,…,bj,…,bN}\{\mathbf{b}_2,\ldots,\mathbf{b}_j,\ldots,\mathbf{b}_N\} that we were looking for. Its norm equals the (hyper)surface formed by the vectors {b2,…,bj,…,bN}\{\mathbf{b}_2,\ldots,\mathbf{b}_j,\ldots,\mathbf{b}_N\}. The reader can check that in 3 dimension, p1=b2∧b3\mathbf{p}_1=\mathbf{b}_2\wedge\mathbf{b}_3.

Reduction by orthogonal projection on the first hyperplane layer

Beside the metric tensor used to quantify the lattice rhombicity, we need another crystallographic concept, the “layers”. We will also employ the left inverse of matrices as coordinate transformation matrices between N×NN \times N space and its N×(N−1)N \times(N-1) subspaces, a tool we already introduced for 3 ×\times 3 spaces in [4]. Let us consider a unit cell of the lattice L={b1,…,bj,…,bN}\mathcal{L}=\{\mathbf{b}_1,\ldots,\mathbf{b}_j,\ldots,\mathbf{b}_N\} attached to the hyperplane {b2,…,bj,…,bN}\{\mathbf{b}_2,\ldots,\mathbf{b}_j,\ldots,\mathbf{b}_N\}. There are many equivalent unit cells, but we are looking for a quasi-reduced one. First we replace the N−1N-1 sublattice {b2,…,bj,…,bN}\{\mathbf{b}_2,\ldots,\mathbf{b}_j,\ldots,\mathbf{b}_N\} by its reduced form {b2′,…,bj′,…,bN′}\{\mathbf{b}'_2,\ldots,\mathbf{b}'_j,\ldots,\mathbf{b}'_N\} obtained by Lagrange’s division as described in §2.1. If the N−1N-1 reduction is not possible, the sublattice {b2,…,bj,…,bN}\{\mathbf{b}_2,\ldots,\mathbf{b}_j,\ldots,\mathbf{b}_N\} is not replaced. All the vectors bj′\mathbf{b}'_j belong to the hyperplane; we say that they are in the layer q=0q=0 of the plane p1\mathbf{p}_1. The vector b1\mathbf{b}_1 is the layer q=1q=1 of the hyperplane p1\mathbf{p}_1. The set {b1,b2′,…,bj′,…,bN′}\{\mathbf{b}_1,\mathbf{b}'_2,\ldots,\mathbf{b}'_j,\ldots,\mathbf{b}'_N\} is a unit cell attached to the hyperplane. Vectors of the lattice L\mathcal{L} on the layer q=1q=1 shorten than b1\mathbf{b}_1 can be determined as follows. We note O the origin of the lattice and Z the point such that OZ→=b1\overrightarrow{\mathrm{OZ}}=\mathbf{b}_1, as illustrated in Figure 3. We call H the projection of O on the layer q=1q=1 of the hyperplane p1\mathbf{p}_1. It is such that OH→∥p1\overrightarrow{\mathrm{OH}}\parallel\mathbf{p}_1 and p1tOH→=p1tb1\mathbf{p}_1^{\mathrm{t}}\overrightarrow{\mathrm{OH}}=\mathbf{p}_1^{\mathrm{t}}\mathbf{b}_1. Thus,

Hyperplanar reduction showing lattice layers $q=0$ and $q=1$, vectors, hyperplane, and orthogonal projection

Figure 3. Hyperplanar reduction. The lattice is “stratified” into different layers. Here only the layers q=0q=0 and q=1q=1 are represented. The vector of the layer q=1q=1 that should shorten/reduced is OZ=b1\mathbf{OZ}=\mathbf{b}_1. The reduction is made thanks to the calculation of the point H (marked by a little orange star) which is the orthogonal projection of the origin O onto the layer q=1q=1.

OH→=(p1tb1p1tp1)p1.\overrightarrow{\mathrm{OH}}=\left(\frac{\mathbf{p}_1^{\mathrm{t}}\mathbf{b}_1}{\mathbf{p}_1^{\mathrm{t}}\mathbf{p}_1}\right)\mathbf{p}_1.

Its coordinates are not integer but remain rational.

The vector ZH=−OZ+ZH\mathbf{ZH}=-\mathbf{OZ}+\mathbf{ZH} is a vector of the hyperplane p1\mathbf{p}_1, which means that it can be written as a linear combination of the vectors {b2′,…,bj′,…,bN′}\{\mathbf{b}'_2,\ldots,\mathbf{b}'_j,\ldots,\mathbf{b}'_N\}. In order to get its coordinates, we use again the N×N−1N\times N-1 matrix formed by writing the reduced vectors in columns, i.e.

S1′=[b1,2′⋯b1,j′⋯b1,N′⋮⋯⋮⋯⋮bi,2′⋯bi,j′⋯bi,N′⋮⋯⋮⋯⋮bN,2′⋯bN,j′⋯bN,N′]\mathbf{S}'_1= \begin{bmatrix} b'_{1,2} & \cdots& b'_{1,j} & \cdots& b'_{1,N}\\ \vdots& \cdots& \vdots& \cdots& \vdots\\ b'_{i,2} & \cdots& b'_{i,j} & \cdots& b'_{i,N}\\ \vdots& \cdots& \vdots& \cdots& \vdots\\ b'_{N,2} & \cdots& b'_{N,j} & \cdots& b'_{N,N} \end{bmatrix}

The N−1N-1 local coordinates of ZH\mathbf{ZH} in the basis {b2′,…,bj′,…,bN′}\{\mathbf{b}'_2,\ldots,\mathbf{b}'_j,\ldots,\mathbf{b}'_N\} are given by ZHloc=(S1′)Left−1⋅ZH\mathbf{ZH}_{loc}=(\mathbf{S}'_1)^{-1}_{Left}\cdot\mathbf{ZH} where (S1′)Left−1(\mathbf{S}'_1)^{-1}_{Left} is the left inverse of the matrix S1′\mathbf{S}'_1. We already used it in Cayron (2021); we recall that a left inverse of a non-square matrix M\mathbf{M} is MLeft−1=(MtM)−1Mt\mathbf{M}^{-1}_{Left}=(\mathbf{M}^{t}\mathbf{M})^{-1}\mathbf{M}^{t}. The vector ZHloc={z2,z3,…,zN}\mathbf{ZH}_{loc}=\{z_2,z_3,\ldots,z_N\} is a rational N−1N-1 dimensional vector in the N−1N-1 subspace. A lattice point Z′\mathbf{Z}' close to H that belongs to the same layer is given by Z′Hloc={⌊z2⌉,⌊z3⌉,…,⌊zN⌉}\mathbf{Z}'\mathbf{H}_{loc}=\{\lfloor z_2\rceil,\lfloor z_3\rceil,\ldots,\lfloor z_N\rceil\}. The vector ZZloc′=ZHloc−Z′Hloc\mathbf{ZZ}'_{loc}=\mathbf{ZH}_{loc}-\mathbf{Z'H}_{loc} is calculated and re-expressed in the NN-dimensional space by ZZ′=S1′⋅ZZloc′\mathbf{ZZ}'=\mathbf{S}'_1\cdot\mathbf{ZZ}'_{loc}. The vector b1′=OZ′=OZ+ZZ′\mathbf{b}'_1=\mathbf{OZ}'=\mathbf{OZ}+\mathbf{ZZ}' is a reduced form of the vector b1\mathbf{b}_1. The rhombicity is re-calculated; if it has decreased, the solution {b2′,…,bj′,…,bN′,b1′}\{\mathbf{b}'_2,\ldots,\mathbf{b}'_j,\ldots,\mathbf{b}'_N,\mathbf{b}'_1\} replaces {b1,…,bj,…,bN}\{\mathbf{b}_1,\ldots,\mathbf{b}_j,\ldots,\mathbf{b}_N\} and the process is repeated with the new list by recursion. If it has not decreased, the next vector in the list, b2\mathbf{b}_2, is used to calculate p2\mathbf{p}_2 and b2′\mathbf{b}'_2, etc. The process stops when all the vectors bi\mathbf{b}_i of the list {b1,…,bj,…,bN}\{\mathbf{b}_1,\ldots,\mathbf{b}_j,\ldots,\mathbf{b}_N\} are screened but none of the vector bi′\mathbf{b}'_i allows to reduce anymore the lattice rhombicity. In materials science, we would say that bi′\mathbf{b}'_i is obtained from bi\mathbf{b}_i by “simple shearing” on the hyperplane pi\mathbf{p}_i. In paper, we will call this operation “hyperplanar reduction”. The reader can notice that both Lagrange’s division and hyperplanar reduction imply orthogonal projections followed by numerical rounding in which rational numbers are replaced by their closest integers. After hyperplanar reduction, the lattice that was previously directionally reduced at the end of § 2.2 becomes even more reduced since its values decreased to R=451R = 451 and S=113S = 113. These values are not yet as good as those obtained by LLL, but we have not yet used with the interplay between directional and hyperplanar reductions.

Cubification methods by cycling direction and hyperplanar reductions

Methods and options

Directional and hyperplanar reductions can now be repeated in cycles until the lattice rhombicity cannot be decreased anymore. We call this cycling “cubification”. There is not a unique way to perform a cubification as it can be started by the hyperplanar reduction or by directional reduction. It also depends on the algorithm variants chosen for Lagrange’s division (§ 2.1) and the simplification (§ 2.2) of the direction reduction. By trial-and-error, we could identify two cubification methods (Table 1).

Method 1:Method 2:
Cubification (list, opt.):Cubification (list, opt.):
newlist = Sort_by_norm (list)newlist = Sort_by_norm (list)
newlist = Directional reduction (newlist, opt.)newlist = Hyperplanar reduction (newlist)
newlist = Hyperplanar reduction (newlist)newlist = Directional reduction (newlist, opt.)
If RR (newlist) < RR (list):newlist = Hyperplanar reduction (newlist)
Return Cubification (newlist, opt.)If RR (newlist) < RR (list):
Else Return listReturn Cubification (newlist, opt.)
Else Return list

Table 1. Two cubification methods. Their options are given in Table 2.

The algorithm variant that should be chosen depends on the type of matrix formed by the set of vectors that should be reduced (Table 2). We call here “columnar matrix” a list of vectors whose matrix (the vectors are written in rows) contains many zeros, and at least one column with many non-null and generally high integer values. A typical example is the matrix given in Figure 1a. We noticed that for large matrices, i.e. in dimensions approximatively N≥15N \ge15, Lagrange’s division in its Append variant gives better results. We call “heterogeneous matrix”, a matrix that contains many zeros, and at least one row and one column with many non-null and generally high integer values. We noticed that for some cases of large heterogeneous matrices, with approximatively N≥15N \ge15, the first directional reduction goes beyond the recursion limit of our computer; when this happens, a first hyperplanar reduction without N−1N - 1 directional reduction solves the problem. We call “random matrix” a matrix whose values are randomly computed with integers between 0 and 100. Larger limits, for example 1000, in large random matrices N≥15N \ge15 leads to too high integer values in intermediate calculations and error messages both in OLLL and Cubification. A columnar random matrix is an identity matrix in which the last column is replaced by random integers in the range 0-100. Columnar random matrices are classified here as random matrices and are treated with method 2.

Type of list of vectorsCubification methodVariant for the Directional reduction: Lagrange’s divisionVariant for the Directional reduction: Simplification
Small columnar matrixMethod 1InsertInsert
Large columnar matrixMethod 1AppendInsert
Large heterogeneous matrixMethod 1 (N−1N - 1 Hyperplanar reduction +)InsertInsert
Random matrixMethod 2AppendAppend

Table 2. Method with options to be used depending of the type of the list of vectors (square matrix). We consider “large” a matrix of dimension N≥15N \ge15. For some large heterogeneous matrices a first step with hyperplanar reduction without N−1N - 1 directional reduction may be required before starting Method 1 as indicated in parenthesis .

Computer program and comparisons

We wrote a computer program called Cubification in Python 3.8 using the Numpy library to perform the matrix calculations (scalar products, matrix products, inverses etc.) and to generate the random numbers, vectors and matrices. All the results presented in the paper were obtained with a 6 years old laptop equipped with Intel(R) Core(TM)i7-4600 CPU 2.1 GHz, 64-bit Windows system, with a RAM of 8 GB. The recursion limit in our Python program has been fixed to 10’000. We compared the results obtained with our program with those obtained by the LLL method computed in Python3 by Yonashiro [8] and called OLLL. All the OLLL calculations were made with α=3/4\alpha= 3/4. For specific matrices, as that of Figure 1, we also used the function ReduceLattice of Mathematica. On this example we checked that OLLL and Mathematica gives the same result; the only difference is that the calculations are nearly instantaneous with Mathematica whereas they are quite long with OLLL. As both use the same algorithm principles, this observation shows that one cannot compare easily the execution times to estimate the efficiency of an algorithm. Part of slowness of OLLL probably comes from the fact that Python is an interpreted language. In the rest of the paper, the execution times will be compared only between our program Cubification and OLLL because both are written in Python.

Results on non-random matrices

The best results of Cubification are obtained with columnar non-random matrices. For them our algorithm not only equals LLL but it seems to outperform it. For small columnar matrices, the cubification algorithm gives the same results as LLL, and for large N≥10−15N \geq10 - 15 matrices, our experience shows that it gives in general reduced lists with RR and SS values that are lower than with LLL. For example, the lattice of Figure 1a could be reduced in only 3 cycles such that the final lattice is characterized by R=308R = 308, S=88S = 88; these values are clearly lower than those obtained by the LLL (R=531R = 531, S=99S = 99). The output list of vectors is given in Figure 4. One reason of the better cubicity is that the ±1\pm1 are more homogenously distributed among the 20 columns. Now, if one compare the execution time, the result was obtained in only 2.5 s with Cubification, whereas 71 s were required for OLLL. The lattice that was already reduced by LLL given in Figure 1b could even be reduced more with Cubification in 1.2 s with final values R=360R = 360, S=92S = 92. It can be noted that these values are however not as good as those obtained from the initial matrix in Figure 1a.

Figure 4. Cubification by the method 1 of the lattice of Figure 1a. The vectors are written in rows, as in Figure 1. The reduced lattice has for values R=308R = 308, S=88S = 88.

For heterogeneous matrices, we have tested only five 20×2020 \times20 matrices, and all of them show that LLL and cubification gives similar results. An example with a 20×2020 \times20 matrix is given in Figure S1.

Figure S1. Example of reduction of heterogeneous matrix with LLL and cubification. (a) Input matrix R=489734657R = 489734657, S=68191151S = 68191151, (b) matrix reduced by LLL, R=12007R = 12007, S=10407S = 10407, (c) matrix reduced by cubification R=11905R = 11905, $S = 10407.

Results on random matrices

One way to automatically compare the algorithms is to generate random matrices. We have tested the performances of Cubification (method 2) and OLLL programs on columnar random matrices and full random matrices. We have tested the program on matrices of dimensions 10 ×\times 10, 12 ×\times 12 and 14 ×\times 14. Fifty matrices have been generated for each type. The performances are measured by the reduction factors R (input)R (output)\frac{R\ (\mathrm{input})}{R\ (\mathrm{output})} and S (input)S (output)\frac{S\ (\mathrm{input})}{S\ (\mathrm{output})}. The highest the reduction factors, the better the algorithm. The results are given in Table 3.

Reduction factorR (input)R (output)\frac{R\ (\mathrm{input})}{R\ (\mathrm{output})}S (input)S (output)\frac{S\ (\mathrm{input})}{S\ (\mathrm{output})}Mean time per matrix
Columnar random matrices 10 ×\times 10
OLLL278010002.4 s
Cubification360010600.11 s
Columnar random matrices 12 ×\times 12
OLLL312010605.5 s
Cubification410010900.33 s
Columnar random matrices 14 ×\times 14
OLLL3630116010.5 s
Cubification437010700.54 s
Full random matrices 10 ×\times 10
OLLL14.35.22.2 s
Cubification16.95.40.22 s
Full random matrices 12 ×\times 12
OLLL14.15.05.6 s
Cubification15.24.60.71 s
Full random matrices 14 ×\times 14
OLLL13.64.712.7 s
Cubification14.34.11.30 s

Table 3. Reduction factors and mean time obtained on columnar and full random matrices of dimensions 10 ×\times 10, 12 ×\times 12 and 14 ×\times 14 by testing 50 matrices. The mean deviation estimated by various tests is for OLLL around ±\pm 20 % for 10x10 matrix and it decreases down to ±\pm 5% for 14 ×\times 14 matrix. It seems to be 30 % larger for Cubification.

The reduction of the rhombicity is systematically better with Cubification than with OLLL algorithm. The norms seem however less reduced by Cubification for large full random matrices. By comparing the execution times, Cubification appears to be approximatively ten times faster than OLLL. As the two computer programs use the same language (Python3) we can suppose that the cubification algorithm is at least as time effective as the LLL one. Clearly, more studies involving specialists of computer programming are required to better evaluate and compare the advantages and limits of both algorithms. One can even imagine a larger algorithm in which both methods would work together.

Conclusion and perspectives

We propose an alternative approach to the LLL algorithm for the problem of lattice reduction. It is based on the complementary actions of directional reduction and hyperplanar reduction. The former implies projections on the basis vectors (1 dimensional subspaces) and the latter on the basis hyperplanes (N−1N - 1 dimensional subspaces). The algorithm does not require the calculations of Gram-Schmidt bases. The driving parameter of the reduction is the lattice rhombicity, a parameter that encompasses the information on the norms and on the deviations from orthogonality of the basis vectors. The results are quite equivalent to LLL for random and heterogeneous matrices, and systematically better for columnar matrices. We wrote a computer program in Python3 called Cubification and we compared its execution time with another Python3 computer program called OLLL. Our program is approximatively ten times faster, which makes us think that cubification may be more effective than LLL. More studies are however required to confirm or infirm this assertion.

We foresee margins of progression for cubification. The two cubification methods described in §4.1 were determined by trial-and-error; better strategies to alternate the directional and hyperplanar reduction processes seem possible, for example by cross-calling the two processes without necessarily screening all the vectors in the basis. We will also try to generalize to the whole program the N→N−1N \rightarrow N - 1 decrease of dimensions already used in the hyperplanar reduction with help left inverse matrices. Reducing efficiently a lattice requires a strategy of optimisation in the space of possible paths. We think that our work on the Taylor series of optimized functions applied to the function “rhombicity” could be a way to find an effective path in reasonable time. It should be recalled however that, as LLL, cubification gives only a good solution, but not necessarily the best one. More theoretical mathematics are required to evaluate how far the good solutions are from the optima. The new approach proposed in the present paper may probably help to get a new point of view on this problem and improve our understanding of the nature of its complexity.

Lattice reduction is used in various technological fields such as computer science, cryptography, image processing, etc. Cubification may be beneficial in these domains. We take the opportunity of this paper to draw the attention of cryptographers on crystallography, and more especially on the groupoid composition table formed by the variants (simple-cosets) and their operators (doublecosets). These tables were introduced for phase transformations in materials [1] but could have application in cryptography once generalized to groups larger than the 32 crystallographic point groups.

Acknowledgements

Prof. Roland Logé is warmly acknowledged for the freedom given to our research that sometimes goes beyond metallurgy.

Note: In a first time, the Python program Cubification will be made available to the reviewers of the present manuscript. If the manuscript is accepted for publication, the program and its sources will be deposited on github or will be freely available on demand.

Supporting information

Example of reduction of an heterogeneous matrix

(a) Input (the coordinates of the vectors are written in rows)

[6784−97−33421909−23111−3611248914567433499941276945−853−11−84237−33342919−189911−36148156−54334099−4876145−31300100000000000000001586000100000000000000010300000100000000000000192100000100000000000005690000001000000000000−72100000001000000000001183000000001000000000015700000000001000000000−66650000000000100000000123000000000001000000089000000000000010000006000000000000010000074200000000000000100003300000000000000010008880000000000000000100140000000000000000010769000000000000000000112340000000000000000000−853]\begin{bmatrix}67&84&-97&-33&421&909&-23&1&11&-361&124&891&456&743&34&999&412&769&45&-853\\-11&-84&237&-333&42&919&-18&99&11&-36&14&81&56&-543&340&99&-48&76&145&-313\\0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1586\\0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1030\\0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1921\\0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&0&569\\0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&-721\\0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1183\\0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1570\\0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&-6665\\0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&123\\0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&890\\0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&0&6\\0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&0&742\\0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&33\\0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&888\\0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&14\\0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&0&769\\0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&1&1234\\0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&-853\end{bmatrix}

(b) Output LLL

[000−101110000000000010001−100000010000000−100−1000−1000100100000000000−100100−101000000000000−10−100−1001000000010−110000−100100000000−11000−1000000100000000−1001010010−1100000000−100100010011000000010−1001000010000001000−100100001−100010000000001000−1−1−1001000100000101101000−100000000−10010000−10011100000000−10−100000−110−11000010−100000−100000−10−1000−10−1010000−100000000000000−10010010−10000056000000−100−1−100000000−11−84000101000001−100000]\begin{bmatrix}0&0&0&-1&0&1&1&1&0&0&0&0&0&0&0&0&0&0&0&1\\0&0&0&1&-1&0&0&0&0&0&0&1&0&0&0&0&0&0&0&-1\\0&0&-1&0&0&0&-1&0&0&0&1&0&0&1&0&0&0&0&0&0\\0&0&0&0&0&-1&0&0&1&0&0&-1&0&1&0&0&0&0&0&0\\0&0&0&0&0&0&-1&0&-1&0&0&-1&0&0&1&0&0&0&0&0\\0&0&1&0&-1&1&0&0&0&0&-1&0&0&1&0&0&0&0&0&0\\0&0&-1&1&0&0&0&-1&0&0&0&0&0&0&1&0&0&0&0&0\\0&0&0&-1&0&0&1&0&1&0&0&1&0&-1&1&0&0&0&0&0\\0&0&0&-1&0&0&1&0&0&0&1&0&0&1&1&0&0&0&0&0\\0&0&1&0&-1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&1\\0&0&0&-1&0&0&1&0&0&0&0&1&-1&0&0&0&1&0&0&0\\0&0&0&0&0&0&1&0&0&0&-1&-1&-1&0&0&1&0&0&0&1\\0&0&0&0&0&1&0&1&1&0&1&0&0&0&-1&0&0&0&0&0\\0&0&0&-1&0&0&1&0&0&0&0&-1&0&0&1&1&1&0&0&0\\0&0&0&0&0&-1&0&-1&0&0&0&0&0&-1&1&0&-1&1&0&0\\0&0&1&0&-1&0&0&0&0&0&-1&0&0&0&0&0&-1&0&-1&0\\0&0&-1&0&-1&0&1&0&0&0&0&-1&0&0&0&0&0&0&0&0\\0&0&0&0&0&0&-1&0&0&1&0&0&1&0&-1&0&0&0&0&0\\56&0&0&0&0&0&0&-1&0&0&-1&-1&0&0&0&0&0&0&0&0\\-11&-84&0&0&0&1&0&1&0&0&0&0&0&1&-1&0&0&0&0&0\end{bmatrix}

(c) Output cubification (method 1)

(00000000−1−1010000−100000000−100100−1010000000000000000010010110000−100000000−10000010−100−1000000−10010100000000−10000−100010010000000010−1000000000010−100010−1−1−100000000000−10000−11000−1000100010000000−100−10−1000000−1−10000010001000100001010000100000−101000−1100000−100−110000000−1100000000000001101010100000−10−1−10−100001000000000010100000001000−1−100110000−10−1000001100000−11110−100−10000100−1−56000−100000−100−100000−1−11−840000−1000000010000−1)\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & 0 & 1 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 1 & 0 & 0 & -1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & -1 \\ 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & -1 \\ 0 & 0 & 0 & 1 & 0 & -1 & -1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 1 & 0 & 0 & 0 & -1 & 1 & 0 & 0 \\ 0 & 0 & 0 & -1 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & -1 & 0 & -1 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & -1 & -1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & -1 & 1 & 1 & 1 & 0 & -1 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & -1 \\ -56 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & -1 \\ -11 & -84 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & -1 \end{pmatrix}

References

  1. [1]Cayron, C. (2006). Groupoid of orientational variants. Acta Cryst. A62, 21-40.pubmed.ncbi.nlm.nih.gov/16371700
  2. [4]Cayron, C. (2021a) Axial Heterotwins, https://arxiv.org/abs/2011.03931 submitted to Acta Crystallographica,
  3. [5]Cayron, C. (2021b). A fast algorithm to solve the det-1 column-constrained integer matrix problem and hyperplane unit cells, will be submitted to Acta Crystallographica.
  4. [7]Nguyen, P.Q. & Vallée, B. (2010). The LLL algorithm. Survey and Applications. Springer-Verlag Berlin Heidelberg.
  5. [8]Yonashiro, N. (2020) OLLL, A Python3 Implementation of LLL, available at https://github.com/orisano/olll (last access 08 January 2021).
  6. [9]Wikipedia (2020), https://en.wikipedia.org/wiki/Lenstra/Lenstra/Lovász_lattice_basis_reduction_algorithm

Paper details

vlnc:W_vd8c6eqy
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents