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

chye{{Short description|Algorithm on systems of polynomials}}
[[कंप्यूटर बीजगणित]] में, एक [[बहुपद प्रणाली|बहुपद {{mvar| S}}]] का त्रिकोणीय अपघटन सरल बहुपद प्रणालियों का {{math|''S''<sub>1</sub>, ..., ''S<sub>e</sub>''}} एक समुच्चय है जैसे कि एक बिंदु का समाधान है {{mvar|S}} यदि और केवल यदि यह किसी एक प्रणाली का समाधान है {{math|''S''<sub>1</sub>, ..., ''S<sub>e</sub>''}}.

जब उद्देश्य के समाधान सेट का वर्णन करना है {{mvar|S}} इसके गुणांक [[क्षेत्र (गणित)]] के बीजीय समापन में, वे सरल प्रणालियाँ [[नियमित श्रृंखला]]एँ हैं। यदि बहुपद प्रणालियों के गुणांक {{math|''S''<sub>1</sub>, ..., ''S<sub>e</sub>''}} वास्तविक संख्याएं हैं, फिर वास्तविक समाधान हैं  {{mvar|S}} त्रिकोणीय अपघटन द्वारा नियमित अर्ध-बीजीय प्रणालियों में प्राप्त किया जा सकता है। दोनों ही मामलों में, इन सरल प्रणालियों में से प्रत्येक में त्रिकोणीय आकार और उल्लेखनीय गुण हैं, जो शब्दावली को सही ठहराते हैं।

== इतिहास ==
विशेषता सेट विधि पहला गुणनखंड-मुक्त एल्गोरिथ्म है, जिसे एक बीजगणितीय विविधता को समान घटकों में विघटित करने के लिए प्रस्तावित किया गया था। इसके अलावा, लेखक, [[मिस्टर वू यू वेन]] | वेन-सुन वू, ने इस पद्धति के कार्यान्वयन को महसूस किया और अपने 1987 के अग्रणी लेख में बहुपद समीकरणों को हल करने के लिए एक शून्य संरचना प्रमेय शीर्षक से प्रयोगात्मक डेटा की सूचना दी।<ref>Wu, W. T. (1987). A zero structure theorem for polynomial equations solving. MM Research Preprints, 1, 2–12</ref> इस कार्य को संदर्भ में रखने के लिए, आइए याद करें कि इस लेख के लिखे जाने के समय बीजगणितीय समुच्चय अपघटन का सामान्य विचार क्या था।

होने देना {{math|'''K'''}} बीजगणितीय रूप से बंद क्षेत्र हो और {{math|'''k'''}} का उपक्षेत्र हो {{math|'''K'''}}. उपसमुच्चय {{math|''V'' ⊂ '''K'''<sup>''n''</sup>}} एक (affine) बीजगणितीय विविधता है {{math|'''k'''}} यदि कोई बहुपद समुच्चय मौजूद है {{math|''F'' ⊂ '''k'''[''x''<sub>1</sub>, ..., ''x<sub>n</sub>'']}} जैसे कि शून्य सेट {{math|''V''(''F'') ⊂ '''K'''<sup>''n''</sup>}} का {{mvar|F}} बराबर है {{mvar|V}}.

याद करें कि {{mvar|V}} अगर सभी बीजगणितीय किस्मों के लिए अप्रासंगिक कहा जाता है {{math|''V''<sub>1</sub>, ''V''<sub>2</sub> ⊂ '''K'''<sup>''n''</sup>}} रिश्ता {{math|''V'' {{=}} ''V''<sub>1</sub> ∪ ''V''<sub>2</sub>}} का तात्पर्य है {{math|''V'' {{=}} ''V''<sub>1</sub>}} या {{math|''V'' {{=}} ''V''<sub>2</sub>}}. पहला बीजगणितीय विविधता अपघटन परिणाम प्रसिद्ध लस्कर-नोथेर प्रमेय है जिसका अर्थ निम्नलिखित है।

