ماتریس خلوت در ریاضیات و ساختمان داده | به زبان ساده

یکی از مباحث مربوط به آنالیز عددی (Numerical Analysis) که جنبه کاربردی در علوم محاسباتی بخصوص در برنامه‌نویسی رایانه‌ای دارد، ماتریس خلوت (Sparse Matrix) یا بردار خلوت (Sparse Array) است. شیوه‌های مختلفی برای نمایش یا بیان ماتریس‌های خلوت وجود دارد که کارایی محاسبات بیشتری نسبت به ماتریس‌های اصلی دارند. از این جهت که محاسبات ماتریسی و برداری، براساس این گونه نمایش ماتریس‌های خلوت، ساده‌تر و موثرتر هستند، در این نوشتار به بررسی ماتریس خلوت در ریاضیات و کاربردهای آن در ساختمان داده خواهیم پرداخت.

برای آشنایی بیشتر با ماتریس‌ها بهتر است نوشتارهای ماتریس‌ها در ریاضی — به زبان ساده و ترانهاده ماتریس — به زبان ساده را مطالعه کنید. همچنین خواندن مطالب ساختمان داده (Data Structure) — راهنمای جامع و کاربردی و دترمینان یک ماتریس — به زبان ساده  نیز خالی از لطف نیست.

ماتریس خلوت در ریاضیات و ساختمان داده

می‌دانید که ماتریس (Matrix) یک نمای دو بعُدی از داده‌ها است، بطوری که به شکل یک جدول با $$n$$ سطر و $$m$$ ستون قابل نمایش باشد. مقدارهای درون این جدول، درایه‌های ماتریس گفته شده و می‌توانند در مجموعه اعداد حقیقی (زمانی که موضوع یا زمینه کاری اعداد حقیقی است) تغییر کنند. البته امکان استفاده از مقادیر یا اعداد مختلط نیز در ماتریس‌ها وجود دارد.

فیلم آموزش ساختمان داده ها – مرور و تست کنکور ارشد در فرادرس

کلیک کنید

اغلب با توجه به ابعاد ماتریس‌ها، آن‌ها را شناسایی و طبقه‌بندی می‌کنیم. در زیر یک ماتریس با ۳ سطر و ۲ ستون را مشاهده می‌کنید.

$$\large \begin{bmatrix}1 & 5 \\ 3 & 1.2 \\ -6 & \sqrt{12} \end{bmatrix}$$

معمولا درایه‌های یک ماتریس $$n \times m$$ را به صورت زیر مشخص می‌کنند.

$$\large [a_{ij}] , \;\;i= 1 , \ldots , n , \;\;\; j = 1, \ldots,  m$$

این ساختار یک ماتریس را نشان می‌دهد. در این حالت $$i$$ را اندیس سطر (Row Index) و $$j$$ را اندیس ستون (Column Index) می‌نامیم.

نکته: فضای ذخیره سازی برای چنین ماتریسی در حافظه رایانه‌ها، متناسب با تعداد سطرها و ستون‌ها خواهد بود. در نتیجه هر چه ماتریس دارای ابعاد بزرگتری باشد، فضای ذخیره‌سازی بیشتری نیز در حافظه احتیاج دارد.

حال یک ماتریس به صورت زیر را در نظر بگیرید.

$$\large S = \begin{bmatrix}0 & 1 & 0 \\ 0 & 0 & 0\\ -6 & \sqrt{12} & 0 \\ 0 & -1 &0 \\ 0 & 0 & 2 \end{bmatrix}$$

در این حالت، ماتریس A را یک «ماتریس خلوت» (Sparse Matrix) یا ماتریس پراکنده می‌نامند، زیرا درایه‌های موثر (تغییر پذیر) آن نسبت به درایه‌های صفر (ثابت) بیشتر است. در مقابل اگر درایه‌های موثر یک ماتریس بیش از درایه‌های صفر آن باشند، ماتریس را «ماتریس متراکم» (Dense Matrix) می‌گویند.

