In this thesis, we are concerned with the image restoration problem which hasbeen formulated in the literature as a system of linear inequalities. With this for-mulation, the resulting constraint matrix is an unstructured sparse-matrix andeven with small size images we end up with huge matrices. So, to solve therestoration problem, we have used the surrogate constraint methods, that canwork eï¬ciently for large size problems and are amenable for parallel implemen-tations. Among the surrogate constraint methods, the basic method considers allof the violated constraints in the system and performs a single block projectionin each step. On the other hand, parallel method considers a subset of the con-straints, and makes simultaneous block projections. Using several partitioningstrategies and adopting diï¬erent communication models we have realized severalparallel implementations of the two methods. We have used the hypergraph par-titioning based decomposition methods in order to minimize the communicationcosts while ensuring load balance among the processors. The implementationsare evaluated based on the per iteration performance and on the overall perfor-mance. Besides, the eï¬ects of diï¬erent partitioning strategies on the speed ofconvergence are investigated. The experimental results reveal that the proposedparallelization schemes have practical usage in the restoration problem and inmany other real-world applications which can be modeled as a system of linearinequalities.Keywords: Parallel image restoration, distortion, parallel algorithms, linear feasi-bility, surrogate constraint method, hypergraph partitioning, rowwise partition-ing, checkerboard partitioning, ï¬ne-grain partitioning, point-to-point communi-cation, all-to-all communication, convergence rate.

Bu şalışmada, doğrusal eşitsizlikler sistemine dünüştürülmüş olan gürüntücs g s o us u u us ou uonarımı problemi uzerinde durulmuştur. Bu yüntemle elde edilen matrisler belliü s obir yapısal dizilime sahip olmayan seyrek matrislerdir. Ayrıca, küşuk ülşekliuc ü o cgürüntülerde dahi şok büyük ülşekli matrisler oluşmaktadır. Dolayısıyla, prob-ou u c u u oc slemin şozümünde, büyük ülşekli problemler işin verimli şalışabilen ve paralelcü u u u u oc c csügerşekleştirmelere uygun olan aracı kısıtlar yüntemleri kullanılmıştır. Onerilenc s o syüntemler arasından, sağlanmayan kısıtların tümünü dikkate alan ve her adımdao g u uutek bir izdüşum gerşekleştiren temel yüntem ve sağlanmayan kısıtların altus ü c s o gkümelerini dikkate alıp oluşan izdüşumlerin dışbükey birleşimini alan paralelu s usü su syüntem kullanılmıştır. Ceşitli bülümleme stratejileri ve farklı iletişim model-o s şs ou sleri kullanılarak bir şok paralel gerşekleştirimler yapılmıştır. Hiper-şizge temellic c s s cbülümlemeler kullanılarak iletişim maliyeti azaltılırken işlemciler arasındaki yükou s s udengesi sağlanmıştır. Gerşekleştirimler yineleme bazında ve toplam bazdag s c sdeğerlendirilmiştir. Aynı zamanda, bülümlemelerin yakınsama hızına olan etkisig s ouaraştırılmıştır. Deney sonuşları, ünerilen paralel yüntemlerin, gürüntü onarımıs s c o o ou uprobleminde ve doğrusal eşitsizlikler sistemine şevrilebilen gerşek uygulamalardag s c cpratik kullanımı olduğunu güstermiştir.Anahtar süzcükler : Paralel gürüntü onarımı, bozunum, paralel algoritmalar, li-ou ou uneer ï¬zibilite, aracı kısıtlar yüntemi, hiper-şizge parşalama, sırasal parşalama,o c c cdamatahtası parşalama, ince tane parşalama, noktasal iletişim, herkes-herkesec c siletişim, yakınsama hızı.s

101