রৈখিক বীজগণিত/বিষয়: গাউস পদ্ধতির গতি

রৈখিক বীজগণিত
← বিষয়: নেটওয়ার্ক বিশ্লেষণ	বিষয়: গাউস পদ্ধতির গতি	ভেক্টর জগত →

আমরা এই বইয়ে রৈখিক সমীকরণ জোট সমাধানের জন্য গাউসের পদ্ধতি ব্যবহার করছি কারণ এটি বোঝা সহজ, সহজেই প্রমাণ করা যায় যে এটি সঠিক উত্তর দেয় এবং এটি দ্রুতগতির। এটি দ্রুত কারণ, আমাদের প্রয়োজনীয় হাতে-কলমে করা সমস্ত হিসাবের ক্ষেত্রে, আমরা মাত্র কয়েকটি ধাপে এবং কয়েক মিনিটের মধ্যেই উত্তর পেয়েছি। তবে, বাস্তবে যে বিজ্ঞানী এবং প্রকৌশলীরা রৈখিক সমীকরণ জোট সমাধান করেন, তাদের এমন একটি পদ্ধতি প্রয়োজন যা বড় সিস্টেমের (যেমন ১,০০০ বা ১০,০০০ কিংবা এমনকি ১,০০,০০০ সমীকরণ বিশিষ্ট) জন্য যথেষ্ট দ্রুত। এই সিস্টেমগুলো কম্পিউটারে সমাধান করা হয়, তাই মেশিনের গতি এক্ষেত্রে সহায়ক। তবে তা সত্ত্বেও, ব্যবহৃত পদ্ধতির গতি একটি প্রধান বিবেচ্য বিষয় এবং কখনো কখনো এটি কোন ধরনের সমস্যাগুলো সমাধান করা যাবে তার সীমাবদ্ধতা নির্ধারণ করে দেয়।

একটি অ্যালগরিদমের গতি সাধারণত মাপা হয়, ইনপুট ডেটাসেটের আকার বৃদ্ধির সাথে সাথে সমস্যাটি সমাধান করতে প্রয়োজনীয় সময় কীভাবে বৃদ্ধি পায় তা নির্ণয় করার মাধ্যমে। অর্থাৎ, যদি আমরা ইনপুট ডেটার আকার দশগুণ বাড়াই, ধরুন ১০০০-সমীকরণের একটি সিস্টেম থেকে ১০,০০০-সমীকরণের সিস্টেমে, বা ১০,০০০ থেকে ১,০০,০০০-এ, তবে অ্যালগরিদমটির কত বেশি সময় লাগবে? গৃহীত সময় কি দশগুণ, একশগুণ নাকি হাজারগুণ বাড়বে? অ্যালগরিদমের নেওয়া সময় কি ডেটাসেটের আকারের সমানুপাতিক, নাকি সেই আকারের বর্গের, অথবা ঘনফলের সমানুপাতিক, ইত্যাদি?

এখানে ফোরট্রান প্রোগ্রামিং ভাষায় লেখা গাউসের পদ্ধতির কোডের একটি খণ্ডাংশ দেওয়া হলো। রৈখিক সমীকরণ জোটের সহগগুলো $N \times N$ অ্যারে A-তে সংরক্ষিত আছে এবং ধ্রুবকগুলো $N \times 1$ অ্যারে B-তে সংরক্ষিত আছে। $1$ থেকে $N$ এর মধ্যকার প্রতিটি রো এর জন্য এই প্রোগ্রামটি ইতোমধ্যে পিভট ভুক্তি $A (R O W, C O L)$ খুঁজে পেয়েছে। এখন এটি পিভট করবে।

- P I V I N V \cdot ρ_{R O W} + ρ_{i}

