Geri Dön

Analysis of a distributed algorithm for solving linear equations

Doğrusal denklemlerin çözümü için kullanılan dağıtık bir algoritmanın analizi

  1. Tez No: 570183
  2. Yazar: OSMAN MECNUN DURU
  3. Danışmanlar: DR. ÖĞR. ÜYESİ ONUR CİHAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Elektrik ve Elektronik Mühendisliği, Computer Engineering and Computer Science and Control, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2019
  8. Dil: İngilizce
  9. Üniversite: Marmara Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Elektrik Elektronik Mühendisliği Bilim Dalı
  13. Sayfa Sayısı: 67

Özet

Doğrusal bir denklem sistemini çözmek, bilim ve mühendislikteki en bilinen ve en önemli sorunlardan biridir. Bu tarz sistemlerin, öngörme, kestirim ve doğrusal olmayan denklemlerin doğrusal yaklaşımları gibi sayısız uygulamaları vardır. Bu sistemlerin çözümü için literatürde, büyük doğrusal denklem sistemlerini küçük parçalara bölen ve merkezi bir işlemci ile çözmekten daha hızlı ve daha doğru bir şekilde çözülmelerini sağlayan çeşitli dağıtık algoritmalar önerilmiştir. Bu algoritmaların temel fikri, sistemi, özerk etmenlerin birbirlerinden fiziksel olarak ayrıldığı ve yakındaki komşularıyla iletişim kurduğu çok etmenli bir ağ yapısı olarak görmektir. Ağ, her bir etmenin sadece denklemin bir alt kümesini bildiği birden fazla etmenden oluşur ve bu nedenle hiçbiri toplam denklemi ayrı ayrı çözemez.. Bu sorunun üstesinden gelmek için, tüm etmenler dağıtık bir şekilde işbirliği içinde çalışmalıdır. Her i etmeninin R^n de değerler alan bir çözüm vektörü x_i (t) vardır ve etmen i nin komşusu j den aldığı tek bilginin, onun durum vektörü olduğu varsayılmaktadır. Bu tezin amacı, doğrusal cebirsel denklem kümesini çözmek için [1]'de önerilen dağıtık algoritmayı geliştirmek ve yakınsama oranını araştırmaktır. Bu tezde, dağıtık bir algoritma ele alınmış ve iletim gecikmeleri olan ve olmayan ağlardaki yakınsaklık oranları incelenmiştir. Her iki durum için yeni ve hızlı bir yöntem önerilmiştir. Literatürdeki iyi bilinen bir algoritmanın yakınsama oranı ve bu tezde önerilen algoritmanın yakınsama oranı gecikmesiz ve gecikmeli ağlar için karşılaştırılmıştır. Ayrıca, ağırlıklandırma yöntemlerinin algoritmanın yakınsama oranı üzerindeki etkisi de birkaç önemli ağ topolojisi için incelenmiştir ve ele alınan tüm topolojiler için, rastgele yürüyüş yönteminin, örnek denklem sistemi için en hızlı yakınsamayı sağladığı gösterilmiştir.

Özet (Çeviri)

Solving a linear equation system is one of the most known and important problems in science and engineering. Such systems have numerous applications such as forecasting, estimation and linear approaches to nonlinear equations. For the solution of these systems, several distributed algorithms have been proposed in the literature, which divide large linear equation systems into small pieces and enable them to be solved faster and more accurately than solving it by a centralized processor. The basic idea of these algorithms is to consider the system as a multi-agent network structure where the autonomous agents are physically separated from each other and communicate with their neighbors nearby. The network consists of multiple agents, each agent knows only a subset of the equation and therefore none can solve the overall equation individually. In order to overcome this issue, all agents must work cooperatively in a distributed way. Each agent i has a solution vector x_i (t) that takes values in R^n, and it is assumed that the only information that the agent receives from its neighbor j is its state vector. The aim of the thesis is to upgrade a well-known distributed algorithm in [1] for solving a linear algebraic equation and investigate its convergence rate. In this thesis, we consider a distributed algorithm and examine its convergence rate in networks with and without transmission delays. A new rapid method is proposed for both cases. Convergence rates of a well-known algorithm in the literature and the one proposed in this thesis are compared for un-delayed and delayed networks. Furthermore, the effect of weighting strategies on the convergence rate of the algorithm is investigated for several important network topologies as well and it is shown that for all topologies under consideration, the random walk method yields the fastest convergence for the example equation system.

Benzer Tezler

  1. Kaynak kısıtlı proje çizelgeleme probleminde tekrarsız kromozom destekli paralel genetik algoritma uygulaması

    A parallel genetic algorithm application with nonrepetitive chromosome improvement for resource constrained project scheduling problem

    ŞAFAK EBESEK

    Doktora

    Türkçe

    Türkçe

    2019

    Mimarlıkİstanbul Teknik Üniversitesi

    Mimarlık Ana Bilim Dalı

    PROF. DR. HAKAN YAMAN

  2. Large deflections of non-linear bi-modulus functionally graded beams under different boundary and loading conditions

    Doğrusal olmayan çift modüllü fonksiyonel derecelendirilmiş kirişlerin farklı sınır koşulları ve yüklemeler altındaki büyük yer değiştirmeleri

    AYHAN HACIOĞLU

    Doktora

    İngilizce

    İngilizce

    2023

    Makine Mühendisliğiİstanbul Teknik Üniversitesi

    Makine Mühendisliği Ana Bilim Dalı

    PROF. DR. CEMAL BAYKARA

  3. Hücresel yapay sinir ağları için iki öğrenme algoritması ve görüntü işleme uygulamaları

    Two learning algorithms for cellular neural networks and their image processing applications

    SİNAN KARAMAHMUT

    Yüksek Lisans

    Türkçe

    Türkçe

    1994

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    DOÇ.DR. CÜNEYT GÜZELİŞ

  4. Kiriş problemleri sonlu elemanlar yöntemi ile çözümü

    The Solution of beam problems with finite element method

    OSAMA A.SALEH ABDALLA

    Yüksek Lisans

    Türkçe

    Türkçe

    1995

    Makine MühendisliğiMarmara Üniversitesi

    YRD. DOÇ. DR. İSMAİL BİNİCİ

  5. Düzgün yayılı yük etkisindeki betonarme plakların sonlu elemanlar yöntemi ile doğrusal olmayan hesabı

    Finite elements method for the non-linear analysis of reinforced concrete plates subjected to uniformly distributed loads

    KUTLU DARILMAZ

    Yüksek Lisans

    Türkçe

    Türkçe

    1997

    İnşaat Mühendisliğiİstanbul Teknik Üniversitesi

    Yapı Ana Bilim Dalı

    PROF. DR. NAHİT KUMBASAR