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ı, Sparse matrix clustering algorithms, matrix-matrix-transpose- vector computation schemes, sparse matrix data structures
  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ı: 65

Ö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. Optimal energy efficient sensor network design

    Algılayıcı ağ tasarımı

    RAED S.M. DARAGHMA

    Doktora

    İngilizce

    İngilizce

    2016

    Elektrik ve Elektronik MühendisliğiAnadolu Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    DOÇ. DR. NURAY AT

  2. Depo raf yerleşim problemi ve kümeleme temelli bir yaklaşım

    Warehouse shelf assignment problem and a clustering based approach

    ÖMER DEMİRCAN

    Yüksek Lisans

    Türkçe

    Türkçe

    2018

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

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

    PROF. DR. BANU SOYLU

  3. Nötrozofi yaklaşımı ve dalgacık dönüşümü ile renkli doku görüntülerinin bölütlenmesi

    Color texture image segmentation by using neutrosophic approach and wavelet transform

    KAZIM HANBAY

    Yüksek Lisans

    Türkçe

    Türkçe

    2010

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolFırat Üniversitesi

    Elektronik-Bilgisayar Eğitimi Ana Bilim Dalı

    DOÇ. DR. ABDULKADİR ŞENGÜR

  4. Tip-2 bulanık öbekleme yöntemleri ile zaman serilerinin modellenmesi

    Time series modelling with Type-2 fuzzy clustering methods

    MEHMET FURKAN DODURKA

    Yüksek Lisans

    Türkçe

    Türkçe

    2014

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Kontrol ve Otomasyon Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. ENGİN YEŞİL

  5. Hiperspektral görüntülerin eğiticisiz bölütlenmesi

    Unsupervised segmentation of hyperspectral images

    GÖKHAN BİLGİN

    Doktora

    Türkçe

    Türkçe

    2009

    Bilim ve TeknolojiYıldız Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    PROF. DR. SARP ERTÜRK

    PROF. DR. TÜLAY YILDIRIM