(এই কোড খণ্ডাংশটি শুধুমাত্র উদাহরণ হিসেবে দেওয়া হয়েছে এবং এটি অসম্পূর্ণ। উদাহরণস্বরূপ, গাউসের পদ্ধতির নির্ভুলতা নিয়ে পরবর্তী বিষয়টি দেখুন। তবুও, এই খণ্ডাংশটি আমাদের উদ্দেশ্যে কাজ করবে, কারণ সমস্ত পরীক্ষা এবং উপ-ক্ষেত্র সহ সম্পূর্ণ সংস্করণগুলোর বিশ্লেষণ আরো জটিল হলেও, তা মূলত একই ফলাফল দেয়।)

PIVINV=1./A(ROW,COL)
DO 10 I=ROW+1, N
DO 20 J=I, N
A(I,J)=A(I,J)-PIVINV*A(ROW,J)
20 CONTINUE
B(J)=B(J)-PIVINV*B(ROW)
10 CONTINUE

সবচেয়ে বাইরের লুপটি (যা এখানে দেখানো হয়নি) $N - 1$ সারি পর্যন্ত চলে। এই সারিগুলোর প্রতিটির জন্য, প্রদর্শিত লুপগুলো A এর সেই ভুক্তিগুলোর উপর গাণিতিক কাজ সম্পন্ন করে যেগুলো পিভট ভুক্তির নিচে এবং ডানদিকে অবস্থিত (এবং B এর ভুক্তিগুলোতেও কাজ করে, তবে বিশ্লেষণ সহজ করার জন্য আমরা সেই অপারেশনগুলো গণনা করব না---অনুশীলনী দেখুন )। আমরা ধরে নিচ্ছি যে পিভট সাধারণ স্থানেই পাওয়া গেছে, অর্থাৎ, $C O L = R O W$ (আগের মতোই, সাধারণ ক্ষেত্রের বিশ্লেষণ আরও জটিল হলেও, মূলত তা একই ফলাফল দেয়)। এর অর্থ হলো, গাণিতিক কাজ করার জন্য $(N - R O W)^{2}$ টি ভুক্তি রয়েছে। গড়ে, রো হবে $N / 2$ । সুতরাং আমরা অনুমান করতে পারি যে উপরের নেস্টেড লুপগুলো প্রায় $(N / 2)^{2}$ বার চলবে, অর্থাৎ, এগুলো সমীকরণ সংখ্যার বর্গের সমানুপাতিক সময়ে চলবে। যে বাইরের লুপটি দেখানো হয়নি তা বিবেচনায় নিলে, আমরা এই অনুমানে পৌঁছাই যে অ্যালগরিদমটির চলার সময় সমীকরণ সংখ্যার ঘনের সমানুপাতিক।

যেসব অ্যালগরিদম ডেটাসেটের আকারের সরাসরি সমানুপাতিক সময়ে চলে সেগুলো দ্রুতগতির; যেসব অ্যালগরিদম ডেটাসেটের আকারের বর্গের সমানুপাতিক সময়ে চলে সেগুলো অপেক্ষাকৃত কম দ্রুতগতির হলেও সাধারণত বেশ ব্যবহারযোগ্য; এবং যেসব অ্যালগরিদম ডেটাসেটের আকারের ঘনের সমানুপাতিক সময়ে চলে সেগুলোর গতিও বেশ যুক্তিসঙ্গত।

এই ধরনের গতির অনুমানগুলো থেকে একটি অ্যালগরিদম গড়ে কত দ্রুত বা ধীর গতিতে চলতে পারে তা বোঝার একটি ভালো উপায় পাওয়া যায়। তবে, সিস্টেমের এমন কিছু বিশেষ ক্ষেত্র রয়েছে যেখানে উপরের গাউসের পদ্ধতির কোডটি বিশেষভাবে দ্রুত কাজ করে, তাই একটি সমস্যার এমন কিছু নিয়ামক থাকতে পারে যা একে এই ধরনের সমাধানের জন্য বিশেষভাবে উপযোগী করে তোলে।