مشخص است که بسیاری از عناصر یا درایه‌های ماتریس خلوت صفر (یا ثابت) هستند. در نتیجه ذخیره سازی چنین ماتریسی به شکل کامل، حافظه نسبتا زیادی را با توجه به اطلاعات موجود در ماتریس اصلی خواهد گرفت. از طرفی بار محاسباتی نیز برای ماتریس‌هایی به این شکل، زیاد خواهد بود در حالیکه برای مثلا ضرب، بیشتر محاسبات یکسان در نظر گرفته می‌شوند.

توجه داشته باشید که ماتریس‌های مربعی از نوع «بالا مثلثی» (َUpper Triangular) یا «پایین مثلثی» (Lower Triangular) یا «ماتریس قطری» (Diagonal Matrix)، ماتریس‌های خلوت محسوب می‌شوند.

نکته: اگر ماتریس‌های خلوت به جای مقدار صفر، یک مقدار ثابت دیگر داشته باشند، نحوه ذخیره‌سازی آن‌ها باز هم می‌تواند به شیوه بیان ماتریس‌های خلوت باشد. فقط هنگام انجام عملیات ریاضی، باید با دقت بیشتری نسبت به محاسبات عمل کرده و اثر این مقدار ثابت را در محاسبات بعدی لحاظ کنیم.

چنین وضعیتی برای بسیاری از ساختارهای ذخیره سازی ممکن است رخ دهد. برای مثال تصویری از یک نوشته که زمینه‌ای سیاه دارد، دارای مقدارهای زیادی از کد مثلا صفر برای نمایش رنگ زمینه است. اگر قرار باشد که همه این پیکسل‌های تصویری ذخیره شوند، حجم زیادی از حافظه اشغال خواهد شد. در حالیکه فقط بعضی از پیکسل‌ها اهمیت داشته و مقادیر متفاوتی دارند.

بنابراین شیوه‌ای برای ذخیره سازی چنین ماتریس‌هایی در حوزه مباحث مربوط به «ساختمان داده» (Data Structure) مطرح می‌شود که در ادامه به این موضوع خواهیم پرداخت. البته این تکنیک‌ها به کاهش حجم و فشرده‌سازی مقادیر و ماتریس‌ها کمک کرده و می‌توانند برای فشرده کردن تصویرهای بیتی (Bitmap Image) به کار روند.

ضریب خلوتی (Sparsity)

یک ماتریس خلوت (Sparse Matrix)، به ماتریسی گفته می‌شود که دارای درایه صفر (یا ثابت) زیادی باشد. در این حالت می‌توان برای چنین ماتریس‌هایی «ضریب خلوتی» (Sparsity) را به شکل نسبت درایه‌های غیر صفر به کل درایه‌ها در نظر گرفت. به این ترتیب فرمول زیر را برای محاسبه ضریب خلوتی خواهیم داشت.

