এই বিভাগে আমরা দেখব স্পার্স ম্যাট্রিক্স কী এবং কিভাবে সেগুলি মেমরিতে উপস্থাপন করা যায়। একটি ম্যাট্রিক্স স্পার্স ম্যাট্রিক্স হবে যদি এর অধিকাংশ উপাদান 0 হয়। অন্য একটি সংজ্ঞা অনুযায়ী, সর্বোচ্চ 1/3 অ-শূন্য উপাদান (প্রায় 30% m x n) সম্বলিত ম্যাট্রিক্সকে স্পার্স ম্যাট্রিক্স বলা হয়।
কম্পিউটার মেমরিতে অপারেশন দক্ষতার সাথে সম্পন্ন করার জন্য আমরা ম্যাট্রিক্স ব্যবহার করি। কিন্তু যদি ম্যাট্রিক্সগুলো স্পার্স প্রকৃতির হয়, তবে অপারেশন দক্ষতার সাথে সম্পন্ন হতে পারে, কিন্তু মেমরিতে বড় পরিমাণ স্থান নেয়। সেই স্থানগুলো কোনো উদ্দেশ্য phụcন করে না। তাই আমরা স্পার্স ম্যাট্রিক্স সংরক্ষণের জন্য অন্য কিছু কাঠামো অনুসরণ করব।
ধরি আমাদের নিম্নলিখিত স্পার্স ম্যাট্রিক্স রয়েছে:
দেখা যাচ্ছে 8টি অ-শূন্য উপাদান এবং 28টি শূন্য মান রয়েছে। এই ম্যাট্রিক্স 6x6 = 36 মেমরি স্পেস নেয়। যদি ম্যাট্রিক্সের আকার বড় হয়, তবে আপচয়される স্থানও বাড়বে।
আমরা টেবিল কাঠামো ব্যবহার করে স্পার্স ম্যাট্রিক্সের তথ্য সংরক্ষণ করতে পারি। ধরি আমরা X নামে একটি টেবিল তৈরি করি:
এখানে প্রথম কলাম সারি নম্বর ধারণ করছে, দ্বিতীয়টি কলাম নম্বর, এবং তৃতীয়টি M[row, col]-এ উপস্থিত ডেটা। এই টেবিলের প্রতিটি সারিকে ট্রিপলেট বলা হয় কারণ তিনটি প্যারামিটার রয়েছে। প্রথম ট্রিপলেট ম্যাট্রিক্সের আকারের তথ্য ধারণ করে। Row = 6 এবং Column = 6 নির্দেশ করছে যে ম্যাট্রিক্স M হল 6x6 ম্যাট্রিক্স। ভ্যালু ফিল্ডটি অ্যারেতে কতগুলো অ-শূন্য উপাদান আছে তা নির্দেশ করছে।
এই টেবিলও 9x3 = 36 পরিমাণ স্থান নেয়, তো লাভ কোথায়? যদি ম্যাট্রিক্সের আকার 8x8 = 64 হয়, কিন্তু শুধু 8টি উপাদান থাকে, তবে টেবিল X-ও 36 ইউনিট স্থান নেবে। আমরা দেখতে পাচ্ছি যে 3টি কলাম Фиксড, সারির সংখ্যা অ-শূন্য উপাদানের সংখ্যার সাথে পরিবর্তিত হয়। তাই যদি T সংখ্যক অ-শূন্য উপাদান থাকে, তবে স্পেস কমপ্লেক্সিটি হবে O(3*T) = O(T)। ম্যাট্রিক্সের জন্য তা হবে O(m x n)।
