लैटिस न्यूनन

File:Lattice-reduction.svg

दो आयामों में लैटिस में न्यूनन, काले सदिश लैटिस के लिए दिए गए आधार हैं (नीले बिंदुओं द्वारा दर्शाए गए), लाल सदिश लघुकृत आधार हैं।

गणित में, लैटिस आधार न्यूनन का लक्ष्य, एक पूर्णांक लैटिस आधार के साथ दिए गए निविष्ट के रूप में, छोटे और लगभग लांबिक सदिश वाले आधार का पता लगाना है। इसे विभिन्न कलन विधियो का उपयोग करके प्राप्त किया जाता है, जिसकी कार्यावधि सामान्यतः लैटिस के आयाम में कम से कम घातीय होती है।

लगभग लांबिक

लगभग लांबिक की एक माप 'लांबिक दोष' है। यह आधार सदिश की लंबाई के गुणन की तुलना उनके द्वारा परिभाषित समांतर चतुर्भुज के आयतन से करता है। पूर्णतः लांबिक आधार वाले सदिश के लिए, ये मात्राएँ समान होंगी।

$n$ सदिशों के किसी विशेष आधार को आव्यूह $B$, द्वारा दर्शाया जा सकता है, जिसके स्तंभ आधार सदिश $b_{i},i=1,\ldots ,n$ हैं। पूर्ण आयामी स्थिति में जहां आधार सदिश की संख्या उनके द्वारा व्याप्त समष्टि के आयाम के बराबर होती है, यह आव्यूह वर्गाकार होता है, और मूल समांतर चतुर्भुज का आयतन इस आव्यूह के निर्धारक का पूर्ण मान $\det(B)$ होता है। यदि सदिशों की संख्या अंतर्निहित समष्टि के आयाम से कम है, तो आयतन ${\sqrt {\det(B^{T}B)}}$ है।किसी दिए गए लैटिस $\Lambda$ के लिए , यह आयतन किसी भी पर समान (संकेत तक) है, और इसलिए इसे लैटिस $\det(\Lambda )$ या लैटिस स्थिरांक $d(\Lambda )$ के निर्धारक के रूप में जाना जाता है।

लांबिक दोष, समानांतर चतुर्भुज आयतन द्वारा विभाजित आधार सदिश लंबाई का गुणन है,

$\delta (B)={\frac {\Pi _{i=1}^{n}\|b_{i}\|}{\sqrt {\det(B^{T}B)}}}={\frac {\Pi _{i=1}^{n}\|b_{i}\|}{d(\Lambda )}}$

ज्यामितीय परिभाषा से यह स्पष्ट होता है कि $\delta (B)\geq 1$ समानता के साथ वास्तविकता दोष होगा, यदि जब आधार लांबिक हों।

यदि लैटिस न्यूनन की समस्या को सबसे छोटे संभावित दोष के साथ आधार का पता लगाने के रूप में परिभाषित किया गया है, तो समस्या NP कठिन होती है । हालाँकि, दोष $\delta (B)\leq c$ के साथ आधार का पता लगाने के लिए बहुपद काल कलन विधि मौजूद हैं जहां c कुछ स्थिरांक है जो केवल आधार सदिश की संख्या और अंतर्निहित समष्टि के आयाम (यदि भिन्न हो) पर निर्भर करता है। यह कई व्यावहारिक अनुप्रयोगों में एक अच्छा समाधान है।

दो आयामों में

केवल दो सदिशों से युक्त आधार के लिए, दो पूर्णांकों के सबसे बड़े सामान्य विभाजक के लिए यूक्लिडीयकलनविधि के अनुरूप न्यूनन की एक सरल और कुशल विधि है।यूक्लिडीयकलनविधि की तरह, यह तकनीक पुनरावृत्तिशील होती है, प्रत्येक चरण में छोटे सदिश के पूर्णांक गुणज को जोड़कर या घटाकर दो सदिशों में से बड़े को लघुकृत किया जाता है।

कलन विधि का छद्मकोड, जिसे अक्सर लैग्रेंज कलन विधि या लैग्रेंज-गॉस कलन विधि के रूप में जाना जाता है, वह इस प्रकार है,

    निविष्ट, ${\textstyle (u,v)}$ लैटिस के लिए एक आधार ${\textstyle L}$। मान लीजिए कि ${\textstyle ||v||\leq ||u||}$, अन्यथा उन्हें एक-दूसरे के साथ बदल दें।
    निर्गत, ${\textstyle ||u||=\lambda _{1}(L),||v||=\lambda _{2}(L)}$ के साथ एक आधार ${\textstyle (u,v)}$।

    जबकि ${\textstyle ||v||<||u||}$:          

${\textstyle q:=\lfloor {\langle u,{\frac {v}{||v||^{2}}}\rangle }\rceil }$ # निकटतम पूर्णांक तक पूर्णांकित करें

${\textstyle r:=u-qv}$

         ${\textstyle u:=v}$
         $$