LLL reduction: Difference between revisions
first draft |
m Bold lemma and recategorize |
||
| (8 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 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. | 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. | ||
== | Another application is finding good bases for JI that can be used as [[Fokker block]]s. | ||
== Computing the comma basis for a temperament == | |||
Let's take 7-limit meantone as an example. The mapping matrix is: | Let's take 7-limit meantone as an example. The mapping matrix is: | ||
$$ | $$ | ||
| Line 23: | 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 54: | Line 56: | ||
This gives a comma basis of [[126/125]] and [[81/80]], which is what we expect for septimal meantone. | This gives a comma basis of [[126/125]] and [[81/80]], which is what we expect for septimal meantone. | ||
== Computing Fokker blocks == | |||
Consider some p-limit [[subgroup]], with the log-prime vector | |||
<math>j = \begin{bmatrix} | |||
\log_2 2 & \log_2 3 & \cdots & \log_2 p \\ | |||
\end{bmatrix} </math>. | |||
Pick some value for k, and construct the following block matrix: | |||
$$ | |||
\begin{bmatrix} | |||
\mathrm{I} \\ | |||
\hline | |||
k \cdot j | |||
\end{bmatrix} | |||
= | |||
\begin{bmatrix} | |||
1 & 0 & \cdots & 0 \\ | |||
0 & 1 & \cdots & 0 \\ | |||
\vdots & \vdots & \ddots & \vdots \\ | |||
0 & 0 & \cdots & 1 \\ | |||
\hline | |||
k \log_2(2) & k \log_2(3) & \cdots & k \log_2(p) & | |||
\end{bmatrix} | |||
$$ | |||
(Note the similarity to the definition of the k-Weil-Euclidean norm.) | |||
After applying LLL reduction to the columns, and removing the last row, we are left with a square matrix that defines a change of basis. | |||
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: | |||
$$ | |||
\begin{bmatrix} | |||
\mathrm{I} \\ | |||
\hline | |||
800 j | |||
\end{bmatrix} | |||
= | |||
\begin{bmatrix} | |||
1 & 0 & 0 & 0 \\ | |||
0 & 1 & 0 & 0 \\ | |||
0 & 0 & 1 & 0 \\ | |||
0 & 0 & 0 & 1 \\ | |||
\hline | |||
800 & 1268 & 1858 & 2246 & | |||
\end{bmatrix} | |||
$$ | |||
We can interpret the columns as consisting of intervals followed by their size. If we had picked k = 1200, the last row would be in cents. | |||
When LLL reducing this matrix, we are asking for columns that have small coefficients, as well as small spans, which is what we want for nice commas! | |||
The choice of parameter k will set the tradeoff between the span and complexity, larger k giving smaller but more complex commas. | |||
The reduced basis is: | |||
$$ | |||
\begin{bmatrix} | |||
\mathrm{B} \\ | |||
\hline | |||
u | |||
\end{bmatrix} | |||
= | |||
\begin{bmatrix} | |||
-5 & 6 & -5 & -1 \\ | |||
-1 & 0 & 2 & -7 \\ | |||
-2 & -5 & 2 & 4 \\ | |||
4 & 2 & -1 & 1 \\ | |||
\hline | |||
0 & 2 & 6 & 2 | |||
\end{bmatrix} | |||
$$ | |||
Throwing away the bottom row, we are left with a square matrix <math>\mathrm{B}</math>. | |||
Reading off the columns as prime-count vectors, we get: | |||
* <math>2^{-5} \cdot 3^{-1} \cdot 5^{-2} \cdot 7^{4} = </math> [[2401/2400]], the breedsma. | |||
* <math>2^{6} \cdot 5^{-5} \cdot 7^{2} = </math> [[3136/3125]], the didacus comma. | |||
* <math>2^{-5} \cdot 3^{2} \cdot 5^{2} \cdot 7^{-1} = </math> [[225/224]], the marvel comma. | |||
* <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| \det (\mathrm{B}) \right| = 1</math> so we can invert it in the integers. | |||
$$ | |||
\mathrm{B}^{-1} = | |||
\begin{bmatrix} | |||
19 & 30 & 44 & 53 \\ | |||
72 & 114 & 167 & 202 \\ | |||
99 & 157 & 230 & 278 \\ | |||
31 & 49 & 72 & 87 \\ | |||
\end{bmatrix} | |||
$$ | |||
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, 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]] | |||