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
- 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
- Parallelization of noise subspace-based doa estimation algorithms on CPU and GPU
Gürültü altuzayı tabanlı DOA kestirim algoritmalarının CPU ve GPU üzerinde parallelleştirilmesi
HAMZA ERAY
Yüksek Lisans
İngilizce
2021
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiModelleme ve Simülasyon Ana Bilim Dalı
PROF. DR. ALPTEKİN TEMİZEL
- 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 forward and inverse problems of electro-magnetic source imaging of the human brain
Elektro-manyetik kaynak görüntüleme ileri probleminin paralel bilgisayar ortamında çözülmesi
CAN ERKİN ACAR
Doktora
İngilizce
2003
Elektrik ve Elektronik MühendisliğiOrta Doğu Teknik ÜniversitesiElektrik-Elektronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. NEVZAT GÜNERİ GENÇER
- Parallelization of functional flow to predict protein functions
Protein fonksiyon tahminlemesi için fonksiyonel akış yönteminin paralelleştirilmesi
EMRAH AKKOYUN
Yüksek Lisans
İngilizce
2011
BiyoistatistikOrta Doğu Teknik ÜniversitesiTıp Bilişimi Ana Bilim Dalı
YRD. DOÇ. DR. TOLGA CAN