$$ \large Sparsity = \dfrac{ \text{# of non-zero elements} }{ \text{# of total elements} } $$

فیلم آموزش ساختمان داده ها – جامع و با نکات مهم در فرادرس

کلیک کنید

به این ترتیب برای ماتریس S‌ که در بالا معرفی شد، مقدار ضریب خلوتی برابر است با:

$$\large Sparsity(S) = \dfrac{10}{15}  = \dfrac{1}{3} = 0.67$$

همچنین اگر ماتریس خلوتی را به شکل زیر در نظر گرفته باشیم،

$$\large \begin{pmatrix} 11 & 22 & 0 & 0 & 0 & 0 & 0 \\ 0 & 33 & 44 & 0 & 0 & 0 & 0 \\ 0 & 0 & 55 & 66 &  77 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 88 & 0 \\  0 & 0 & 0 & 0 & 0 & 0 & 99 \end{pmatrix}$$

ضریب خلوتی برای آن به صورتی که در ادامه قابل مشاهده است، قابل محاسبه است.

$$\large Sparsity= \dfrac{26}{35}  = 0.74$$

واضح که ماتریس بالا، دارای ضریب خلوتی بزرگتری نسبت به ماتریس S است، در نتیجه فضای کمتری برای ذخیره‌سازی آن لازم خواهد بود. متمم ضریب خلوتی، به ضریب تراکم یا «چگالی» (Density) معروف است. مشخص است که برای ماتریس بالا، ضریب چگالی برابر با مقدار زیر است.

$$\large Density =1 - Sparsity = 1 -  0.74  = 0.26 = \dfrac{9}{35}$$

همچنین برای ماتریس S نیز چگالی برابر است با:

$$\large Density(S) = 1 -  Sparsity = 1 -  0.67  = 0.33 = \dfrac{5}{15}$$

حال یک ماتریس ۲۰۰۰ در ۲۰۰۰ را در نظر بگیرید که فقط ۵۰۰ مقدار آن، مخالف صفر است. مقدار ضریب خلوتی آن برابر  0٫999 قرار دارد. واضح است که ذخیره سازی چهار میلیون مقدار که فقط ۵۰۰ تای آن مخالف صفر است، فضای بسیار بیشتری نسبت به حالتی خواهد داشت که ماتریس خلوت را با شیوه‌های فشرده‌سازی و با ساختاری دیگر ذخیره کنیم. در زیر ضریب خلوتی و چگالی این چنین ماتریسی را محاسبه کرده‌ایم.

$$\large Sparsity= \dfrac{3999500}{4000000}  = 0.9999$$

$$\large Density= \dfrac{500}{4000000}  = 0.0001$$

ذخیره سازی یک ماتریس خلوت

در مورد یک ماتریس خلوت یا پراکنده، می‌توان با ذخیره کردن فقط ورودی‌های غیر صفر عمل ثبت را انجام داد و با این کار کاهش حافظه قابل توجهی برای ذخیره سازی این ساختار بوجود آورد. بسته به تعداد و پراکندگی ورودی‌های غیر صفر ماتریس خلوت، از ساختار داده‌های مختلفی می‌توان استفاده کرد و در مقایسه با ثبت کامل ماتریس، صرفه جویی زیادی در حافظه صورت داد.

نکته: مهم این است که در ساختار جدید ممکن است دسترسی به عناصر خاص، پیچیده‌تر شود و ساختارهای اضافه‌ای لازم خواهد بود تا بتوانیم ماتریس اصلی را به صورت کامل بازیابی کنیم.

در کل می‌توان شیوه یا ساختار ذخیره سازی ماتریس خلوت را به دو دسته تقسیم کرد.

• روش‌هایی که از پشتیبانی خوبی برای تغییرات روی درایه‌های ماتریس اولیه برخوردار هستند. مانند «کلیدهای دیکشنری» (Dictionary of Keys) که به اختصار KOD گفته می‌شوند. یا روش «لیستی از لیست‌ها» (List of Lists)  که به صورت خلاصه به شکل LIL نشان داده شده، یا «لیست مختصات» (Coordinate List) با عبارت اختصاری COO، همگی روش‌هایی برای نمایش یک ماتریس خلوت هستند.
• رویکرد دیگر برای نمایش ماتریس خلوت، تکنیک CSR یا «ردیف خلوت فشرده» (Compressed Sparse Row) یا CSC یا «ستون خلوت فشرده» (Compressed Sparse Column) است که برای اجرای عملیاتی مانند ترانهاده کردن ماتریس اولیه، بسیار کارا عمل می‌کنند.

ابتدا شیوه اول را معرفی کرده، سپس روش CSR را به کار می‌بریم.

رویکرد COO برای نمایش ماتریس خلوت

اغلب برای نمایش ساختار مختصاتی یا لیست مختصات از شکل زیر (که ظاهری مانند ماتریس دارد) استفاده می‌کنند. توجه داشته باشید که ردیف اول به ویژگی‌های ماتریس خلوت پرداخته و ارتباط با مقدارها ندارد.

• ردیف اول: ابتدا تعداد سطرها، سپس تعداد ستون‌ها و در انتها نیز تعداد عناصر غیر صفر مشخص می‌شود.
• ردیف‌های بعدی: به ترتیب شماره سطر، شماره ستون و مقدار عنصر غیر صفر از ماتریس خلوت قرار می‌گیرد.

از آنجایی که، نحوه نوشتن مقادیر سطر به سطر صورت خواهد گرفت، ستون اول این شیوه نمایش، از کوچک به بزرگ مرتب شده است (بدون توجه به سطر اول).