ماتریس خلوت

نمونه‌ای از ماتریس خلوت $\left({\begin{smallmatrix}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{smallmatrix}}\right)$
ماتریس خلوت فوق فقط شامل ۹ عنصر غیرصفر با ۲۶ عنصر صفر است. خلوتی آن ۷۴٪ و چگالی آن ۲۶٪ است

ماتریس خلوت یا ماتریس اسپارس (به انگلیسی: Sparse Matrix) ماتریسی است که اکثر عناصر آن صفر باشد.^[۱] هیچ تعریف دقیقی در مورد نسبت عناصر با ارزش صفر برای یک ماتریس وجود ندارد که به عنوان خلوت شناخته شوند، اما یک معیار رایج این است که تعداد عناصر غیرصفر تقریباً برابر با تعداد سطرها یا ستون‌ها باشد. در مقابل، اگر اکثر عناصر غیر صفر باشند، ماتریس چگال در نظر گرفته می‌شود.^[۲] تعداد عناصر با مقدار-صفر تقسیم بر تعداد کل عناصر (به عنوان مثال، m × n برای یک ماتریس m در n) گاهی به عنوان خلوتی ماتریس نامیده می‌شود. در رایانه هنگامی که ابعاد ماتریس بزرگ و تعداد زیادی از درایه‌های موجود صفر باشند پس خلوت هستند و هنگام ذخیره و دستکاری این ماتریس‌ها در رایانه، استفاده از الگوریتم‌ها و ساختارهای داده‌ای که از ساختارِ خلوتِ ماتریس بهره می‌برند، مفید و اغلب ضروری است.

رایانه‌های ویژه‌ای برای ماتریس‌های خلوت ساخته‌شده‌اند،^[۳] زیرا در زمینه یادگیری ماشین رایج هستند.^[۴] عملیات با استفاده از ساختارها و الگوریتم‌های ماتریس-چگال، زمانی که روی ماتریس‌های خلوت بزرگ اعمال می‌شود، کند و ناکارآمد هستند زیرا پردازش و حافظه روی صفرها تلف می‌شوند. داده‌های خلوت طبیعتاً راحت‌تر فشرده می‌شوند و بنابراین به ذخیره‌سازی کمتری نیاز دارند. دستکاری برخی از ماتریس‌های خلوت بسیار بزرگ با استفاده از الگوریتم‌های استاندارد ماتریس چگال غیرممکن است. این ماتریس در مسائل مربوط به پردازش تصویر و نمایش تصویر نیز مورد استفاده قرار می‌گیرند.

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

یک ماتریس معمولاً به صورت یک آرایه دو بعدی ذخیره می‌شود و نوعی ساختمان داده می‌باشد، دارای دو مقدار، یکی سطر و دیگری ستون می‌باشد که به واقع فضای مورد نیاز برای ذخیره‌سازی آن را نیز بیان می‌دارد (سطر*ستون). هر درایه از طریق یک شناسه‌ای همچون a و دو زیرنوشت (i و j) و درنهایت با استفاده از شکل _i,j) نمایش داده می‌شود. هر درایه می‌تواند مقداری داشته باشد. در ماتریس خلوت؛ به دلیل نوع استفاده؛ دارای تعداد زیادی درایه با مقدار صفر است؛ مثلاً: در پردازش تصویر یک تصویر دارای تعداد زیادی صفر است. برای جلوگیری از اتلاف در زمان و حافظه از این ماتریس استفاده می‌گردد. ساده‌ترین حالت پیاده‌سازی به صورت یک آرایه و یک لیست پیوندی است که هر کدام از عناصر دارای یک سری از ویژگی‌ها به صورت کلی <matrix<r,c،t است که r نمایانگر شمارهٔ سطر و c نمایانگر ستون و t نمایانگر مقدار ذخیره‌شده در سطر و ستون ماتریس خلوت یادشده است.

منابع ویرایش

