Algorithms and convergence of the Jacobi-type methods

doctoral thesis

• Title (croatian): Algoritmi i konvergencija metoda Jacobijeva tipa
• Author: Ana Perković
• Mentor: Erna Begović Kovač (mentor)
• Committee member: Nela Bosner (predsjednik povjerenstva)
• Committee member: Zoran Tomljanović (član povjerenstva)
• Committee member: Zvonimir Bujanović (član povjerenstva)
• Committee member: Zlatko Drmač (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2025-02-14, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics
• Universal decimal classification (UDC): 51 - Mathematics

Abstract

The Jacobi eigenvalue algorithm is a well-known iterative method used for solving the eigenvalue problem of symmetric matrices. The process is based on matrix diagonalization. In this thesis we study several modifications of the Jacobi method. We work on both matrix and tensor numerical problems. First, we review and generalize the Eberlein method, which is a Jacobi-type method for diagonalization of an arbitrary matrix. We prove the global convergence of the Eberlein method under a broad class... More of generalized serial pivot strategies with permutations. Moreover, we discuss the cases of unique and multiple eigenvalues. Next, we consider block-partitioned matrices and introduce a block version of the Eberlein method. We give a convergence proof for the block Eberlein algorithm under the already mentioned class of generalized serial pivot strategies. Lastly, we study the methods for approximate tensor diagonalization. We propose an iterative Jacobi-type trace maximization algorithm for solving this problem on general tensors, as well as the structure-preserving variant for the symmetric tensors. We prove the global convergence for both of our algorithms. All theoretical work is accompanied by numerous numerical examples. Less

Abstract (croatian)

Jacobijev algoritam je poznata iterativna metoda za rješavanje problema svojstvenih vrijednosti za simetrične matrice. Postupak se temelji na dijagonalizaciji matrice. U ovoj se disertaciji bavimo modifikacijama Jacobijeve metode koje koristimo za rješavanje numeričkih problema za matrice i tenzore. U prvom dijelu rada proučavat ćemo Eberleininu metodu Jacobijevog tipa za dijagonalizaciju opće matrice. Poopćit ćemo Eberleininu metodu i dati dokaz globalne konvergencije za široku klasu tzv.... More generaliziranih serijalnih pivotnih strategija s permutacijama. Analizirat ćemo slučaj jednostrukih i višestrukih svojstvenih vrijednosti. Nadalje, promatrat ćemo matrice s blok-particijom te uvesti blok verziju Eberleinine metode. Dat ćemo dokaz konvergencije blok Eberleininog algoritma za već spomenutu klasu generaliziranih serijalnih pivotnih strategija. Naposljetku, promatrat ćemo problem približne dijagonalizacije tenzora. Predstavit ćemo iterativni algoritam Jacobijevog tipa temeljen na maksimizaciji traga tenzora. Konstruirat ćemo algoritam za opće tenzore te njegovu varijantu za simetrične tenzore u kojoj je očuvana polazna simetrična struktura. Za oba algoritma dokazat ćemo globalnu konvergenciju. Svi teorijski rezultati će biti popraćeni brojnim numeričkim primjerima. Disertacija je podijeljena u četiri poglavlja. U prvom poglavlju dan je osvrt na rezultate iz literature. Opisan je realni i kompleksni Jacobijev algoritam za rješavanje problema svojstvenih vrijednosti i izvedene su formule za računanje kutova transformacije. Opisano je nekoliko klasa pivotnih strategija. Poglavlje se nastavlja teorijom o Jacobijevim anihilatorima i operatorima koji se koriste u brojnim rezultatima o konvergenciji za standardnu Jacobijevu metodu i za druge metode Jacobijeva tipa. Koristit ćemo tu teoriju za dokaz konvergencije Eberleinine metode po elementima, ali i njene blok varijante. Prvo poglavlje završava osvrtom na teoriju o konvergenciji Jacobijeva algoritma. Drugo poglavlje temelji se na članku [10] od Begović Kovač i Perković objavljenom 2024. godine. Prvo je dan pregled postojećih rezultata o konvergenciji Eberleinine metode, za realni i kompleksni slučaj. Glavni dio poglavlja je proširenje globalne konvergencije metode na široku klasu generaliziranih serijalnih pivotnih strategija. Pokaže se da, za proizvoljnu početnu matricu A, Eberleinina metoda konvergira uz bilo koju strategiju iz navedene klase. Niz matrica $A^{(k)}, k\geq 0$, koji se dobije nakon svake iteracije, konvergira prema normalnoj matrici. Niz hermitskih dijelova dobivenih matrica, $(A^{(k)} + (A^{(k)})^*) /2, k\geq 0$, konvergira prema dijagonalnoj matrici takvoj da su na dijagonali realni dijelovi svojstvenih vrijednosti od $A$. Ako sve svojstvene vrijednosti od $A$ imaju različite realne dijelove, niz $A^{(k)}$ konvergira prema dijagonalnoj matrici sa svojstvenim vrijednostima od $A$ na dijagonali. Inače, svojstvene vrijednosti s jednakim realnim dijelovima mogu dovesti do ne-nul van-dijagonalnih elemenata u dobivenoj matrici. Kroz numeričke primjere testirana je metoda na realnim i kompleksnim matricama, za početne matrice koje su unitarno dijagonalizabilne i za one koje to nisu. Promatrana je promjena u matričnoj van-dijagonalnoj normi, tj., udaljenosti od dijagonalne matrice. Nadalje, pokazana je blok struktura koja se pojavljuje ako početna matrica ima višestruke svojstvene vrijednosti. Naposljetku, pokazano je kako numerički riješiti problem kod ponavljajućih svojstvenih vrijednosti. Treće poglavlje sadrži prijedlog novog blok Eberleininog algoritma. Dan je kratki uvod u blok matrice i blok algoritme. Opisana je blok verzija Eberleinine metode u kojoj su matrice podijeljene u blokove. Zatim, predložen je način za računanje transformacija $\mathbf{R}_k$ i $\mathbf{S}_k, k\geq 0$, te dan dokaz konvergencije algoritma uz generalizirane serijalne pivotne strategije. Rezultati konvergencije su u skladu s onima za Eberleininu metodu po elementima. Numeričkim testovima pokazano je kako blok algoritam radi za različite veličine blokova i za ponavljajuće realne dijelove svojstvenih vrijednosti. Četvrto i posljednje poglavlje orijentirano je na približnu dijagonalizaciju tenzora. Temelji se na članku [11] od Begović Kovač i Perković objavljenom 2024. godine. Ovdje je detaljno objašnjena terminologija i pojmovi vezani uz tenzore koji se koriste u tenzorskom računu. Prvo je dan osvrt na postojeće algoritme za dijagonalizaciju tenzora. Zatim je iznesen prijedlog algoritma koji se temelji na maksimizaciji traga tenzora, kao u [65]. Algoritam koristi metodu alternirajućih najmanjih kvadrata (ALS). Naime, jedna iteracija algoritma na tenzoru reda $d$ sastojat će se od $d$ mikroiteracija. Pokazana je globalna konvergencija našeg algoritma za opće tenzore. Preciznije, pokazano je da je svako gomilište dobiveno našim algoritmom stacionarna točka funkcije koju maksimiziramo. Ovaj rezultat istog je tipa kao rezultati konvergencije algoritama za dijagonalizaciju tenzora koji se baziraju na maksimizaciji Frobeniusove norme dijagonale tenzora. Konvergencija vrijedi za sve cikličke strategije uz dodatni uvjet na pivotni par $(p, q)$, zvan Łojasiewitzeva nejednakost gradijenta. Nadalje, naš algoritam maksimizacije traga prilagođen je kako bi se očuvala struktura simetričnih tenzora. U tom slučaju, svih d rotacija koje djeluju u jednoj iteraciji moraju biti iste. Prema tome, ovo više nije ALS algoritam jer se trag maksimizira po svim modovima istovremeno. Ipak, dokaz konvergencije će ići uz bok dokazu za algoritam koji ne čuva strukturu. Numerički primjeri uključuju testove oba algoritma na tenzorima različitih redova, dijagonalizabilnih tenzora i onih koji to nisu. Promatrano je povećanje traga tenzora i smanjenje van-dijagonalne norme tenzora, te su dane usporedbe za različite cikličke pivotne strategije. Less

• Keywords: Jacobi-type method; matrix diagonalization; pivot strategies; global convergence; tensor diagonalization
• Keywords (croatian): Metoda Jacobijeva tipa; dijagonalizacija matrice; pivotne strategije; globalna konvergencija; dijagonalizacija tenzora
• Language: english
• URN:NBN: urn:nbn:hr:217:716226
• Project: Number: UIP-2019-04-5200; Title: Dekompozicije i aproksimacije matrica i tenzora; Title: Decompositions and Approximations of Matrices and Tensors; Acronym: DAMAT; Leader: Erna Begović Kovač; Jurisdiction: Croatia; Funder: Hrvatska zaklada za znanost; Funding stream: Installation Research Projects
• Study programme: Title: Doctoral study; Study programme type: university; Study level: postgraduate; Academic / professional title: doktor/doktorica u području prirodnih znanosti (doktor/doktorica u području prirodnih znanosti)
• Type of resource: Text
• Extent: vii, 158 str.
• File origin: Born digital
• Access conditions: Open access
• Created on: 2025-03-04 10:14:06