বাস্তবে, কম্পিউটার বীজগণিত সিস্টেমে বা আদর্শ প্যাকেজগুলোতে যে কোড পাওয়া যায়, তা গাউসের পদ্ধতির একটি ভিন্ন রূপ প্রয়োগ করে, যাকে ত্রিভুজাকার উৎপাদকে বিশ্লেষণ বলা হয়। এই পদ্ধতিটি বর্ণনা করার জন্য ম্যাট্রিক্স বীজগণিতের ভাষা প্রয়োজন, যা আমরা তৃতীয় অধ্যায়ের আগে দেখতে পাব না। তা সত্ত্বেও, উপরের কোডটি ধারণাগতভাবে অ্যাপ্লিকেশনগুলোতে সাধারণত ব্যবহৃত কোডের বেশ কাছাকাছি।

রৈখিক সমীকরণ জোট সমাধানের জন্য প্রয়োজনীয় সময়ের ক্ষেত্রে কিছু তাত্ত্বিক গতি-বৃদ্ধি সাধিত হয়েছে। গাউসের পদ্ধতি ছাড়াও এমন কিছু অ্যালগরিদম আবিষ্কৃত হয়েছে যেগুলোর সময় ডেটাসেটের আকারের ঘনের সমানুপাতিক নয়, বরং (প্রায়) $2.7$ ঘাতের সমানুপাতিক (এটি এখনো সক্রিয় গবেষণার অধীন, তাই সময়ের সাথে সাথে এই সূচক কিছুটা কমে আসতে পারে)। যাইহোক, এই তাত্ত্বিক উন্নতিগুলো এখনো ব্যাপকভাবে ব্যবহৃত হয়নি, এর আংশিক কারণ হলো, গাউসের পদ্ধতিকে ছাড়িয়ে যাওয়ার জন্য নতুন পদ্ধতিগুলোতে বেশ বড় ডেটাসেটের প্রয়োজন হয় (যদিও এগুলো অনেক বড় সেটের ক্ষেত্রে গাউসের পদ্ধতিকে ছাড়িয়ে যাবে, তবে কিছু প্রারম্ভিক অতিরিক্ত কাজের কারণে বাস্তবে এ পর্যন্ত সমাধান করা সিস্টেমগুলোতে এগুলো গাউসের পদ্ধতির চেয়ে দ্রুত হতে পারে না)।

অনুশীলনী

সমস্যা ১

কম্পিউটার সিস্টেমগুলো এলোমেলো বা র্যান্ডম সংখ্যা তৈরি করতে পারে (অবশ্যই এগুলো কেবল ছদ্ম-র্যান্ডম, কারণ এগুলো কোনো নির্দিষ্ট অ্যালগরিদম দ্বারা তৈরি হয়; তবে প্রাপ্ত সংখ্যার অনুক্রমটি আপাত র্যান্ডমনেসের জন্য বেশ কয়েকটি যুক্তিযুক্ত পরিসংখ্যানগত পরীক্ষায় উত্তীর্ণ হয়)।

