Development of fused parameter optımızatıon algorıthm for two- and three-parameter eıgenvalue problems
İki- ve üç-parametreli özdeğer problemleri için birleşik parametre optimizasyon algoritması geliştirilmesi
- Tez No: 980046
- Danışmanlar: PROF. DR. AHMET DURAN
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Matematik, Computer Engineering and Computer Science and Control, Mathematics
- Anahtar Kelimeler: Adi diferensiyel denklemler, Cebirsel matris denklemleri, Helmholtz denklemi, Kısmi diferensiyel denklemler, Paralel algoritmalar, Parametre optimizasyonu, Sayısal yöntemler, Özdeğer problemleri, Ordinary differential equations, Algebraic matrix equations, Helmholtz equation, Partial differential equations, Parallel algorithms, Parameter optimization, Numerical methods, Eigenvalue problem
- Yıl: 2025
- Dil: İngilizce
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Lisansüstü Eğitim Enstitüsü
- Ana Bilim Dalı: Matematik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Matematik Mühendisliği Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
Günümüzde, bilim ve teknolojideki çalışma konularından biri çok parametreli özdeğer problemleri (MuPEP'ler) olduğu görülmektedir. Bu problemler gecikmeli diferansiyel denklemlerin kararlılığı, güç akışı denklemi, dinamik model güncelleme problemi, aeroelastik flutter problemleri, otoregresif-hareketli ortalama (ARMA) model tanımlaması ve stokastik oyunlar vb. gibi çeşitli uygulamalarda görülmektedir. MuPEP'ler, böylesi çeşitli uygulamalardaki sınır değer problemlerini çözmek için değişkenlerin ayrılması yönteminin kullanıldığı durumlarda ortaya çıkmaktadır. Dolayısıyla, bu tez çalışmasında iki- ve üç-parametreli özdeğer problemlerine odaklandık. MuPEP'lerin kolayca çözülebilmesi için Kronecker çarpımı yardımıyla bu problemleri genelleştirilmiş özdeğer problemleri sistemine indirgemek mümkündür. Ancak Kronecker çarpımında zaman ve bellek kullanımı bakımından ciddi maliyetler ortaya çıkmaktadır. Bu çarpımda zaman maliyetini önemli ölçüde azaltmak için paralel programlama kullanma (Bölüm 5) gibi bazı yöntemler olmasına rağmen, doğrudan MuPEP'leri çözen sayısal yöntemlere odaklanmak daha uygundur. Bu nedenle, bu problemler için sayısal çözümlerin geliştirilmesi önemli bir ihtiyaçtır. Newton Yöntemi, çok parametreli özdeğer problemlerini çözmede kullanılan sayısal yöntemlerden biri olarak kabul edilir. Bu yöntem MuPEP'lerin çözümü için başarılı bir yöntem olmasına rağmen, bazı durumlarda hesaplama maliyeti veya yakınsama problemleri gibi sorunlarla karşılaşıyoruz. Özellikle, Newton yöntemini kullanarak büyük ölçekli yoğun matrisleri içeren MuPEP'leri çözmedeki zorluklar dikkatimizi çekmektedir. Bu durumun temel nedeni, Newton yönteminde problemin boyutu büyüdüğünde yeterince doğru başlangıç koşullarını belirlemenin zorlaşmasıdır. Bilindiği gibi Newton yönteminin hızla yakınsayabilmesi için iterasyonların çözüme yeterince yakın bir noktadan başlaması gerekir. Literatürde tansör Rayleigh bölümü küçük ve orta ölçekli matrisleri içeren problemlerde başlangıç özdeğerlerin belirlenmesinde önerilen bir yöntemdir. Bu çalışmamızda büyük ölçekli matrisleri içeren problemler ile yaptığımız simülasyonlarda tensör Rayleigh bölümünün her zaman yeterli olmadığını gözlemliyoruz. Dolayısıyla, bu durum büyük ölçekli matris içeren problemler için etkili bir çözüm üretme gereksinimini ortaya çıkarmaktadır. Bu tez çalışmasında iki parametreli ve üç parametreli özdeğer problemleri için bir birleşik parametre optimizasyon (fusedparopt) algoritması öneriyoruz. Fusedparopt algoritmamızı tensör Rayleigh bölümü (RQ) ve en dik iniş (SD) tekniğini Newton yöntemi ile birleştirerek oluşturduk. Fusedparopt algoritmamızdaki bu birleşim için üç farklı yol sunuyoruz. Birinci yolda, probleme ait olan katsayı matrislerini ve başlangıç özvektörlerini kullanarak RQ ile başlangıç özdeğerlerini elde ettikten sonra başlangıç özdeğerleri ve özvektörleri SD tekniği ile optimize ederek sonrasında Newton iterasyonu ile çözüme ulaşabiliyoruz. İkinci yolda, RQ ile başlangıç özdeğerlerini elde ettikten sonra Newton iterasyonu ile çözüme yakınsamaya çalışırken ıraksama veya durgunluk durumları oluştuğu esnada SD tekniği ile özdeğerleri ve özvektörleri optimize ederek devamında çözüme ulaşabiliyoruz. Üçüncü yolda ise birinci ve ikinci yolda bahsedilen optimizasyonları birlikte yaparak çözüme ulaşabiliyoruz. Bu şekilde sunduğumuz yönteme fusedparopt_SD diyoruz. Bununla birlikte literatürde iki parametreli ve üç parametreli özdeğer problemlerinde SD tekniğinin yakınsaması hakkında görebildiğimiz kadarıyla bir teorem bulamadık. Bu sebeple, çalışmamızda bu problemler üzerinde SD tekniğinin yakınsamasını gösteren yeni teoremler sunuyoruz. Ayrıca, SD tekniğine alternatif olarak Sınırlı hafızalı Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) yöntemini çalışmamızda inceledik. L-BFGS yönteminin tek başında çok parametreli özdeğer problemlerinde etkili olamayacağını gözlemledik. Buna rağmen, birleşik algoritmamızda fusedparopt_SD yöntemine alternatif olarak fusedparopt_LBFGS yöntemini çok parametreli özdeğer problemleri için önerebiliyoruz. Önerdiğimiz yöntemlerin uygulamalardaki etkisini görmek için iki parametreli özdeğer problemlerini içeren örnekler üzerinde testler yapıyoruz. Bu örnekler, Lamé sisteminden gelen katsayı matrisleri, rastgele oluşturulmuş genel matrisler ile yapılan simülasyonlar ve yakınsama diyagramlarından oluşmaktadır. Ayrıca önerdiğimiz fusedparopt algoritmamızı modern yöntemlerden tensör Rayleigh bölümü-Newton (RQ_N) yöntemi ve Matlab'ın MultiParEig paketinde yer alan twopareigs algoritmasıyla karşılaştırıyoruz. Algoritmamızın twopareigs yönteminden daha hızlı yakınsayabildiği durumları gözlemledik. RQ_N yöntemi ile yüksek maliyetli çözümlerin veya yakınsama sorunlarının oluştuğu durumlarda fusedparopt algoritmamız ile bu sorunların üstesinden gelerek daha verimli çözümler elde edebildik. Yakınsaklık diyagramlarında RQ_N yöntemi ile elde edilen çözümlerin daha fazla dalgalanmaya sahip olduğunu ve problem boyutu arttıkça dalgalanmaların büyüdüğünü görüyoruz. Ancak, fusedparopt yöntemi ile edilen sonuçlar daha az dalgalanma görülecek şekilde iyileşebiliyor. Fusedparopt_SD ve fusedparopt_LBFGS yöntemleriyle elde edilen sonuçların, matris türüne bağlı olarak birbirine yakın ve karşılaştırılabilir olduğu görülmektedir. Dolayısıyla, Fusedparopt_SD ve fusedparopt_LBFGS yöntemlerinin veri setimizdeki örnekler dikkate alındığında iki parametreli özdeğer problemleri için sağlamlık (robustness), makul maliyetli çözüm sunma ve ıraksama problemini azaltma gibi özelliklere sahip olduğunu görmekteyiz. Bu çalışmamızda önerdiğimiz yöntemi problemlerdeki tüm farklı özdeğer kümelerini ve özdeğerlere karşı gelen özvektörleri bulmayı sağlayacak şekilde geliştiriyoruz. Deterministik ızgara (grid) çoklu başlangıç yöntemi ve rastgele çoklu başlangıç yöntemi gibi çoklu başlangıç yöntemlerinden faydalanıyoruz. Bu iki yöntemi tüm farklı özdeğer kümelerini bulmak için fusedparopt algoritmamız ile birlikte kullanmayı öneriyoruz. Ayrıca farklı özdeğer kümeleri arasında katlı özdeğer kümeleri bulunabilir. Bu durumda, katlı özdeğerlere karşı gelen özvektörlerin farklılığını tespit edebilmek için bir benzerlik testi uygulaması önermekteyiz. Bu aşamada önerdiğimiz yöntemleri üç parametreli özdeğer problemlerini içeren örnekler üzerinde test ediyoruz. Testlerde küçük ölçekli matrisleri içeren problemler, büyük ölçekli matrisleri içeren problemler, singüler problemler veya singüler olmayan problemler gibi farklı tiplere sahip problemleri ele alıyoruz. Çoklu başlangıç yöntemleri ile geliştirdiğimiz fusedparopt algoritmamızı RQ_N yöntemi ve Matlab'ın MultiParEig paketinde yer alan modern algoritmalar ile karşılaştırıyoruz. Gerçek hayattan bir uygulama için elipsoidal dalga denkleminin ayrıklaştırılması ile elde edilen katsayı matrislerinden oluşan bir problemi ele alıyoruz. Bu problemin çözümüne dair sıkıntıları tartışıp, önerdiğimiz yöntemin problemin çözümünde sağladığı avantajları değerlendiriyoruz. Ayrıca, tüm farklı özdeğer kümelerini daha verimli bir şekilde hesaplamak için fusedparopt algoritmamızı ileri bir seviyeye taşıyoruz. Fusedparopt algoritmamızı çoklu-başlangıç yöntemlerinin avantajını kullanarak paralel hale getirmeyi öneriyoruz. Örneğin, Baer dalga denklemini ayrıştırıyoruz ve üç parametreli bir özdeğer problemi elde ediyoruz. Daha sonra bu problemi, Matlab'da dinamik iş parçacığı tabanlı paralel hesaplama ile fusedparopt algoritmamızı kullanarak çözüyoruz. Farklı iş parçacığı sayıları için hızlanma ve verimlilik grafiklerini inceliyoruz. Sonuç olarak günümüz bilim ve teknoloji dünyasındaki ilerlemeler, büyük ölçekli problemlerle ilgilenme ve bunları çözebilmeye dair ihtiyacı doğurmaktadır. Ancak, problemlerin boyutunun artması, çözüm maliyetlerinde (hesaplama süresi ve bellek ihtiyacı gibi) artışa neden olur. Bu durum, sadece problemleri çözmekle kalmayıp, aynı zamanda hızlı ve verimli bir şekilde bir çözüme ulaşmaya odaklanmayı da gerektirir. Bu nedenle, bu tezde önerilen birleşik algoritmalar, özellikle büyük ölçekli boyutlardaki çok parametreli özdeğer problemlerinde tüm veya hedef sayıda farklı özdeğer kümelerini ve bunlara karşılık gelen özvektörleri bulmak için hızlı, kararlı, sağlam ve düşük bellek kullanımı gibi avantajlara sahiptir.
Özet (Çeviri)
Nowadays, one of the issues of study in science and technology is multi-parameter eigenvalue problems (MuPEPs). These problems appear in a variety of applications such as stability of delay-differential equations, the power flow equation, dynamic model updating problem, aeroelastic flutter problems, autoregressive–moving-average (ARMA) model identification and stochastic games, etc. Moreover, MuPEPs arise in a variety of applications of these types when the method of separation of variables is used to solve boundary value problems. Therefore, we focus on two- and three-parameter eigenvalue problems. These problems can be reduced to a system of generalized eigenvalue problems by the Kronecker product and so they can be solved easily. However, Kronecker product needs serious costs in time and space. Although there are some methods such as using parallel programming to significantly reduce time cost in this product, it is more appropriate to focus on numerical methods that directly solve MuPEPs. Therefore, developing numerical solutions for these problems is an important requirement. Newton's Method is considered as one of the numerical methods used to solve the multi-parameter eigenvalue problems. Although the Newton method is a successful method for the solution of MuPEPs, we sometimes encounter some troubles such as computation cost or convergence problems. Especially, we deal with the difficulties in solving MuPEPs involving large-scale dense matrices using Newton's method. In this dissertation, we propose a fused parameter optimization (fusedparopt) algorithm for two-parameter and three-parameter eigenvalue problems. Our fusedparopt algorithm is built by Newton's method as a solver, tensor Rayleigh quotient (RQ) and the steepest descent (SD) techniques. We combine them in three ways; optimizing initial eigenpairs, optimizing eigenpairs during Newton's iteration and making these optimizations together. It is called fusedparopt_SD method. In addition, there are no such theorems about the convergence of the steepest descent technique for two-parameter and three-parameter eigenvalue problems. Therefore, we propose new theorems for the convergence of the steepest descent technique on two-parameter and three-parameter eigenvalue problems. Limited-memory BFGS (L-BFGS) can be considered as an alternative method to the SD method. We also propose L-BFGS method in our fused algorithm, as an alternative to the fusedparopt_SD method. It is called fusedparopt_LBFGS method. Two-parameter eigenvalue problems are handled to see the effect our proposed methods in applications. We test the performance of our algorithms and compare them with state-of-art algorithms such as twopareigs from MultiParEig toolbox in Matlab and tensor Rayleigh quotient-Newton (RQ_N) using the coefficient matrices coming from Lamé system and simulations via randomly generated general matrices and convergence diagrams. Our algorithm can converge earlier than the state-of-art twopareigs methods. Although high-cost solutions or convergence problems are obtained with the RQ_N method, we have more effective solutions with our algorithm. We see that solutions with RQ_N method have more fluctuations and they grow up as the size of the problem increases. However, fusedparopt method improves the results with less volatility. The results obtained by the fusedparopt_LBFGS and fusedparopt_SD methods are close to each other and comparable, depending on the matrix type. Thus, we see that fusedparopt_SD and fusedparopt_LBFGS methods achieve robustness, reasonable cost and diminish divergence problem for two-parameter eigenvalue problems based on our data set. Furthermore, we improve our proposed method for some special cases. Two approaches including deterministic grid multi-start approach and random multi-start approach are proposed in order to find all different eigenvalue tuples via our fused algorithm. We apply a similarity test to validate the distinction of computed multiple eigenvectors corresponding to the eigenvalues having multiplicity greater than one. Then, we perform tests on three-parameter eigenvalue problems having different types such as non-singular or singular problems involving small-scale or large-scale matrices. We compare our proposed approaches via fusedparopt algorithm with RQ_N and with state-of-art algorithms from MultiParEig toolbox in Matlab. Also, we discuss the challenges for coefficient matrices coming from the ellipsoidal wave equation. We also propose to parallelize our fusedparopt algorithm using the advantage of the multi-start method to compute all different eigenvalue tuples more efficiently. We make an implementation for the Baer wave equation. We obtain a three-parameter eigenvalue problem after discretizion of this equation. Then we solve this problem using our fusedparopt algorithm by dynamic thread-based parallel computing on Matlab. In conclusion, advances in science and technology require the ability to deal with large-scale problems and solve them today. However, increasing the size of the problems causes more costs in the solution, such as time and memory. This case requires not only solving problems, but also focusing to reach a solution quickly and efficiently. Therefore, the proposed fused algorithms in this dissertation have the advantages of being fast, stable, robust and low memory usage in order to find all or target number of different eigenvalue tuples and the corresponding eigenvectors in multi-parameter eigenvalue problems, especially in large-scale sizes.
Benzer Tezler
- 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
1994
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. CÜNEYT GÜZELİŞ
- Elektrokardiyogram verilerinin iyileştirilmiş yapay arı kolonisi (MABC) algoritması ile analizi
Analysis of electrocardiogram data by using modified artificial bee colony (MABC) algorithm
SELİM DİLMAÇ
Doktora
Türkçe
2017
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. TAMER ÖLMEZ
- Havayolu yolculuk deneyimini iyileştirmek için makine öğrenmesi yöntemleriyle uçuş gecikmesi tahmini
Machine learning techniques for enhancing airline passenger experience through flight delay prediction
ESMA ERGÜN
Yüksek Lisans
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilişim Uygulamaları Ana Bilim Dalı
DR. ÖĞR. ÜYESİ SÜHA TUNA
- Uyarlamalı süzgeçler
Adaptive filters
RIDVAN AYSEL
Yüksek Lisans
Türkçe
1994
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. AHMET H. KAYRAN
- Bozulabilir mallar için optimal üretim planlaması
Optimal production planning for decaying items
MELDA GÜRSOY