Geri Dön

Clustering based approach for efficient AATx computations

AATx'in verimli hesaplanması için gruplamaya dayalı yaklaşım

  1. Tez No: 112583
  2. Yazar: BÜLENT ÖZEL
  3. Danışmanlar: PROF. DR. CEVDET AYKANAT
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: matris-matris-transpoz-vektör hesabı, seyrek matris kümeleme algoritması, seyrek matris veri yapıları, Kümeleme, Matrisler, Sparse matrix clustering algorithms, matrix-matrix-transpose- vector computation schemes, sparse matrix data structures, Clustering, Matrices
  7. Yıl: 2001
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: Belirtilmemiş.

Özet

IV ÖZET AATx'in VERİMLİ HESAPLANMASI İÇİN GRUPLAMAYA DAYALI YAKLAŞIM Bülent Özel Bilgisayar Mühendisliği, Yüksek Lisans Tez Yöneticisi: Prof. Dr. Cevdet Aykanat Eylül, 2001 Birçok bilimsel uygulama, bir seyrek dikdörtgensel matrisin aynı matrisin transpozunun bir vektör ile defalarca çarpılmasını içermektedir. Bu bileşik işlem iki yol izlenerek yapılabilir. Birincisinde y = ATx ve z = Ay gibi iki seyrek matris vektör çarpımı her bir tekrarlama sırasında yapılır, ikincisinde ise, tekrarli çarpma işlemine girmeden hemen önce B - AAT gibi bir matris oluşturulur. Daha sonra, her bir tekrar adımında z = Bx çarpımı yapılır. Bu ikinci yolda oluşturulan B matrisi A matrisinden daha çok sıfırdan farklı ele mana sahip olacağı için genellikle bu ikinci yolda yapılan z = Bx çarpımı ilk yolda yapılan iki matris vektör çarpımından daha uzun sürmektedir. Bazı ma trislerde seyreklik yapısına bağlı olarak ikinci yolda yapılan iş daha az olmak tadır. Bu çalışmada önerilen gruplama algoritmaları ile A matrisi alt matrislere ayrıştırılmış ve her bir alt matris için yukarıda adı geçen çarpma yollarının hangisinin kullanılacağı yine bu çalışmada önerilen ölçekler ile belirlenmiş ve verilen bir matrisi iki çarpma yolunu da kullanarak çarpan melez bir algoritma önerilmiştir. Gruplama problemi seyrek matrislerin iki parçalı çizge modelleri kul lanılarak ele alınmıştır. Önerilen gruplama algorithmaları A matrisine tekrarlı çarpma işleminden önce uygulanmış ve değişik uygulama alanlarından örneklenen bir çok matris üzerinde sınanmıştır. Matris elemanı çarpma- toplama işleminde yüzde 17'lere varan azalma sağlanmıştır.

Özet (Çeviri)

Ill ABSTRACT CLUSTERING BASED APPROACH FOR EFFICIENT AATx COMPUTATION Bülent Özel M.S. in Computer Engineering Supervisor: Prof. Dr. Cevdet Aykanat September, 2001 Many scientific applications involve repeated sparse matrix-matrix-transpose- vector multiplication computations. These computations are carried out by following two schemes. In the first one, two successive sparse matrix multipli cations in the form of y = ATx and z = Ay are performed at each iteration. In the second one, matrix B = AAT is obtained prior to the iterations and then the matrix-vector multiply z - Bx is performed at each iteration. Matrix B is usually denser than the A matrix, and hence the computation z = Bx is more expensive then the afore mentioned successive products. In some cases, due to sparsity pattern öf the A matrix, the computation z = Bx may require lesser computation time. In this work, we propose clustering metrics and algo rithms to decompose the A matrix into blocks to use both of the computation schemes in order to reduce the computation time. We give a hybrid algorithm for computing z = AATx that combines the two computation schemes. The clustering problem is modelled using bipartite graph representation of sparse matrices. Efficient algorithms are proposed based on the metrics and as pect ratios that measure the extra multiply-and-add operations and encourage the formation of blocks that are suitable for the hybrid scheme. The clustering algorithms are applied once to matrix A as a preprocessing step before the repeated matrix-matrix-transpose-vector computations. Very promising im provements on sparse matrices from various collections are obtained, where up to 17% reductions in the number of multiply-and-add operations are observed.

Benzer Tezler

  1. Tez No

    982204

    Clustering-based heuristics for efficient meter reading planning in electricity distribution networks

    Elektrik dağıtım şebekelerinde etkin sayaç okuma planlaması için kümeleme tabanlı sezgisel yöntemler

    BURAK KARA

    Yüksek Lisans

    İngilizce

    İngilizce

    2025

    Endüstri ve Endüstri MühendisliğiÖzyeğin Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. İHSAN YANIKOĞLU

  2. Tez No

    276651

    Query based energy efficient clustering methods for wireless sensor networks

    Kablosuz algılayıcı ağları için sorguya dayalı enerji etkin kümeleme yöntemleri

    ONUR KOŞAR

    Yüksek Lisans

    İngilizce

    İngilizce

    2011

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilişim Sistemleri Bölümü

    DOÇ. DR. ALTAN KOÇYİĞİT

  3. Tez No

    787671

    A hybrid approach for data classification based on mathematical modelling and improved online learning algorithm for general fuzzy min-max neural network

    Genel bulanık min-maks sinir ağları için gelişmiş çevrimiçi öğrenme algoritmasına ve matematiksel modellemeye dayalı veri sınıflandırması için hibrit bir yaklaşım

    ÖMER NEDİM KENGER

    Doktora

    İngilizce

    İngilizce

    2023

    Endüstri ve Endüstri MühendisliğiGaziantep Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. EREN ÖZCEYLAN

  4. Tez No

    450932

    An approach for energy efficient retrofits evaluation of educational buildings through life-cycle cost optimization in Turkey

    Türkiye'deki eğitim yapılarının yaşam döngüsü maliyet optimizasyonu ile enerji etkin yenilenmesi için bir yaklaşım

    YİĞİT YILMAZ

    Doktora

    İngilizce

    İngilizce

    2017

    Enerjiİstanbul Teknik Üniversitesi

    Mimarlık Ana Bilim Dalı

    PROF. DR. GÜL KOÇLAR ORAL

  5. Tez No

    711174

    Fuzzy clustering based ensemble learning approach: Applications in digital advertising

    Bulanık kümeleme tabanlı topluluk öğrenmesi yaklaşımı: Dijital reklam alanında uygulamalar

    AHMET TEZCAN TEKİN

    Doktora

    İngilizce

    İngilizce

    2021

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    İşletme Mühendisliği Ana Bilim Dalı

    PROF. DR. FERHAN ÇEBİ

    PROF. DR. TOLGA KAYA

Geri Dön