Decomposing linear programs for parallel solution
Doğrusal programların paralel çözümleme içim bölünmesi
- Tez No: 50009
- Danışmanlar: DOÇ.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: Seyrek Matris, Block Açısal Durum, Hiperçizge Parçalama, Düğüm Ayıracıyla Çizge Parçalama iv, Doğrusal programlama, Grafikler, Sparse Matrices, Block Angular Form, Hypergraph Partitioning, Graph Partitioning by Node Separator in, Linear programming, Graphics
- Yıl: 1996
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Belirtilmemiş.
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: Belirtilmemiş.
Özet
ÖZET DO?RUSAL PROGRAMLARIN PARALEL ÇÖZÜMLEME İÇİN BÖLÜNMESİ Ali Pınar Bilgisayar ve Enformatik Mühendisliği, Yüksek Lisans Danışman: Doç. Dr. Cevdet Aykanat Temmuz, 1996 Birçok güncel araştırma büyük ölçekli problemlerin matrislerinde sıkça rast lanan seyreklikten daha iyi yararlanmaya dayalıdır. Bu araştırma, seyrek bir ma trisi belli sayıda eşit büyüklükte bloklardan oluşan blok açısal duruma çevirmek için değişik metodlar önermektedir. Bu problemin önemli bir uygulaması doğrusal programlamadadır. Doğrusal programlamada, varolan blok açısal yapılan kul lanan birçok çözüm yöntemi önerilmiştir. Ama bu yöntemler yalnızca varolan blok açısal duruma dayandıkları için ölçeklendirme sorunuyla karşı karşıyadırlar. Bu çalışma bölünme için iki hiperçizge modeli öneriyor, ve bu modeller prob lemi iyi bilinen hiperçizge parçalama problemine indirgiyor. Önerilen bir diğer model ise çizge modeli, ve bu model de problemi düğüm ayıracıyla çizge parçalama problemine indirgiyor. Önerilen modeller, çok sayıda çok büyük ölçekli matris leri bölmede denendi. Hem çözüm kalitesi, hem de zaman açısından çok çekici sonuçlar elde edildi.
Özet (Çeviri)
ABSTRACT DECOMPOSING LINEAR PROGRAMS FOR PARALLEL SOLUTION Ali Pmar M. S. in Computer Engineering and Information Science Supervisor: Assoc. Prof. Cevdet Aykanat July, 1996 Many current research efforts axe based on better exploitation of sparsity - common in most large scaled problems - for computational efficiency. This work proposes different methods for permuting sparse matrices to block angular form with specified number of equal sized blocks for efficient parallelism. The problem has applications in linear programming, where there is a lot of work on the so lution of problems with existing block angular structure. However, these works depend on the existing block angular structure of the matrix, and hence suf fer from unscalability. We propose two hypergraph models for decomposition, and these models reduce the problem to the well-known hypergraph partitioning problem. We also propose a graph model, which reduces the problem to the graph partitioning by node separator problem. We were able to decompose very large problems, the results are quite attractive both in terms solution quality and running times.
Benzer Tezler
- Analitik hiyerarşi prosesi yardımıyla kalite fonksiyon açınımında önceliklendirme
Başlık çevirisi yok
CEM GÖRKEM ÖZARPACI
Yüksek Lisans
Türkçe
1998
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ETHEM TOLGA
- Elektrik güç sistemlerinde durum kestirimi
Electrical power system state estimation
YEŞİM NEMLİOĞLU
Yüksek Lisans
Türkçe
1993
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. NESRİN TARKAN
- Dijital işaret işleme ve FIR filtre tasarımı algoritmaları
Digital signal processing and FIR filter design algorithms
METİN KALAYCI
Yüksek Lisans
Türkçe
1992
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ. DR. MEHMET BÜLENT ÖRENCİK
- EMG işaretlerinden motor birim aksiyon potansiyellerinin ayrıştırılması
Decomposition of motor unit action potantials from EMG signals
İBRAHİM MUSTAFA EKİN
Yüksek Lisans
Türkçe
1997
Elektrik ve Elektronik MühendisliğiKaradeniz Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. TEMEL KAYIKÇIOĞLU
- Homomorfik filtreleme ile EKG analizi
Başlık çevirisi yok
HÜSEYİN HIZ
Yüksek Lisans
Türkçe
1995
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. MEHMET KORÜREK