त्रिकोणीय अपघटन

कंप्यूटर बीजगणित में, एक बहुपद प्रणाली का त्रिकोणीय अपघटन S सरल बहुपद प्रणालियों का एक सेट है S₁, ..., S_e जैसे कि एक बिंदु का समाधान है S यदि और केवल यदि यह किसी एक प्रणाली का समाधान है S₁, ..., S_e.

जब उद्देश्य के समाधान सेट का वर्णन करना है S इसके गुणांक क्षेत्र (गणित) के बीजीय समापन में, वे सरल प्रणालियाँ नियमित श्रृंखलाएँ हैं। यदि बहुपद प्रणालियों के गुणांक S₁, ..., S_e वास्तविक संख्याएं हैं, फिर वास्तविक समाधान हैं S त्रिकोणीय अपघटन द्वारा नियमित अर्ध-बीजीय प्रणालियों में प्राप्त किया जा सकता है। दोनों ही मामलों में, इन सरल प्रणालियों में से प्रत्येक में त्रिकोणीय आकार और उल्लेखनीय गुण हैं, जो शब्दावली को सही ठहराते हैं।

इतिहास

विशेषता सेट विधि पहला गुणनखंड-मुक्त एल्गोरिथ्म है, जिसे एक बीजगणितीय विविधता को समान घटकों में विघटित करने के लिए प्रस्तावित किया गया था। इसके अलावा, लेखक, मिस्टर वू यू वेन | वेन-सुन वू, ने इस पद्धति के कार्यान्वयन को महसूस किया और अपने 1987 के अग्रणी लेख में बहुपद समीकरणों को हल करने के लिए एक शून्य संरचना प्रमेय शीर्षक से प्रयोगात्मक डेटा की सूचना दी। इस कार्य को संदर्भ में रखने के लिए, आइए याद करें कि इस लेख के लिखे जाने के समय बीजगणितीय समुच्चय अपघटन का सामान्य विचार क्या था।

होने देना K बीजगणितीय रूप से बंद क्षेत्र हो और k का उपक्षेत्र हो K. उपसमुच्चय V ⊂ Kⁿ एक (affine) बीजगणितीय विविधता है k यदि कोई बहुपद समुच्चय मौजूद है F ⊂ k[x₁, ..., x_n] जैसे कि शून्य सेट V(F) ⊂ Kⁿ का F बराबर है V.

याद करें कि V अगर सभी बीजगणितीय किस्मों के लिए अप्रासंगिक कहा जाता है V₁, V₂ ⊂ Kⁿ रिश्ता V = V₁ ∪ V₂ का तात्पर्य है V = V₁ या V = V₂. पहला बीजगणितीय विविधता अपघटन परिणाम प्रसिद्ध लस्कर-नोथेर प्रमेय है जिसका अर्थ निम्नलिखित है।

प्रमेय (लास्कर - नोथेर)। प्रत्येक बीजगणितीय किस्म के लिए V ⊂ Kⁿ सूक्ष्म रूप से कई अलघुकरणीय बीजगणितीय किस्में मौजूद हैं V₁, ..., V_e ⊂ Kⁿ ऐसा कि हमारे पास है

$V=V_{1}\cup \cdots \cup V_{e}.$

इसके अलावा, अगर V_i ⊈ V_j के लिए रखता है 1 ≤ i < j ≤ e फिर सेट {V₁, ..., V_e} अद्वितीय है और इसका अलघुकरणीय अपघटन बनाता है V.

किस्में {{math|V₁, ..., V_e}उपरोक्त प्रमेय में } के अलघुकरणीय घटक कहलाते हैं V और एक अपघटन एल्गोरिथ्म के लिए एक प्राकृतिक आउटपुट के रूप में माना जा सकता है, या, दूसरे शब्दों में, एक एल्गोरिथ्म के लिए समीकरणों की एक प्रणाली को हल करने के लिए k[x₁, ..., x_n].

एक कंप्यूटर प्रोग्राम का नेतृत्व करने के लिए, इस एल्गोरिथम विनिर्देश को निर्धारित करना चाहिए कि इरेड्यूसिबल घटकों का प्रतिनिधित्व कैसे किया जाता है। इस तरह के एक एन्कोडिंग जोसेफ रिट द्वारा पेश किया गया है निम्नलिखित परिणाम के माध्यम से।

