Makine öğrenimi ve yapay zeka bağlamında seyrek matris depolama veoperasyonlarının alan ve zaman karmaşıklığında iyileştirme
Improvement on the space and time complexity of sparse matrix storage and operations in the context of machine learning and artificial intelligence
Yazar: HASAN TAHSİN AYTEKİN
Danışman: PROF. DR. ARAL EGE
Ufuk Üniversitesi / Sosyal Bilimler Enstitüsü / Yönetim Bilişim Sistemleri Ana Bilim Dalı / Yönetim Bilişim Sistemleri Bilim Dalı
Derece: Doktora, 2024
Konu: Yönetim Bilişim Sistemleri = Management Information Systems

Özet:
Seyrek matris, öğelerinin çoğunun sıfır olduğu bir matristir. Standart yoğun matris yapıları ve algoritmaları kullanan işlemler büyük seyrek matrislere uygulandığında, işlemler ve bellek, tekrarlanan sıfırlar ile boşa harcandığından yavaş ve verimsizdir. Seyrek matrisleri bir bilgisayarda depolarken ve işlerken, matrisin seyrek yapısından yararlanan özel algoritmalar ve veri yapılarını kullanmak gerekmektedir. Seyrek veriler doğası gereği daha kolay sıkıştırılır ve bu nedenle önemli ölçüde daha az depolama gerektirir. Bu tezde, seyrek matrislerin depolanması ve depolanan matris elemanlarına erişim için geliştirilen çeşitli yöntemler detaylı bir şekilde incelenmiştir. Bu inceleme sonucunda, hem seyrek matrislerin verimli bir şekilde depolanmasında hem de matris elemanlarının etkili bir şekilde erişiminde mevcut yöntemlerden daha ileri kazanımlar sağlayan segmentlere ayırarak sıkıştırma odaklı yeni bir yöntem geliştirilmiştir. Seyrek matris depolama ve depolanan bilgiye erişim için bu tez çalışmasında geliştirdiğimiz segmentlere ayırarak sıkıştırma algoritmaları ile mevcut sıkıştırma algoritmalarını değerlendirmek üzere bir simülasyon ortamı geliştirilmiştir. Simülasyon ortamında kullanılan veriler, daha önce benzer çalışmalar için kullanılan referans seyrek matris verilerini içeren SuiteSparse Matrix Collection veri bankasında 01/03/2024 tarihi itibariyle mevcut olan tüm seyrek matrislerdir. Simülasyon ortamından elde edilen sonuçlar kapsamında yapılan karşılaştırmalar sonucunda; Sıkıştırılmış Seyrek Satır (SSS) veya Sütun (SSSt) sıkıştırma oranlarına ek olarak, 2 baytlık segment boyutu kullanılan seyrek matrislerde SSS ile olan %22,53 oranındaki ortalama sıkıştırma oranına ek olarak, ortalama %21,97 ek sıkıştırma oranı ve SSSt veri yapısı kullanıldığında ise %22,01 olarak elde edilen ortalama sıkıştırma oranına ek olarak ortalama %22,60 ek sıkıştırma oranına ulaşılmıştır. Segmentlere ayırarak SSS (SSSS) veya SSSt (SSSSt) veri yapısındaki seyrek matris hücrelerine erişim zamanlarının karşılaştırılmasında ise önemli oranlarda performans artışı gözlemlenmiştir. Performans artışları Segmentlere ayırarak Satır bazlı karşılaştırmalarda en fazla 255 çarpan katına kadar ve Segmentlere ayırarak Sütun bazlı karşılaştırmalarda en fazla 245 çarpan katına kadar olmuştur.

Abstract:
A sparse matrix is a matrix where most of its elements are zeros. When operations using standard dense matrix structures and algorithms are applied to large sparse matrices, the operations and memory are slow and inefficient as they are wasted with repeated zeros. When storing and processing sparse matrices on a computer, it is necessary to use specialized algorithms and data structures that take advantage of the sparse nature of the matrix. Sparse data is inherently more easily compressed and therefore requires significantly less storage. In this thesis, various methods for storing sparse matrices and accessing stored matrix elements are analyzed in detail. As a result of this analysis, a new segmented compression-oriented method is developed that outperforms existing methods in both efficient storage and efficient retrieval of matrix elements of sparse matrices. A simulation environment has been developed to evaluate the existing compression algorithms with the segmented compression algorithms we have developed in this study for sparse matrix storage and access to stored information. The data used in the simulation environment are all sparse matrices available as of 01/03/2024 in the SuiteSparse Matrix Collection data base, which contains reference sparse matrix data previously used for similar studies. As a result of the comparisons made within the scope of the results obtained from the simulation environment; In addition to the Compressed Sparse Row (CSR) or Column (CSC) compression ratios, an average additional compression ratio of 21.97% was achieved in addition to the average compression ratio of 22.53% with CSR, and an average additional compression ratio of 22.60% in addition to the average compression ratio of 22.01% when using the CSC data structure in sparse matrices using a 2-byte segment size. Significant performance improvements were observed when comparing the access times to sparse matrix cells in the segmented CSR or CSC data structure. The performance gains were up to a maximum of 255 multipliers for Segmented Row-based comparisons and up to 245 multipliers for Segmented Column-based comparisons.