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, Dağıtık sistemler, Paralel işlemciler, Linear Programming, Interior Point Algorithms, Distributed Systems, Parallel Processing, Parallel processors
- Yıl: 1995
- 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ı: Belirtilmemiş.
Ö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
- 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
- Parallelization of hierarchical radiosity algorithms on distributed memory computers
Dağınık bellekli bilgisayarlarda sıradüzensel ışıma algoritmalarının paralelleştirilmesi
AHMET REŞAT ŞİRELİ
Yüksek Lisans
İngilizce
1999
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Yazılımı Ana Bilim Dalı
YRD. DOÇ. DR. ATTİLA GÜRSOY
- Parallelization of the fast multipole solution of the electromanyetic scattering problem
Elektromanyetik saçılım probleminin hızlı multipole çözümü paralelleştirme
ALİ AYUB KALUFYA
Yüksek Lisans
İngilizce
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT
- Dağıtılmış nesnesel birim modeli üzerinde görüntü işleme algoritmalarının paralelleştirilmesi
Parallelization of image processing algorithms using distributed components object model
SAVAŞ KÖSE
Yüksek Lisans
Türkçe
1999
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ.DR. NADİA ERDOĞAN
- Pararllel rendering algorithms for distributed-memory multicomputers
Çok işlemcili dağıtık hafızalı bilgisayarlarda paralel görüntüleme algoritmaları
TAHSİN MERTEFE KURÇ
Doktora
İngilizce
1997
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. CEVDET AYKANAT