Clustering based approach for efficient AATx computations
AATx'in verimli hesaplanması için gruplamaya dayalı yaklaşım
- Tez No: 112583
- Danışmanlar: PROF. DR. CEVDET AYKANAT
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- 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
- Yıl: 2001
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- 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
- Optimal energy efficient sensor network design
Algılayıcı ağ tasarımı
RAED S.M. DARAGHMA
Doktora
İngilizce
2016
Elektrik ve Elektronik MühendisliğiAnadolu ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. NURAY AT
- 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
2018
Endüstri ve Endüstri MühendisliğiErciyes ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. BANU SOYLU
- 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
2010
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolFırat ÜniversitesiElektronik-Bilgisayar Eğitimi Ana Bilim Dalı
DOÇ. DR. ABDULKADİR ŞENGÜR
- 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
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
YRD. DOÇ. ENGİN YEŞİL
- Hiperspektral görüntülerin eğiticisiz bölütlenmesi
Unsupervised segmentation of hyperspectral images
GÖKHAN BİLGİN
Doktora
Türkçe
2009
Bilim ve TeknolojiYıldız Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. SARP ERTÜRK
PROF. DR. TÜLAY YILDIRIM