प्रमेय (रिट)। अगर V ⊂ Kⁿ एक गैर-खाली और अलघुकरणीय किस्म है तो कोई कम त्रिकोणीय सेट की गणना कर सकता है C आदर्श में निहित है $\langle F\rangle$ द्वारा उत्पन्न F में k[x₁, ..., x_n] और ऐसा है कि सभी बहुपद g में $\langle F\rangle$ छद्म-विभाजन w.r.t द्वारा शून्य को कम करता है C.

हम सेट कहते हैं C Ritt के प्रमेय में आदर्श का एक Ritt विशेषता सेट $\langle F\rangle$. त्रिकोणीय सेट की धारणा के लिए कृपया नियमित श्रृंखला देखें।

जोसेफ रिट ने फील्ड एक्सटेंशन पर बहुपद गुणनखंडन पर आधारित बहुपद प्रणालियों को हल करने के लिए एक विधि का वर्णन किया और प्रमुख आदर्शों के विशिष्ट सेटों की गणना की।

हालाँकि, इस पद्धति का व्यावहारिक कार्यान्वयन प्राप्त करना एक कठिन समस्या थी और बनी हुई है। 1980 के दशक में, जब वू की विशेषता सेट विधि की विधि पेश की गई थी, तो बहुपद गुणनखंडन एक सक्रिय शोध क्षेत्र था और इस विषय पर कुछ मूलभूत प्रश्न हाल ही में हल किए गए थे। आजकल, अधिकांश अनुप्रयोग समस्याओं को संसाधित करने के लिए एक बीजगणितीय विविधता को अप्रासंगिक घटकों में विघटित करना आवश्यक नहीं है, क्योंकि अपघटन की कमजोर धारणाएं, गणना करने के लिए कम खर्चीला, पर्याप्त हैं।

अभिलक्षण समुच्चय विधि Ritt's Theorem के निम्न संस्करण पर निर्भर करती है।

प्रमेय (वेन-त्सुन वू)। किसी परिमित बहुपद समुच्चय के लिए F ⊂ k[x₁, ..., x_n], कोई कम त्रिकोणीय सेट की गणना कर सकता है $C\subset \langle F\rangle$ ऐसा है कि सभी बहुपद g में F छद्म-विभाजन w.r.t द्वारा शून्य को कम कर देता है C.

विभिन्न अवधारणाओं और एल्गोरिदम ने वू वेनजुन | वेन-त्सुन वू के काम को आगे बढ़ाया। 1990 के दशक की शुरुआत में, एक नियमित श्रृंखला की धारणा, स्वतंत्र रूप से 1991 में माइकल काल्कब्रेनर द्वारा अपनी पीएचडी थीसिस और लू यांग और जिंगझोंग झांग द्वारा पेश की गई थी। महत्वपूर्ण एल्गोरिथम खोजों का नेतृत्व किया।

काल्कब्रेनर की दृष्टि में, एक बीजगणितीय विविधता के अलघुकरणीय घटकों के सामान्य शून्य का प्रतिनिधित्व करने के लिए नियमित श्रृंखलाओं का उपयोग किया जाता है। यांग और झांग के मूल कार्य में, उनका उपयोग यह तय करने के लिए किया जाता है कि क्या एक हाइपरसफेस एक अर्ध-विविधता (एक नियमित श्रृंखला द्वारा दी गई) को काटता है। नियमित शृंखलाओं में, वास्तव में, कई दिलचस्प गुण होते हैं और बीजगणितीय या अवकल समीकरणों की प्रणाली को विघटित करने के लिए कई एल्गोरिदम में महत्वपूर्ण धारणा है।

कई पत्रों में नियमित जंजीरों की जांच की गई है। इस विषय पर प्रचुर मात्रा में साहित्य को नियमित श्रृंखला की कई समकक्ष परिभाषाओं द्वारा समझाया जा सकता है। दरअसल, काल्कब्रेनर का मूल सूत्रीकरण यांग और झांग से काफी अलग है। इन दो धारणाओं के बीच एक पुल, काल्कब्रेनर और यांग और झांग का दृष्टिकोण, डोंगमिंग वांग के पेपर में दिखाई देता है। त्रिकोणीय अपघटन प्राप्त करने के लिए विभिन्न एल्गोरिदम उपलब्ध हैं V(F) कालब्रेनर के अर्थ में और डेनियल लाजार्ड और वू वेनजुन|वेन-त्सुन वू के अर्थ में। डैनियल लाजार्ड द्वारा लेक्स्ट्रियांगुलर एल्गोरिथम और ट्रायड एल्गोरिदम Marc Moreno Maza द्वारा विशेषता सेट विधि के साथ मिलकर विभिन्न कंप्यूटर बीजगणित प्रणालियों में उपलब्ध हैं, जिनमें Axiom (कंप्यूटर बीजगणित प्रणाली) और मेपल (सॉफ्टवेयर) शामिल हैं।