: प्रमेय (लास्कर - नोथेर)। प्रत्येक बीजगणितीय किस्म के लिए {{math|''V'' ⊂ '''K'''<sup>''n''</sup>}} सूक्ष्म रूप से कई अलघुकरणीय बीजगणितीय किस्में मौजूद हैं {{math|''V''<sub>1</sub>, ..., ''V<sub>e</sub>'' ⊂ '''K'''<sup>''n''</sup>}} ऐसा कि हमारे पास है
::<math>  V = V_1 \cup \cdots \cup V_e. </math>
: इसके अलावा, अगर  {{math|''V<sub>i</sub>'' ⊈ ''V<sub>j</sub>''}} के लिए रखता है {{math|1 ≤ ''i'' < ''j'' ≤ ''e''}} फिर सेट {{math|{''V''<sub>1</sub>, ..., ''V<sub>e</sub>''} }} अद्वितीय है और इसका अलघुकरणीय अपघटन बनाता है {{mvar|V}}.

किस्में {{math|''V''<sub>1</sub>, ..., ''V<sub>e</sub>''}उपरोक्त प्रमेय में } के अलघुकरणीय घटक कहलाते हैं {{mvar|V}} और एक अपघटन एल्गोरिथ्म के लिए एक प्राकृतिक आउटपुट के रूप में माना जा सकता है, या, दूसरे शब्दों में, एक एल्गोरिथ्म के लिए समीकरणों की एक प्रणाली को हल करने के लिए {{math|'''k'''[''x''<sub>1</sub>, ..., ''x<sub>n</sub>'']}}.

एक कंप्यूटर प्रोग्राम का नेतृत्व करने के लिए, इस एल्गोरिथम विनिर्देश को निर्धारित करना चाहिए कि इरेड्यूसिबल घटकों का प्रतिनिधित्व कैसे किया जाता है। इस तरह के एक एन्कोडिंग [[जोसेफ रिट]] द्वारा पेश किया गया है<ref>Ritt, J. (1966). Differential Algebra. New York, Dover Publications</ref> निम्नलिखित परिणाम के माध्यम से।

: प्रमेय (रिट)। अगर {{math|''V'' ⊂ '''K'''<sup>''n''</sup>}} एक गैर-खाली और अलघुकरणीय किस्म है तो कोई कम त्रिकोणीय सेट की गणना कर सकता है {{mvar|C}} आदर्श में निहित है <math>\langle F \rangle</math> द्वारा उत्पन्न {{mvar|F}} में {{math|'''k'''[''x''<sub>1</sub>, ..., ''x<sub>n</sub>'']}} और ऐसा है कि सभी बहुपद {{mvar|g}} में <math>\langle F \rangle</math> छद्म-विभाजन w.r.t द्वारा शून्य को कम करता है {{mvar|C}}.

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

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

हालाँकि, इस पद्धति का व्यावहारिक कार्यान्वयन प्राप्त करना एक कठिन समस्या थी और बनी हुई है। 1980 के दशक में, जब वू की विशेषता सेट विधि की विधि पेश की गई थी, तो बहुपद गुणनखंडन एक सक्रिय शोध क्षेत्र था और इस विषय पर कुछ मूलभूत प्रश्न हाल ही में हल किए गए थे।<ref>A. M. Steel Conquering inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic</ref>
आजकल, अधिकांश अनुप्रयोग समस्याओं को संसाधित करने के लिए एक बीजगणितीय विविधता को अप्रासंगिक घटकों में विघटित करना आवश्यक नहीं है, क्योंकि अपघटन की कमजोर धारणाएं, गणना करने के लिए कम खर्चीला, पर्याप्त हैं।

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

: प्रमेय (वेन-त्सुन वू)। किसी परिमित बहुपद समुच्चय के लिए {{math|''F'' ⊂ '''k'''[''x''<sub>1</sub>, ..., ''x<sub>n</sub>'']}}, कोई कम त्रिकोणीय सेट की गणना कर सकता है <math>C \subset \langle F \rangle</math> ऐसा है कि सभी बहुपद {{mvar|g}} में {{mvar|F}} छद्म-विभाजन w.r.t द्वारा शून्य को कम कर देता है {{mvar|C}}.