↑ Yan, Di; Wu, Tao; Liu, Ying; Gao, Yang (2017). An efficient sparse-dense matrix multiplication on a multicore system. IEEE. doi:10.1109/icct.2017.8359956. ISBN 978-1-5090-3944-9. The computation kernel of DNN is large sparse-dense matrix multiplication. In the field of numerical analysis, a sparse matrix is a matrix populated primarily with zeros as elements of the table. By contrast, if the number of non-zero elements in a matrix is relatively large, then it is commonly considered a dense matrix. The fraction of zero elements (non-zero elements) in a matrix is called the sparsity (density). Operations using standard dense-matrix structures and algorithms are relatively slow and consume large amounts of memory when applied to large sparse matrices.
↑ Yan, Di; Wu, Tao; Liu, Ying; Gao, Yang (2017). An efficient sparse-dense matrix multiplication on a multicore system. IEEE. doi:10.1109/icct.2017.8359956. ISBN 978-1-5090-3944-9. The computation kernel of DNN is large sparse-dense matrix multiplication. In the field of numerical analysis, a sparse matrix is a matrix populated primarily with zeros as elements of the table. By contrast, if the number of non-zero elements in a matrix is relatively large, then it is commonly considered a dense matrix. The fraction of zero elements (non-zero elements) in a matrix is called the sparsity (density). Operations using standard dense-matrix structures and algorithms are relatively slow and consume large amounts of memory when applied to large sparse matrices.
↑ "Cerebras Systems Unveils the Industry's First Trillion Transistor Chip". www.businesswire.com (به انگلیسی). 2019-08-19. Retrieved 2019-12-02. The WSE contains 400,000 AI-optimized compute cores. Called SLAC™ for Sparse Linear Algebra Cores, the compute cores are flexible, programmable, and optimized for the sparse linear algebra that underpins all neural network computation
↑ "Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer | Argonne National Laboratory". www.anl.gov (Press release) (به انگلیسی). Retrieved 2019-12-02. The WSE is the largest chip ever made at 46,225 square millimeters in area, it is 56.7 times larger than the largest graphics processing unit. It contains 78 times more AI optimized compute cores, 3,000 times more high speed, on-chip memory, 10,000 times more memory bandwidth, and 33,000 times more communication bandwidth.

[Yan_Wu_Liu_Gao_2017_p.2-1] Yan, Di; Wu, Tao; Liu, Ying; Gao, Yang (2017). An efficient sparse-dense matrix multiplication on a multicore system. IEEE. doi:10.1109/icct.2017.8359956. ISBN 978-1-5090-3944-9. The computation kernel of DNN is large sparse-dense matrix multiplication. In the field of numerical analysis, a sparse matrix is a matrix populated primarily with zeros as elements of the table. By contrast, if the number of non-zero elements in a matrix is relatively large, then it is commonly considered a dense matrix. The fraction of zero elements (non-zero elements) in a matrix is called the sparsity (density). Operations using standard dense-matrix structures and algorithms are relatively slow and consume large amounts of memory when applied to large sparse matrices.

[Yan_Wu_Liu_Gao_2017_p.-2] Yan, Di; Wu, Tao; Liu, Ying; Gao, Yang (2017). An efficient sparse-dense matrix multiplication on a multicore system. IEEE. doi:10.1109/icct.2017.8359956. ISBN 978-1-5090-3944-9. The computation kernel of DNN is large sparse-dense matrix multiplication. In the field of numerical analysis, a sparse matrix is a matrix populated primarily with zeros as elements of the table. By contrast, if the number of non-zero elements in a matrix is relatively large, then it is commonly considered a dense matrix. The fraction of zero elements (non-zero elements) in a matrix is called the sparsity (density). Operations using standard dense-matrix structures and algorithms are relatively slow and consume large amounts of memory when applied to large sparse matrices.

[3] "Cerebras Systems Unveils the Industry's First Trillion Transistor Chip". www.businesswire.com (به انگلیسی). 2019-08-19. Retrieved 2019-12-02. The WSE contains 400,000 AI-optimized compute cores. Called SLAC™ for Sparse Linear Algebra Cores, the compute cores are flexible, programmable, and optimized for the sparse linear algebra that underpins all neural network computation

[4] "Argonne National Laboratory Deploys Cerebras CS-1, the World's Fastest Artificial Intelligence Computer | Argonne National Laboratory". www.anl.gov (Press release) (به انگلیسی). Retrieved 2019-12-02. The WSE is the largest chip ever made at 46,225 square millimeters in area, it is 56.7 times larger than the largest graphics processing unit. It contains 78 times more AI optimized compute cores, 3,000 times more high speed, on-chip memory, 10,000 times more memory bandwidth, and 33,000 times more communication bandwidth.

[۱]

[۲]

[۳]

[۴]