रैखिक समीकरणों के पूर्णांक प्रणाली को हल करने के लिए प्रतियोगिता

हेलो, हैबरडग।



मैं गति के लिए पूर्णांक SLU को हल करने के लिए एक प्रतियोगिता में भाग लेने का प्रस्ताव करता हूं। मैं आपको तुरंत चेतावनी देना चाहता हूं कि एक शौकिया प्रतियोगिता और पुरस्कार की उम्मीद नहीं है, इसलिए मैं उन लोगों को आमंत्रित करता हूं जो इस प्रतियोगिता को दिलचस्प पाते हैं और जिनके पास इसके लिए खाली समय है। प्रतियोगिता इस दृष्टिकोण से उपयोगी हो सकती है कि कुछ लोग ऐसी समस्याओं को काफी प्रभावी ढंग से हल करने में सक्षम हैं।







मैं खेल प्रोग्रामिंग में शौकिया प्रतियोगिताएं जारी रखता हूं। कई लोगों को पिछली प्रतियोगिता पसंद आई और मैंने यह भी वादा किया कि अगला एक समानांतर कंप्यूटिंग में होगा, लेकिन तकनीकी कारणों से मुझे इस तरह की प्रतियोगिता को अनिश्चित काल के लिए स्थगित करना होगा।



एक साल पहले, मैंने गति से मैट्रिक्स को गुणा करने का कार्य प्रस्तावित किया था। परिणाम काफी दिलचस्प हैं: हमने 100 से अधिक बार त्वरण हासिल किया है। अब रैखिक बीजगणित की एक और समस्या प्रस्तावित है - रैखिक समीकरणों के पूर्णांक प्रणाली का समाधान Ax = b।



मैट्रिक्स ए और वेक्टर बी में पूर्णांक होते हैं जो एक संकेत के साथ 32 बिट्स में फिट होते हैं (-2 ³¹ से 2 ³¹ -1 तक)। इस समस्या का उत्तर एक तर्कसंगत वेक्टर x है। चूंकि उत्तर के अंश और हर बहुत लंबे हो सकते हैं, इसलिए लंबे अंकगणित वाले पुस्तकालयों का उपयोग करने के लिए मना नहीं किया जाता है।



प्रणाली का अधिकतम आयाम n = 200 प्रस्तावित है। लेकिन अगर प्रतिभागियों में से कोई एक प्रोग्राम लिखता है जो बहुत तेज़ है, तो यह प्रतिबंध बढ़ा दिया जाएगा। तथ्य यह है कि पूर्णांक में सामान्य गॉस विधि, "माथे", एक यादृच्छिक मैट्रिक्स पर इस तरह के प्रतिबंध के साथ, 10 मिनट के लिए काम करता है। बेशक, यह तेजी से लिखा जा सकता है।



किसी को भी दिलचस्पी है, कृपया प्रतियोगिता का विवरण पढ़ें।



दुर्भाग्य से, मैं अकेले प्रतियोगिता आयोजित करना जारी रखता हूं, इसलिए प्रतिभागियों के लिए गंभीर प्रतिबंध उत्पन्न होते हैं। मेरे पास केवल विंडोज 7 (32 बिट्स) के तहत कार्यक्रमों का परीक्षण करने का अवसर है, इसलिए आप या तो EXE फाइलें या सीपीपी स्रोत भेज सकते हैं जो एक काम करने वाली मशीन पर संकलित किया जाएगा (इस मामले में केवल एमपीआईआर पुस्तकालय उपलब्ध है)। मेरे पास प्रतियोगिता आयोजित करने का कोई अन्य तरीका नहीं है। हालांकि, प्रतिभागियों के मैट्रिस के गुणा के लिए प्रतियोगिता के लिए एक समान प्रतिबंध नहीं रुका।



प्रतियोगिता का एक अच्छा परिणाम, मुझे कार्यान्वयन दिखाई देता है, 5-10 सेकंड में फिट होता है।

इसकी आवश्यकता क्यों है?

पूर्णांक प्रणाली के सटीक समाधान के बारे में जानकारी की खोज की प्रक्रिया में, मैंने पाया कि कुछ लोग इस समस्या को हल कर सकते हैं। मैं खुद इस क्षेत्र का विशेषज्ञ नहीं हूं, लेकिन अपने शोध में मैं पूर्णांक SLU के साथ आया, जिसे बहुत जल्दी हल करने की आवश्यकता है। यह प्रतियोगिता यह समझने में मदद कर सकती है कि पूर्णांक प्रणाली को हल करने की गति में क्या सफलता प्राप्त की जा सकती है और इस मामले में हम सामान्य रूप से क्या उम्मीद कर सकते हैं। प्रतियोगिता का विजेता एक अलग लेख लिखकर अपना अनुभव साझा कर सकता है, जो कम्प्यूटेशनल रैखिक बीजगणित के क्षेत्र में काम करने वाले लोगों के लिए बहुत उपयोगी होगा। रनेट में ऐसे लेखों को खोजना संभव नहीं था, इसलिए इस अंतर को भरना प्रस्तावित है।



यदि यह पता चला (प्रतियोगिता के अंत के बाद) कि मेरी विधियां प्रतिभागियों के तरीकों से तेज हैं, तो मैं खुद इस तरह का लेख लिखूंगा। प्रतियोगिता के अंत तक, मैं इसमें हस्तक्षेप नहीं करता।



बेशक, मैं अपने लिए विशुद्ध रूप से व्यक्तिगत लाभ की तलाश में नहीं हूं और मैं किसी और का कोड चोरी करने और अपने स्वयं के प्रयोजनों के लिए उपयोग नहीं करने जा रहा हूं। यह पहली बार नहीं है जब मैं किसी प्रतियोगिता का आयोजन कर रहा हूं, और ऐसा लगता है कि किसी ने भी अभी तक कोई शिकायत नहीं की है। इसलिए, इस बारे में घटक जटिल नहीं हो सकते हैं :)



सौभाग्य है