Parallelization of an interior point algorithm for linear programming
Bir iç nokta doğrusal programlama algoritmasının paralelleştirilmesi
- Tez No: 33495
- Danışmanlar: YRD. 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: Doğrusal Programlama, İç Nokta Algoritmaları, Dağı- tık Sistemler, Paralel İşleme, Linear Programming, Interior Point Algorithms, Distributed Systems, Parallel Processing
- Yıl: 1995
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar ve Enformatik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 83
Özet
Bu çalışmada, Karmarkar-tipi bir doğrusal programlama optimizasyon algoritması olan Mehrotra'nın predictor-corrector iç nokta algoritmasının paralelleştirilmesi sunulmaktadır. Algoritmanın içerdiği işlem tipleri belirlenmiş ve her işlem tipi için paralel algoritmalar sunulmuştur. Karmarkar-tipi algoritmaların işlem ağırlığını oluşturan büyük simetrik doğrusal denklem kümelerinin çözümü detaylı incelenmiştir. Birçok ileri ve geri çözüm algoritması test e- dilmiş, bir biriktirmeli geri çözüm algoritması geliştirilmiştir. Seyrek matris- vektör çarpımı ve faktörizasyon işlemlerinin dağıtımı için sezgisel bin-packing algoritmaları kullanılmıştır. Performans sonuçlan en iyi olan algoritmalar doğrusal programlama problemlerinin çoklu bilgisayarlarda paralel çözümü için bir sistem geliştirilmesinde kullanılmıştır. Dizayn kıstasları ve uygulama de tayları tartışılmış, bazı performans sonuçları sunulmuştur.
Özet (Çeviri)
In this study, we present the parallelization of Mehrotra's predictor-corrector interior point algorithm, which is a Karmarkar-type optimization method for linear programming. Computation types needed by the algorithm are identi fied and parallel algorithms for each type are presented. The repeated solution of large symmetric sets of linear equations, which constitutes the major com putational effort in Karmarkar-type algorithms, is studied in detail. Several forward and backward solution algorithms are tested, and buffered backward solution algorithm is developed. Heurustic bin-packing algorithms are used to schedule sparse matrix- vector product and factorization operations. Algo rithms having the best performance results are used to implement a system to solve linear programs in parallel on multicomputers. Design considerations and implementation details of the system are discussed, and performance results are presented from a number of real problems.
Benzer Tezler
- Hibrit bir kripto algoritmasının paralelleştirilerek çok çekirdekli işlemcilerin performansının analiz edilmesi
Analyzing performance of multicore processors by parallelization of a hibrid crypto algorithm
ECEM İREN
Yüksek Lisans
Türkçe
2014
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiBilgisayar Mühendisliği Bölümü
DOÇ. DR. AYLİN KANTARCI
- Evolutionary design assistants for architecture
Mimarlık için evrimsel tasarım asistanları
N. ONUR SÖNMEZ
Doktora
İngilizce
2015
Mimarlıkİstanbul Teknik ÜniversitesiMimarlık Ana Bilim Dalı
PROF. DR. ARZU ERDEM
PROF. DR. İKBAL SEVİL SARIYILDIZ
- Gridification of earthquake location finding and regional fault plane solution applications
Deprem yerini bulma ve bölgesel fay düzlemi çözümü uygulamalarının gridleştirilmesi
BİLAL BEKTAŞ
Yüksek Lisans
İngilizce
2013
Mühendislik BilimleriBoğaziçi ÜniversitesiHesaplamalı Bilimler ve Mühendislik Ana Bilim Dalı
PROF. DR. CAN ÖZTURAN
- Parallel hardware and software implementations for electromagnetic computations
Elektromanyetik hesaplamaları için paralel donanım ve yazılım uygulamaları
ALİ RIZA BOZBULUT
Yüksek Lisans
İngilizce
2005
Elektrik ve Elektronik Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
PROF. DR. LEVENT GÜREL
- Parallel direct volume rendening of unsructed grids based on object-space decomposition
Düzensiz ızgaraların obje uzayı bölünmesine dayanan paralel hacim görüntülenmesi
FERİT FINDIK
Yüksek Lisans
İngilizce
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiDOÇ. DR. CEVDET AYKANAT