রৈখিক বীজগণিত/বিষয়: নির্ণায়ক গণনার গতি

রৈখিক বীজগণিত
← বিষয়: ক্র্যামারের নিয়ম	বিষয়: নির্ণায়ক গণনার গতি	বিষয়: অভিক্ষেপীয় জ্যামিতি →

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

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

নির্ণায়কের জন্য বিন্যাস সম্প্রসারণ সূত্রটি স্মরণ করা যাক:

\begin{matrix} | \begin{matrix} t_{1, 1} & t_{1, 2} & \dots & t_{1, n} \\ t_{2, 1} & t_{2, 2} & \dots & t_{2, n} \\ ⋮ \\ t_{n, 1} & t_{n, 2} & \dots & t_{n, n} \end{matrix} | & = \sum_{permutations ϕ} t_{1, ϕ (1)} t_{2, ϕ (2)} \dots t_{n, ϕ (n)} | P_{ϕ} | \\ = \begin{matrix} t_{1, ϕ_{1} (1)} \cdot t_{2, ϕ_{1} (2)} \dots t_{n, ϕ_{1} (n)} | P_{ϕ_{1}} | \\ + t_{1, ϕ_{2} (1)} \cdot t_{2, ϕ_{2} (2)} \dots t_{n, ϕ_{2} (n)} | P_{ϕ_{2}} | \\ ⋮ \\ + t_{1, ϕ_{k} (1)} \cdot t_{2, ϕ_{k} (2)} \dots t_{n, ϕ_{k} (n)} | P_{ϕ_{k}} | \end{matrix} \end{matrix}

