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

یکی از مباحث مربوط به آنالیز عددی (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 برای نمایش ماتریس خلوت

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

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

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

یک ماتریس، مربعی $$4 \times 4$$ با ۴ عنصر غیر صفر به صورت زیر را در نظر بگیرید.

$$\large {\begin{pmatrix} 0 & 0 & 0 & 0 \\ 5 & 8 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 6 & 0 & 0 \\ \end{pmatrix}}$$

با استفاده از شیوه COO، نمایش ماتریس خلوتی که در بالا معرفی شد، به صورت زیر خواهد بود.

$$\large \begin{bmatrix} 4 & 4 & 4 \\ \hline 1 & 0 & 5 \\ 1 & 1 & 8 \\ 2 & 2 & 3 \\ 3 & 1 & 6 \\ \end{bmatrix}$$

ساختار ردیف خلوت فشرده

در این قسمت با توجه به تکنیک به کار رفته در «ردیف خلوت فشرده» (Compressed Sparse Row) یا به اختصار CSR به این شیوه ذخیره سازی یک ماتریس خلوت خواهیم پرداخت تا بتوانیم محاسبات دیگری مانند جمع و ترانهاده ماتریس را نیز به کمک بیان فشرده ماتریس خلوت انجام دهیم.

این شیوه بیان ماتریس خلوت، از یک بردار سه بعدی (سه تایی مرتب) استفاده می‌کند. گاهی به این شیوه بیان ماتریس خلوت، «قالب یل» (Yale Format) نیز می‌گویند. به این ترتیب برای هر درایه غیر صفر، شماره ردیف و ستون ماتریس، به همراه مقدار آن درایه، ثبت شده و هر سطر، تشکیل یک سه تایی مرتب (Triple) را می‌دهد. این سه‌تایی‌های مرتب را در سه بردار می‌توان ذخیره کرد. این بردارها را به صورت زیر نام‌گذاری می‌کنند.

• V یا Value: مقدار درایه را مشخص می‌کند. واضح است که این مقدار غیر صفر است.
• Col_index: شماره ستون مربوط به مقدار درایه را در ماتریس اولیه تعیین می‌کند.
• Row_index: شماره ردیف درایه مورد نظر در این قسمت ثبت می‌شود.

ماتریس زیر را در نظر بگیرید. واضح است که این ماتریس، مربعی $$4 \times 4$$ بوده که فقط ۴ عنصر آن غیر صفر است.

$$\large {\begin{pmatrix} 0 & 0 & 0 & 0 \\ 5 & 8 & 0 & 0 \\ 0 & 0 & 3 & 0 \\ 0 & 6 & 0 & 0 \\ \end{pmatrix}}$$

بیان این ماتریس خلوت به شیوه CSR، به شکل زیر خواهد بود. سه آرایه کاملا در این شکل از نمایش ماتریس خلوت دیده می‌شود.

نکته: فرض بر این است که اندیس اول در اینجا با صفر نشان داده شده است.

در ادامه کدی را با زبان برنامه‌نویسی ++C‌ مشاهده می‌کنید که به تبدیل ساختار آرایه‌ای (سه تایی مرتب) از ماتریس خلوت می‌پردازد.

ماتریس مورد نظر برای تبدیل به نمایش سطر خلوت فشرده به صورت زیر مشخص شده است.

$$\large \begin{pmatrix} 0 & 0 & 0 & 0 & 9 & 0 \\ 0 & 8 & 0 & 0 & 0 & 0 \\ 4 & 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 5 \\ 0 & 0 & 2 & 0 & 0 & 0 \\ \end{pmatrix}$$

حاصل اجرای این برنامه و خروجی بدست آمده، به صورت زیر خواهد بود.

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

ساختار ستون خلوت فشرده

اگر برای استخراج ماتریس فشرده، مقادیر ماتریس به جای ترتیب سطری از ترتیب ستونی برخوردار باشند، روش ذخیره سازی یا ساختار داده را به صورت «ستون خلوت فشرده» (Compressed sparse column) یا به اختصار CSC می‌شناسند. به این ترتیب این بار اندیس ستون (Column Index) در ساختار جدید، مرتب شده است. ولی مقدارهای ماتریس و اندیس سطر و ستون به شیوه قبل مشخص خواهد شد.

نمایش و ثبت ماتریس خلوت در نرم‌افزار MATLAB‌ از ساختار ستون خلوت فشرده با استفاده از تابع sparse بهره می‌برد. این شیوه اغلب برای انجام محاسبات ریاضی مناسب‌تر است.

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

عملگر ترانهاده روی یک ماتریس باعث می‌شود جای مقدارهای درون سطرها با ستون‌ها عوض شود. به این ترتیب $$A$$ را یک ماتریس $$m \times n$$ با درایه‌هایی به صورت زیر در نظر می‌گیریم.

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

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

کلیک کنید

در این صورت ماتریس حاصل از عمل ترانهاده که به شکل $$A'$$ نشان داده می‌شود، دارای ابعادی به صورت $$n \times m$$ است، بطوری که درایه‌های آن از همان درایه‌های ماتریس $$A$$ تشکیل شده ولی داریم:

$$\large a'_{ij} = a_{ji}$$

همانطور که در ساختار سطری خلوت فشرده مشاهده کردید، مقادیری که مقدار مخالف صفر در ماتریس خلوت داشتند، با اندیس سطر و ستون و مقدار درایه ماتریس مشخص و ذخیره می‌شوند. بنابراین اگر بخواهیم چنین  ساختاری را برای ترانهاده یک ماتریس ایجاد کنیم، کافی است که مقدار اندیس سطر را با ستون تغییر دهیم.

برای مثال ماتریس زیر را در نظر بگیرید.

$$\large A= \begin{pmatrix} 0 & 0 & 0 & 0 & 9 & 0 \\ 0 & 8 & 0 & 0 & 0 & 0 \\ 4 & 0 & 0 & 2 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 5 \\ 0 & 0 & 2 & 0 & 0 & 0 \\ \end{pmatrix}$$

مشخص است که ترانهاده آن به صورت زیر در خواهد آمد.

$$\large A' = \begin{pmatrix} 0 & 0 & 4 & 0 & 0 \\ 0 & 8 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 2 \\ 0 & 0 & 2 & 0 & 0 \\ 9 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 5 & 0 \end{pmatrix}$$

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

ترانهاده آن نیز به شکل زیر در خواهد آمد.

برنامه زیر برای انجام این عمل تهیه شده است.

جمع دو ماتریس خلوت

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

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

برای مثال به جمع دو ماتریس خلوت به شیوه نمایش دیکشنری به صورت زیر توجه کنید.

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

قطعه کدی که در ادامه مشاهده می‌کنید، برای نمایش ترانهاده، جمع و ضرب دو ماتریس خلوت براساس نمایش CSR است که به زبان ++C نوشته شده.

خلاصه و جمع‌بندی

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