LLL reduction - Revision history

FloraC: Bold lemma and recategorize

2025-03-31T07:59:48Z

Bold lemma and recategorize

← Older revision		Revision as of 07:59, 31 March 2025
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 147:		Line 147:
	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.		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:~~Algorithm~~]]		[[Category:Algorithms]]

Sintel: Category:Algorithm

2025-03-29T18:34:59Z

Category:Algorithm

← Older revision		Revision as of 18:34, 29 March 2025
Line 146:		Line 146:
	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, 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.		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:Algorithm]]

Sintel: Sintel moved page User:Sintel/LLL reduction to LLL reduction: Move to main

2025-02-17T14:35:45Z

Sintel moved page User:Sintel/LLL reduction to LLL reduction: Move to main

← Older revision	Revision as of 14:35, 17 February 2025
(No difference)

Sintel: use lowercase edo when suffixed

2024-12-28T14:19:31Z

use lowercase edo when suffixed

← Older revision		Revision as of 14:19, 28 December 2024
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}
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.		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, ~~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.

Sintel: too many logs

2024-12-28T01:32:30Z

too many logs

← Older revision		Revision as of 01:32, 28 December 2024
Line 67:		Line 67:
	\mathrm{I} \\		\mathrm{I} \\
	\hline		\hline
	k \cdot ~~\log_2~~ j		k \cdot j
	\end{bmatrix}		\end{bmatrix}
	=		=
Line 89:		Line 89:
	\mathrm{I} \\		\mathrm{I} \\
	\hline		\hline
	800 ~~\cdot \log_2~~ j		800 j
	\end{bmatrix}		\end{bmatrix}
	=		=

Sintel at 20:28, 27 December 2024

2024-12-27T20:28:41Z

← Older revision		Revision as of 20:28, 27 December 2024
Line 25:		Line 25:
	$$		$$

	When computing the kernel of this map (using e.g. ~~hermite~~ normal form), ~~you will~~ get ~~something like~~:		When computing the kernel of this map (using e.g. the [[Hermite normal form]]), we get:
	$$		$$
	\begin{eqnarray}		\begin{eqnarray}

Sintel: forgot a det

2024-12-27T20:15:12Z

forgot a det

← Older revision		Revision as of 20:15, 27 December 2024
Line 131:		Line 131:
	* <math>2^{-1} \cdot 3^{-7} \cdot 5^{4} \cdot 7 = </math> [[4375/4374]], the ragisma.		* <math>2^{-1} \cdot 3^{-7} \cdot 5^{4} \cdot 7 = </math> [[4375/4374]], the ragisma.

	Because we started with the identity matrix, this block is guaranteed have <math>\left\| \mathrm{B} \right\| = 1</math> so we can invert it in the integers.		Because we started with the identity matrix, this block is guaranteed have <math>\left\| \det (\mathrm{B}) \right\| = 1</math> so we can invert it in the integers.
	$$		$$
	\mathrm{B}^{-1} =		\mathrm{B}^{-1} =

Sintel: correct primes

2024-12-27T19:50:14Z

correct primes

← Older revision		Revision as of 19:50, 27 December 2024
Line 76:		Line 76:
	0 & 0 & \cdots & 1 \\		0 & 0 & \cdots & 1 \\
	\hline		\hline
	k \log_2(~~p_1~~) & k \log_2(~~p_2~~) & \cdots & k \log_2(~~p_n~~) &		k \log_2(2) & k \log_2(3) & \cdots & k \log_2(p) &
	\end{bmatrix}		\end{bmatrix}
	$$		$$

Sintel: Computing Fokker blocks

2024-12-27T19:49:00Z

Computing Fokker blocks

@@ Line 10: / Line 10: @@
 Since LLL reduction depends on the choice of inner product, we can use something like the [[Tenney-Euclidean norm|Tenney]] or [[Wilson height|Wilson]] norm to define the complexity we want to penalize.
-== Example of computing a comma basis ==
+Another application is finding good bases for JI that can be used as [[Fokker block]]s.
 Let's take 7-limit meantone as an example. The mapping matrix is:
 $$
@@ Line 54: / Line 56: @@
 This gives a comma basis of [[126/125]] and [[81/80]], which is what we expect for septimal meantone.

Sintel: first draft

2024-12-27T17:05:37Z

first draft

New page

{{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.
Although determining the 'best' basis is an NP-complete problem{{Citation needed}}, the LLL algorithm can find a good basis in polynomial time.

== Applications ==
The most obvious application of LLL reduction is finding a good comma basis for some abstract temperament.
When computing the kernel of a temperament, the commas define a lattice. Applying LLL reduction to this lattice finds a new basis where all commas are short.
Note that 'short' with respect to a suitable norm here means really means 'simple'.
Since LLL reduction depends on the choice of inner product, we can use something like the [[Tenney-Euclidean norm|Tenney]] or [[Wilson height|Wilson]] norm to define the complexity we want to penalize.

== Example of computing a comma basis ==
Let's take 7-limit meantone as an example. The mapping matrix is:
$$
\begin{eqnarray}
\left[
\begin{array}{rrrr}
1 & 0 & -4 & 13 \\
0 & 1 & 4 & 10
\end{array}
\right]
\end{eqnarray}
$$

When computing the kernel of this map (using e.g. hermite normal form), you will get something like:
$$
\begin{eqnarray}
\left[
\begin{array}{rrr}
1 & 0 \\
2 & 12 \\
-3 & -13 \\
1 & 4
\end{array}
\right]
\end{eqnarray}
$$

Reading off the columns of this matrix, these give <math>2 \cdot 3^{2} \cdot 5^{-3} \cdot 7 = </math> [[126/125]] and <math>3^{12} \cdot 5^{-13} \cdot 7^{4} = </math> 1275989841/1220703125, which is probably not what we want.

Applying LLL reduction to the columns of this matrix gives:
$$
\begin{eqnarray}
\left[
\begin{array}{rrr}
1 & -4 \\
2 & 4 \\
-3 & -1 \\
1 & 0
\end{array}
\right]
\end{eqnarray}
$$

This gives a comma basis of [[126/125]] and [[81/80]], which is what we expect for septimal meantone.