LLL reduction: Difference between revisions

(3 intermediate revisions by one other user not shown)

Line 1:

{{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.

Line 84:

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}

Line 142:

$$

The rows of this matrix are the 7-limit maps of ~~19-EDO~~, ~~72-EDO~~, ~~99-EDO~~ and ~~31-EDO~~.

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.

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, ~~31-EDO~~ maps the ragisma to one step, and tempers out the breedsma, didacus and marvel comma. In fact, ~~31-EDO~~ is the unique EDO tempering out these three commas in the 7 limit.

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]]

@@ Line 1: / Line 1: @@
 {{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.
@@ Line 84: / Line 84: @@
 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}
@@ Line 142: / Line 142: @@
 $$
-The rows of this matrix are the 7-limit maps of 19-EDO, 72-EDO, 99-EDO and 31-EDO.
+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.
 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, 31-EDO maps the ragisma to one step, and tempers out the breedsma, didacus and marvel comma. In fact, 31-EDO is the unique EDO tempering out these three commas in the 7 limit.
+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]]