  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.
