LLL reduction: Difference between revisions
Category:Algorithm |
m Bold lemma and recategorize |
||
| 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: | [[Category:Algorithms]] | ||