औपचारिक परिभाषाएँ

होने देना k एक क्षेत्र हो और x₁ < ... < x_n आदेशित चर हो। हम द्वारा निरूपित करते हैं R = k[x₁, ..., x_n] संगत बहुपद वलय। के लिए F ⊂ R, बहुपद समीकरणों की एक प्रणाली के रूप में माना जाता है, बीजगणितीय बंद होने पर त्रिकोणीय अपघटन के दो विचार हैं k. सबसे पहले बीजगणितीय सेट के केवल सामान्य बिंदुओं का प्रतिनिधित्व करके आलसी रूप से विघटित करना है V(F) कालब्रेनर के तथाकथित अर्थ में।

${\sqrt {(F)}}=\bigcap _{i=1}^{e}{\sqrt {\mathrm {sat} (T_{i})}}.$

दूसरा स्पष्ट रूप से सभी बिंदुओं का वर्णन करना है V(F) डैनियल लाजार्ड और वू वेनजुन | वेन-सुन वू के तथाकथित अर्थ में।

$V(F)=\bigcup _{i=1}^{e}W(T_{i}).$

दोनों ही मामलों में T₁, ..., T_e निश्चित रूप से कई नियमित श्रृंखलाएं हैं R और ${\sqrt {\mathrm {sat} (T_{i})}}$ के संतृप्त आदर्श के मूलांक को दर्शाता है T_i जबकि W(T_i) के अर्ध-घटक को दर्शाता है T_i. कृपया इन धारणाओं की परिभाषा के लिए नियमित श्रृंखला देखें।

अभी से मान लीजिए k एक वास्तविक बंद क्षेत्र है। विचार करना S बहुपदों के साथ एक अर्ध-बीजगणितीय प्रणाली R. वहां है निश्चित रूप से कई नियमित अर्ध-बीजगणितीय प्रणालियाँ S₁, ..., S_e ऐसा कि हमारे पास है

$Z_{\mathbf {k} }(S)=Z_{\mathbf {k} }(S_{1})\cup \cdots \cup Z_{\mathbf {k} }(S_{e})$

कहाँ Z_k(S) के बिंदुओं को दर्शाता है kⁿ जो हल करता है S. नियमित अर्ध-बीजीय प्रणाली S₁, ..., S_e अर्ध-बीजगणितीय प्रणाली का त्रिकोणीय अपघटन बनाते हैं S.

उदाहरण

निरूपित Q परिमेय संख्या क्षेत्र। में $Q[x,y,z]$ परिवर्तनीय क्रम के साथ $x>y>z$, निम्नलिखित बहुपद प्रणाली पर विचार करें:

$S={\begin{cases}x^{2}+y+z=1\\x+y^{2}+z=1\\x+y+z^{2}=1\end{cases}}$

मेपल (सॉफ्टवेयर) कोड के अनुसार:

with(RegularChains):
R := PolynomialRing([x, y, z]):
sys := {x^2+y+z-1, x+y^2+z-1, x+y+z^2-1}:
l := Triangularize(sys, R):
map(Equations, l, R);

के समाधान सेट का एक संभावित त्रिकोणीय अपघटन S RegularChains लाइब्रेरी का उपयोग करने के साथ है:

${\begin{cases}z=0\\y=1\\x=0\end{cases}}\cup {\begin{cases}z=0\\y=0\\x=1\end{cases}}\cup {\begin{cases}z=1\\y=0\\x=0\end{cases}}\cup {\begin{cases}z^{2}+2z-1=0\\y=z\\x=z\end{cases}}$

यह भी देखें

• वू की विशेषता सेट की विधि
• नियमित श्रृंखला
• नियमित अर्ध-बीजगणितीय प्रणाली