একটি $5 \times 5$ অ্যারে র্যান্ডম সংখ্যা (ধরা যাক, $[0..1)$ ব্যবধিতে) দিয়ে পূরণ করুন। এটি ব্যতিক্রমী বা সিঙ্গুলার কিনা তা পরীক্ষা করতে গাউসের পদ্ধতি প্রয়োগ করুন। এই পরীক্ষাটি দশবার পুনরাবৃত্তি করুন। সিঙ্গুলার ম্যাট্রিক্স কি ঘন ঘন পাওয়া যায় নাকি বিরল (এই অর্থে)?
র্যান্ডম সংখ্যার দশটি $5 \times 5$ অ্যারে সমাধান করতে কম্পিউটারের কত সময় লাগে তা পরিমাপ করুন। গড় সময় বের করুন। (লক্ষ্য করুন যে, কিছু সিস্টেম খুব দ্রুত সিঙ্গুলার হিসেবে চিহ্নিত হতে পারে, যেমন প্রথম সারিটি যদি দ্বিতীয় সারির সমান হয়। প্রথম অংশের আলোকে, আপনি কি আশা করেন যে সিঙ্গুলার সিস্টেমগুলো আপনার গড় সময়ের উপর বড় কোনো প্রভাব ফেলবে?)
$15 \times 15$ অ্যারের জন্য পূর্ববর্তী ধাপটি পুনরাবৃত্তি করুন।
$25 \times 25$ অ্যারের জন্য পূর্ববর্তী ধাপটি পুনরাবৃত্তি করুন।
$35 \times 35$ অ্যারের জন্য পূর্ববর্তী ধাপটি পুনরাবৃত্তি করুন।
ইনপুটের আকার বনাম গড় সময়ের একটি গ্রাফ তৈরি করুন।

সমস্যা ২

আপনি এমন কী $10 \times 10$ অ্যারে তৈরি করতে পারেন যা সমাধান করতে আপনার কম্পিউটার সিস্টেমের সবচেয়ে বেশি সময় লাগবে? সবচেয়ে কম সময় লাগবে?

সমস্যা ৩

গাউসের পদ্ধতির একটি সহজবোধ্য বাস্তবায়নের জন্য ফোরট্রান প্রোগ্রামের বাকি অংশটুকু লিখুন। একটি কম্পিউটার বীজগণিত সিস্টেমে ব্যবহৃত কোডের গতির সাথে আপনার কোডের গতির তুলনা করুন। কোনটি দ্রুততর? (বেশিরভাগ কম্পিউটার বীজগণিত সিস্টেম ম্যাট্রিক্স বীজগণিতের কিছু কৌশল প্রয়োগ করবে যা আমরা পরে, তৃতীয় অধ্যায়ে দেখব।)

সমস্যা ৪

কোড খণ্ডাংশটিকে এমনভাবে প্রসারিত করুন যেন এটি B অ্যারের একাধিক কলাম থাকার ক্ষেত্রটি পরিচালনা করতে পারে। এটি একসাথে একাধিক সিস্টেম সমাধান করবে (সবগুলোরই সহগ ম্যাট্রিক্স A একই থাকবে)।

সমস্যা ৫

ফোরট্রান ভাষার নিয়ম অনুযায়ী অ্যারেগুলো "কলাম অনুসারে" সংরক্ষিত হয়, অর্থাৎ, পুরো প্রথম কলামটি একসাথে (সংলগ্ন মেমরি স্থানে) সংরক্ষিত হয়, তারপর দ্বিতীয় কলামটি, ইত্যাদি। প্রদত্ত কোড খণ্ডাংশটি কি এই সুবিধার সদ্ব্যবহার করে, নাকি এটিকে আরও দ্রুতগতির করার জন্য নতুন করে লেখা যেতে পারে (কম্পিউটার সংলগ্ন মেমরি অবস্থান থেকে ডেটা দ্রুত সংগ্রহ করতে পারে—এই সুবিধার সদ্ব্যবহার করে)?

সমস্যা ৬

গাউস-জর্ডান বর্জন পদ্ধতির চলার সময় অনুমান করুন। একটি কম্পিউটার ভাষায় গাউস-জর্ডান বর্জন পদ্ধতি বাস্তবায়ন করে আপনার অনুমানটি পরীক্ষা করুন এবং রেনডম ভুক্তিবিশিষ্ট $5 \times 5$ , $15 \times 15$ , এবং $25 \times 25$ ম্যাট্রিক্সের উপর এটি চালিয়ে দেখুন।

সমাধানসমূহ

রৈখিক বীজগণিত
← বিষয়: নেটওয়ার্ক বিশ্লেষণ	বিষয়: গাউস পদ্ধতির গতি	ভেক্টর জগত →