এখানে $n! = n \cdot (n - 1) \cdot (n - 2) \dots 2 \cdot 1$ সংখ্যক ভিন্ন ভিন্ন $n$ -বিন্যাস রয়েছে। যেকোনো আকারের $n$ -এর জন্যই এটি একটি বিশাল মান; উদাহরণস্বরূপ, $n$ -এর মান মাত্র $10$ হলেও এই সম্প্রসারণে $10! = 3, 628, 800$ -টি পদ বা টার্ম থাকে, যার প্রতিটিই $n$ -সংখ্যক ভুক্তি ( পরস্পরের সাথে গুণ করার মাধ্যমে পাওয়া যায়। এটি গুণনের একটি বিশাল সংখ্যা (ব্যবহারিক গণনার সীমার জন্য একটি মোটামুটি বা খসড়া সীমানা হিসেবে $10!$ ধাপের পরামর্শ দিয়েছেন)। ফ্যাক্টোরিয়াল ফাংশনটি বর্গ ফাংশনের চেয়ে দ্রুত বৃদ্ধি পায়। এটি ঘনক ফাংশন, চতুর্থ ঘাত ফাংশন বা যেকোনো বহুপদী ফাংশনের চেয়েও দ্রুত বৃদ্ধি পায়। (ফ্যাক্টোরিয়াল ফাংশন যে বর্গের চেয়ে দ্রুত বৃদ্ধি পায় তা দেখার একটি উপায় হলো— $n!$ -এর প্রথম দুটি উৎপাদক গুণ করলে $n \cdot (n - 1)$ পাওয়া যায়, যা বড় $n$ -এর জন্য প্রায় $n^{2}$ -এর কাছাকাছি, এবং এরপর আরও উৎপাদক গুণ করতে থাকলে এটি আরও বড় হতে থাকবে। একই যুক্তি ঘনক ফাংশন ইত্যাদির ক্ষেত্রেও খাটে)। সুতরাং, একটি কম্পিউটারকে যদি বিন্যাস সম্প্রসারণ সূত্র ব্যবহার করার জন্য প্রোগ্রাম করা হয়, এবং যার ফলে সারির সংখ্যার ফ্যাক্টোরিয়ালের সমান বা তার চেয়ে বেশি সংখ্যক গাণিতিক প্রক্রিয়া সম্পন্ন করতে হয়, তবে ইনপুট ডেটাসেটের আকার বৃদ্ধির সাথে সাথে সেটি অত্যন্ত দীর্ঘ সময় নেবে।

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

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

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

PIVINV=1.0/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 10 CONTINUE সবচেয়ে বাইরের লুপটি (যা এখানে দেখানো হয়নি) $N - 1$ সংখ্যক সারি পর্যন্ত চলে। প্রতিটি সারির জন্য, এখানে প্রদর্শিত নেস্টেড $I$ এবং $J$ লুপ দুটি A ম্যাট্রিক্সের পিভট ভুক্তির নিচে এবং ডানে থাকা উপাদানগুলোর ওপর গাণিতিক প্রক্রিয়া সম্পন্ন করে। ধরা যাক, পিভটটি প্রত্যাশিত স্থানেই পাওয়া গেছে, অর্থাৎ $C O L = R O W$ । তাহলে পিভটের নিচে এবং ডানে মোট $(N - R O W)^{2}$ -সংখ্যক ভুক্তি থাকবে। গড়ে, সারির মান হবে $N / 2$ । সুতরাং, আমরা অনুমান করতে পারি যে এই গাণিতিক প্রক্রিয়াটি প্রায় $(N / 2)^{2}$ বার সম্পাদিত হবে; অর্থাৎ, এর জন্য নেওয়া সময় সমীকরণ সংখ্যার বর্গের সমানুপাতিক হবে। এখানে দেখানো হয়নি এমন বাইরের লুপটিকে হিসাবে নিলে আমরা অনুমান করতে পারি যে, এই অ্যালগরিদমের রান-টাইম সমীকরণ সংখ্যার ঘনকের সমানুপাতিক।

নির্ণায়ক গণনার জন্য সবচেয়ে দ্রুততম অ্যালগরিদম খুঁজে বের করা বর্তমান গবেষণার একটি অন্যতম বিষয়। এমন কিছু অ্যালগরিদমের সন্ধান পাওয়া গেছে যেগুলোর রান-টাইম দ্বিতীয় এবং তৃতীয় ঘাতের মাঝামাঝি হয়ে থাকে।

গতির এই ধরণের অনুমান আমাদের কোনো অ্যালগরিদম কত দ্রুত বা ধীর গতিতে চলবে তা বুঝতে সাহায্য করে। যেসব অ্যালগরিদমের রান-টাইম ডেটাসেটের আকারের সমানুপাতিক সেগুলো দ্রুত চলে; যেসব অ্যালগরিদমের রান-টাইম ডেটাসেটের আকারের বর্গের সমানুপাতিক সেগুলো কিছুটা ধীর গতির হলেও সাধারণত বেশ ব্যবহারোপযোগী; এবং যেসব অ্যালগরিদমের রান-টাইম ডেটাসেটের আকারের ঘনকের সমানুপাতিক সেগুলো খুব বেশি বড় নয় এমন ইনপুট ডেটার জন্য গতিশৈলীর দিক থেকে বেশ যুক্তিযুক্ত বা সহনশীল। তবে, যেসব অ্যালগরিদমের রান-টাইম ডেটাসেটের আকারের ফ্যাক্টোরিয়ালের সমান বা তার চেয়ে বেশি, সেগুলো উল্লেখযোগ্য যেকোনো আকারের ইনপুটের জন্য মোটেও ব্যবহারিক বা গ্রহণযোগ্য নয়।

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

অনুশীলনীসমূহ

এই সমস্যাগুলোর অধিকাংশের জন্যই কম্পিউটারের সাহায্য প্রয়োজন হতে পারে।

সমস্যা ১

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

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

সমস্যা ২

উপরে আলোচিত দুটি পদ্ধতি ব্যবহার করে নিচের প্রতিটির নির্ণায়ক হাতে কলমে গণনা করুন।

$| \begin{matrix} 2 & 1 \\ 5 & - 3 \end{matrix} |$
$| \begin{matrix} 3 & 1 & 1 \\ - 1 & 0 & 5 \\ - 1 & 2 & - 2 \end{matrix} |$
$| \begin{matrix} 2 & 1 & 0 & 0 \\ 1 & 3 & 2 & 0 \\ 0 & - 1 & - 2 & 1 \\ 0 & 0 & - 2 & 1 \end{matrix} |$

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

সমস্যা ৩

আপনার কম্পিউটার সিস্টেমের সারি হ্রাসকরণ বা রো-রিডাকশন করতে সবচেয়ে বেশি সময় নেবে—এমন একটি $10 \times 10$ অ্যারে আপনি কীভাবে তৈরি করতে পারেন? এবং সবচেয়ে কম সময় নেবে এমন অ্যারেটিই বা কেমন হবে?

সমস্যা ৪

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

সমস্যা ৫

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

সমাধান

তথ্যসূত্র

নাথ, ডোনাল্ড ই. (১৯৮৮), দ্য আর্ট অফ কম্পিউটার প্রোগ্রামিং, অ্যাডিসন ওয়েসলি

.

রৈখিক বীজগণিত
← বিষয়: ক্র্যামারের নিয়ম	বিষয়: নির্ণায়ক গণনার গতি	বিষয়: অভিক্ষেপীয় জ্যামিতি →