विभिन्न अवधारणाओं और एल्गोरिदम ने वू वेनजुन | वेन-त्सुन वू के काम को आगे बढ़ाया। 1990 के दशक की शुरुआत में, एक नियमित श्रृंखला की धारणा, स्वतंत्र रूप से 1991 में माइकल काल्कब्रेनर द्वारा अपनी पीएचडी थीसिस और लू यांग और जिंगझोंग झांग द्वारा पेश की गई थी।<ref>Yang, L., Zhang, J. (1994). [http://www.iaea.org/inis/collection/NCLCollectionStore/_Public/22/086/22086436.pdf Searching dependency between algebraic equations: an algorithm applied to automated reasoning]. Artificial Intelligence in Mathematics, pp.&nbsp;14715,  Oxford University Press.</ref> महत्वपूर्ण एल्गोरिथम खोजों का नेतृत्व किया।

काल्कब्रेनर की दृष्टि में,<ref>M. Kalkbrener: A Generalized Euclidean Algorithm for Computing Triangular Representations of Algebraic Varieties. J. Symb. Comput. 15(2): 143&ndash;167 (1993)</ref> एक बीजगणितीय विविधता के अलघुकरणीय घटकों के सामान्य शून्य का प्रतिनिधित्व करने के लिए नियमित श्रृंखलाओं का उपयोग किया जाता है। यांग और झांग के मूल कार्य में, उनका उपयोग यह तय करने के लिए किया जाता है कि क्या एक हाइपरसफेस एक अर्ध-विविधता (एक नियमित श्रृंखला द्वारा दी गई) को काटता है। नियमित शृंखलाओं में, वास्तव में, कई दिलचस्प गुण होते हैं और बीजगणितीय या अवकल समीकरणों की प्रणाली को विघटित करने के लिए कई एल्गोरिदम में महत्वपूर्ण धारणा है।

कई पत्रों में नियमित जंजीरों की जांच की गई है।<ref>S.C. Chou and X.S. Gao. On the dimension of an arbitrary ascending chain.  Chinese Bull. of Sci., 38:799--804, 1991.</ref><ref>Michael Kalkbrener. Algorithmic properties of polynomial rings. J. Symb. Comput.}, 26(5):525--581, 1998.</ref><ref>P. Aubry, D. Lazard, M. Moreno Maza. [http://www.sciencedirect.com/science/article/pii/S0747717199902699 On the theories of triangular sets]. Journal of Symbolic Computation, 28(1&ndash;2):105&ndash;124, 1999.</ref>
इस विषय पर प्रचुर मात्रा में साहित्य को नियमित श्रृंखला की कई समकक्ष परिभाषाओं द्वारा समझाया जा सकता है। दरअसल, काल्कब्रेनर का मूल सूत्रीकरण यांग और झांग से काफी अलग है। इन दो धारणाओं के बीच एक पुल, काल्कब्रेनर और यांग और झांग का दृष्टिकोण, डोंगमिंग वांग के पेपर में दिखाई देता है।<ref>D. Wang. Computing Triangular Systems and Regular Systems. Journal of Symbolic Computation 30(2) (2000) 221&ndash;236</ref>
त्रिकोणीय अपघटन प्राप्त करने के लिए विभिन्न एल्गोरिदम उपलब्ध हैं {{math|''V''(''F'')}} कालब्रेनर के अर्थ में और [[डेनियल लाजार्ड]] और वू वेनजुन|वेन-त्सुन वू के अर्थ में। डैनियल लाजार्ड द्वारा लेक्स्ट्रियांगुलर एल्गोरिथम<ref>D. Lazard, ''Solving zero-dimensional algebraic systems''. Journal of Symbolic Computation '''13''', 1992</ref> और ट्रायड एल्गोरिदम [http://www.csd.uwo.ca/~moreno/ Marc Moreno Maza] द्वारा<ref>M. Moreno Maza: On triangular decomposition of algebraic varieties. MEGA 2000 (2000).</ref> विशेषता सेट विधि के साथ मिलकर विभिन्न कंप्यूटर बीजगणित प्रणालियों में उपलब्ध हैं, जिनमें Axiom (कंप्यूटर बीजगणित प्रणाली) और [[मेपल (सॉफ्टवेयर)]] शामिल हैं।

== औपचारिक परिभाषाएँ ==
होने देना {{math|'''k'''}} एक क्षेत्र हो और {{math|''x''<sub>1</sub> < ... < ''x<sub>n</sub>''}} आदेशित चर हो। हम द्वारा निरूपित करते हैं {{math|''R'' {{=}} '''k'''[''x''<sub>1</sub>, ..., ''x<sub>n</sub>'']}} संगत बहुपद वलय। के लिए {{math|''F'' ⊂ ''R''}}, बहुपद समीकरणों की एक प्रणाली के रूप में माना जाता है, बीजगणितीय बंद होने पर त्रिकोणीय अपघटन के दो विचार हैं {{math|'''k'''}}. सबसे पहले बीजगणितीय सेट के केवल [[सामान्य बिंदु]]ओं का प्रतिनिधित्व करके आलसी रूप से विघटित करना है {{math|''V''(''F'')}} कालब्रेनर के तथाकथित अर्थ में।

: <math>\sqrt{(F)}=\bigcap_{i=1}^{e}\sqrt{\mathrm{sat}(T_i)}.</math>
दूसरा स्पष्ट रूप से सभी बिंदुओं का वर्णन करना है {{math|''V''(''F'')}} डैनियल लाजार्ड और वू वेनजुन | वेन-सुन वू के तथाकथित अर्थ में।

: <math>V(F)=\bigcup_{i=1}^{e}W(T_i).</math>
दोनों ही मामलों में {{math|''T''<sub>1</sub>, ..., ''T<sub>e</sub>''}} निश्चित रूप से कई नियमित श्रृंखलाएं हैं {{mvar|R}} और <math>\sqrt{\mathrm{sat}(T_i)}</math> के संतृप्त आदर्श के मूलांक को दर्शाता है {{math|''T<sub>i</sub>''}} जबकि {{math|''W''(''T<sub>i</sub>'')}} के अर्ध-घटक को दर्शाता है {{math|''T<sub>i</sub>''}}. कृपया इन धारणाओं की परिभाषा के लिए नियमित श्रृंखला देखें।

अभी से मान लीजिए {{math|'''k'''}} एक [[वास्तविक बंद क्षेत्र]] है। विचार करना {{mvar|S}} बहुपदों के साथ एक अर्ध-बीजगणितीय प्रणाली {{mvar|R}}. वहां है<ref>Changbo Chen, James H. Davenport, John P. May, Marc Moreno-Maza, Bican Xia, Rong Xiao. [http://www.sciencedirect.com/science/article/pii/S0747717111002070/pdf?md5=9344a2f6467b91cc32bcef52f9275ab2&pid=1-s2.0-S0747717111002070-main.pdf&_valck=1 Triangular decomposition of semi-algebraic systems].  Proceedings of 2010 International Symposium on Symbolic and Algebraic Computation (ISSAC 2010), ACM Press, pp. 187--194, 2010.</ref> निश्चित रूप से कई नियमित अर्ध-बीजगणितीय प्रणालियाँ {{math|''S''<sub>1</sub>, ..., ''S<sub>e</sub>''}} ऐसा कि हमारे पास है

:<math>Z_{\mathbf{k}}(S) = Z_{\mathbf{k}}(S_1) \cup \cdots \cup Z_{\mathbf{k}}(S_e) </math>
कहाँ {{math|''Z''<sub>'''k'''</sub>(''S'')}} के बिंदुओं को दर्शाता है {{math|'''k'''<sup>''n''</sup>}} जो हल करता है {{mvar|S}}. नियमित अर्ध-बीजीय प्रणाली {{math|''S''<sub>1</sub>, ..., ''S<sub>e</sub>''}} अर्ध-बीजगणितीय प्रणाली का त्रिकोणीय अपघटन बनाते हैं {{mvar|S}}.

== उदाहरण ==
निरूपित {{mvar|Q}} परिमेय संख्या क्षेत्र। में <math>Q[x, y, z]</math> परिवर्तनीय क्रम के साथ <math>x > y > z</math>, निम्नलिखित बहुपद प्रणाली पर विचार करें:

:<math>S = 
\begin{cases} x^2 + y + z = 1 \\ x + y^2 + z = 1 \\ x + y + z^2 = 1 \end{cases}</math>

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

के समाधान सेट का एक संभावित त्रिकोणीय अपघटन {{mvar|S}} [http://www.regularchains.org/ RegularChains] लाइब्रेरी का उपयोग करने के साथ है:

:<math>\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}
</math><br />
== यह भी देखें ==
* वू की विशेषता सेट की विधि
* नियमित श्रृंखला
* नियमित अर्ध-बीजगणितीय प्रणाली

== संदर्भ ==

{{Reflist}}
[[Category: समीकरण]] [[Category: बीजगणित]] [[Category: बहुपदों]] [[Category: बीजगणितीय ज्यामिति]] [[Category: कंप्यूटर बीजगणित]] [[Category: कंप्यूटर बीजगणित प्रणाली]] 



[[Category: Machine Translated Page]]
[[Category:Created On 03/03/2023]]