LLL reduction: Difference between revisions
m forgot a det |
m Bold lemma and recategorize |
||
| (5 intermediate revisions by one other user not shown) | |||
| Line 1: | Line 1: | ||
{{Wikipedia|Lenstra–Lenstra–Lovász lattice basis reduction algorithm}} | {{Wikipedia|Lenstra–Lenstra–Lovász lattice basis reduction algorithm}} | ||
The LLL (Lenstra–Lenstra–Lovász) reduction is an algorithm that computes a basis with short, nearly orthogonal vectors when given an integer lattice. | The '''LLL''' ('''Lenstra–Lenstra–Lovász''') '''reduction''' is an algorithm that computes a basis with short, nearly orthogonal vectors when given an integer lattice. | ||
Although determining the 'best' basis is an NP-complete problem{{Citation needed}}, the LLL algorithm can find a good basis in polynomial time. | Although determining the 'best' basis is an NP-complete problem{{Citation needed}}, the LLL algorithm can find a good basis in polynomial time. | ||
| Line 25: | Line 25: | ||
$$ | $$ | ||
When computing the kernel of this map (using e.g. | When computing the kernel of this map (using e.g. the [[Hermite normal form]]), we get: | ||
$$ | $$ | ||
\begin{eqnarray} | \begin{eqnarray} | ||
| Line 67: | Line 67: | ||
\mathrm{I} \\ | \mathrm{I} \\ | ||
\hline | \hline | ||
k \cdot | k \cdot j | ||
\end{bmatrix} | \end{bmatrix} | ||
= | = | ||
| Line 84: | Line 84: | ||
Since this basis is unimodular, we can invert it to obtain a dual basis containing EDO-maps. | Since this basis is unimodular, we can invert it to obtain a dual basis containing EDO-maps. | ||
To give a concrete example, consider 7-limit JI, and pick (somewhat arbitrarily) k = 800. The matrix then looks like: | To give a concrete example, consider [[7-limit]] JI, and pick (somewhat arbitrarily) k = 800. The matrix then looks like: | ||
$$ | $$ | ||
\begin{bmatrix} | \begin{bmatrix} | ||
\mathrm{I} \\ | \mathrm{I} \\ | ||
\hline | \hline | ||
800 | 800 j | ||
\end{bmatrix} | \end{bmatrix} | ||
= | = | ||
| Line 142: | Line 142: | ||
$$ | $$ | ||
The rows of this matrix are the 7-limit maps of | The rows of this matrix are the 7-limit maps of [[19edo]], [[72edo]], [[99edo]] and [[31edo]]. | ||
Of course, this matrix is also unimodular, so it defines a change of basis in the dual space. | Of course, this matrix is also unimodular, so it defines a change of basis in the dual space. | ||
Because they are inverses, these two bases have the property that for each EDO, the corresponding comma is mapped to 1 step, and all the other commas are tempered out. | Because they are inverses, these two bases have the property that for each EDO, the corresponding comma is mapped to 1 step, and all the other commas are tempered out. | ||
For example, | For example, 31edo maps the ragisma to one step, and tempers out the breedsma, didacus and marvel comma. In fact, 31edo is the unique EDO tempering out these three commas in the 7-limit. | ||
[[Category:Algorithms]] | |||