LLL reduction: Difference between revisions
use lowercase edo when suffixed |
m Bold lemma and recategorize |
||
| (2 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 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:Algorithms]] | |||