Raziskovalni projekt (so)financira Javna agencija za raziskovalno dejavnost RS.
Članica UL: Fakulteta za matematiko in fiziko
Šifra projekta: N1-0154
Naziv projekta: Verjetnostne metode za skupne in singularne probleme lastnih vrednosti
Obdobje: 1. 1. 2021 - 31. 12. 2023
Letni obseg: 0,73 FTE, cenovna kategorija: C
Vodja: Bor Plestenjak
Veda: Naravoslovje
Sodelujoče RO, sestava projektne skupine, bibliografske reference
Vsebinski opis projekta:
Računanje lastnih vrednosti in lastnih vektorjev dane matrike je en izmed najbolj osnovnih problemov numerične linearne algebre in zanj obstajajo zelo izpopolnjeni algoritmi in zanesljive implementacije v t.i. obliki črne škatle. Precej manj pozornosti je bilo posvečene vrsti nestandardnih problemov lastnih vrednosti, za katere je obstoječ izbor algoritmov in implementacij zelo omejen. Osnovna nit tega projekta je, da slučajenje pretvori take probleme v standardne probleme lastnih vrednosti, kar omogoči uporabo obstoječih učinkovitih metod, brez škode za numerično robustnost. Glavni rezultat projekta bodo algoritmi, ki bodo z veliko verjetnostjo zagotavljali visoko natančnost za zmerno ceno, in njihove implementacije skupaj z demonstracijo uporabnosti v različnih aplikacijah.
Z aplikacijami v obdelavi signalov, analizi podatkov in na številnih drugih področjih, predstavljajo skupni problemi lastnih vrednosti pomemben razred problemov, ki jih obravnavamo v tem projektu. Zahtevajo simultano diagonalizacijo ali triangularizacijo družine matrik. Za razliko od pristopov, ki temeljijo na optimizaciji in se pogosto uporabljajo za to nalogo, v projektu načrtujemo analizo, izboljšavo in posplošitev slučajnih metod, ki temeljijo na reševanju standardnega problema lastnih vrednosti za eno ali več slučajnih linearnih kombinacij teh matrik. To bo privedlo do algoritmov, ki bodo enostavni za implementirati, robustni na motnje, in sposobni reševanja problemov z velikimi matrikami, kar bo znatno razširilo vsebine in zahtevnosti aplikacij, ki se jih lahko tako lotimo.
Kadar je posplošeni ali polinomski problem lastnih vrednosti singularen, kar je naslednji razred problemov, ki jih obravnavamo v projektu, postaneta definicija in numerično računanje lastnih vrednosti zelo težavna. Znano je namreč, da lahko v tem primeru poljubno majhna motnja začetnih podatkov povzroči poljubno velike spremembe lastnih vrednosti. Kljub tej anomaliji se singularni problemi pojavljajo v pomembnih aplikacijah, še posebno v inženirstvu, kjer nastopajo v električnih vezjih ali mehaničnih sistemih, ki jih modelirajo diferencialno-algebrske enačbe. V tem projektu bomo uporabili naključne motnje in projekcije za pretvorbo singularnega problema v regularni problem lastnih vrednosti. S pomočjo verjetnostne analize bomo razvili algoritme, ki bodo lahko z zelo visoko verjetnostjo numerično stabilno izračunali lastne vrednosti originalnega singularnega problema.
Večparametrični problemi lastnih vrednosti vsebujejo lastnosti obeh zgoraj obravnavanih razredov. Po eni strani jih lahko rešujemo kot skupne probleme lastnih vrednosti, po drugi strani pa ta pretvorba pogosto vodi do singularnih problemov lastnih vrednosti, še posebno pri uporabi za iskanje ničel sistemov dveh polinomov dveh spremenljivk. Za ta primer bomo kombinirali in priredili slučajne metode, pri čemer bomo upoštevali strukturo, ki je posledica tega, da matrike izvirajo iz večparametričnih problemov lastnih vrednosti.
Rezultati in dosežki projekta:
Program dela je razdeljen na tri glavne sklope:
I. Skupni problemi lastnih vrednosti
II. Singularni problemi lastnih vrednosti
III. Večparametrični problemi lastnih vrednosti
V grobem je bilo predvideno, da se bo v prvih dveh letih švicarska ekipa ukvarjala s sklopom I, slovenska ekipa s sklopom II, v zadnjem letu pa se obe ekipi lotita problemov iz sklopa III.
Sklop I je razdeljen na
I. (1) Analiza verjetnosti in verjetnostni algoritmi
I. (1a) Algoritmi in analiza za skupni spektralni razcep
I. (1b) Algoritmi in analiza za skupni (posplošeni) Schurov razcep
I. (2) Razvoj in analiza iterativnih metod podprostorov Krilova
I. (3) Programska oprema in primerjava
S tem sklopom se je ukvarjala švicarska ekipa. Za več komutirajočih simetričnih matrik je bil analiziran verjetnostni algoritem, kjer diagonaliziramo naključno linearno kombinacijo in nato to uporabimo za diagonalizacijo posameznih matrik. Analiza je pokazala veliko prednosti novega pristopa, rezultati so zbrani in poslani v objavo v [arXiv5]. Pristop je enostavnejši in vrača boljše rezultate od raznih optimizacijskih algoritmov. Za matrike, ki komutirajo, a niso simetrične, je osnovna ideja enaka, a je težje z verjetnostno analizo dokazati, da algoritem deluje.
Sklop II je razdeljen na naslednje točke:
II. (1) Analiza verjetnosti in verjetnostni algoritmi
II. (1a) Vpliv linearizacij na verjetnostna pogojenostna števila
II. (1b) Razvoj in analiza kriterijev za razlikovanje lastnih vrednosti v Metodi 1
II. (1c) Analiza verjetnostnih metod za izračun normalnega ranga
II. (1d) Analiza in izboljšave Metode 2
II. (1e) Analiza in izboljšave Metode 3
II. (2) Programska oprema in primerjava
Tu so Metode 1,2,3 metode za računanje lastnih vrednosti singularnega matričnega šopa. Metoda 1 temelji na članku (Lotz, Noferini 2019) in uporablja naključne perturbacije polnega ranga, Metoda 2 iz (Hochstenbach, Mehl, Plestenjak, 2019) uporablja motnje, ki popolnijo rang, Metoda 3 (najavljena v programu dela projekta) pa projekcijo na problem velikosti normalnega ranga.
V okviru sklopa II je švicarska ekipa analizirala [arXiv4], kako dober kriterij za detekcijo končnih lastnih vrednosti singularnega posplošenega problema lastnih vrednosti je občutljivost lastne vrednosti naključno zmotenega problema v Metodi 1 (1b), hkrati pa je analizirala tudi vpliv izbire linearizacije, s katerim singularni kvadratni problem lastnih vrednosti prevedemo na posplošeni problem lastnih vrednosti (1c). Analiza je potrdila, da v obeh primerih lahko na predlagani način z veliko zanesljivostjo izračunamo lastne vrednosti. Slovenska ekipa je v okviru podsklopa (1e) s tujimi sodelavci razvila Metodo 3 in poslala članek v objavo [arXiv1], novo numerično metodo pa je predstavila na najprestižnejši mednarodni konferenci s področja numerične linearne algebre [Cobiss 131128323]. V članku [arXiv1] so predstavljene tudi izboljšave Metod 2 in 3 za računanje večkratnih lastnih vrednosti (1d, 1e). Metodi 2 in 3 sta implementirani v novi verziji prosto dostopnega Matlab paketa MultiParEig [Cobiss 18581849], kar ustreza sklopu (2), kar pa se tiče knjižnice primerov za primerjalno analizo, nadaljujemo z zbiranjem zanimivih problemov.
D. Kressner in B. Plestenjak sta analiziral vpliv izbire naključnih matrik v Metodi 2 in Metodi 3 (1d, 1e) na občutljivosti lastnih vrednosti zmotenih šopov. Podobno kot v [arXiv4] se da tudi v tem primeru pokazati, da metodi z veliko verjetnostjo vračata pravilne lastne vrednosti, članek je v pripravi. To še dodatno dokazuje veliko uporabnost nove Metode 3 za reševanje singularnih problemov lastnih vrednosti.
Pri točki (1c) zaenkrat ni prišlo do verjetnostne analize računanja normalnega ranga s pomočjo računanja ranga naključno izbrane kombinacije matrik, je pa v članku [arXiv1] razvita nova teorija, na podlagi katere se da iz numeričnih rezultatov z veliko verjetnostjo ugotoviti, da normalni rang ni bil pravilno določen in tako računanje ponoviti. To v določeni meri zmanjša pomen točke 1c, saj je težava praktično rešena že na drug način.
Čeprav je bilo to v planu šele za zadnje leto projekta, je bilo izvedenih kar nekaj zadev iz sklopa III:
III.(1) Nesingularni problemi
III. (1a) Aplikacije rezultatov iz I.(1b) in I.2
III.(2) Singularni problemi
III. (2a) Uporaba rezultatov iz II.(1) in I.(1b)
III. (2d) Aplikacije v iskanju ničel in reševanju problema dvojnih lastnih vrednosti
III.(3) Programska oprema in primerjava
Čeprav teoretičnih rezultatov na področju I.(1b) še ni, so bile ideje vseeno praktično uporabljene v III.(1a) in III.(2a) v paketu MultiParEig [COBISS.SI-ID 18581849], saj je bilo s številnimi numeričnimi eksperimenti potrjeno, da se na način, ko se izračuna Schurova forma naključno izbrane kombinacije operatorskih determinant, pride do boljše simultane triangularizacije povezanega sistema matričnih šopov kot s prejšnjo uporabljeno metodo.
V okviru III.(2a) sta T. Košir in B. Plestenjak v [COBISS.SI-ID 111311363] razširila teoretične rezultate o povezavi med lastnimi vrednostmi singularnega dvoparametričnega problema lastnih vrednosti in sistema pridruženih singularnih matričnih šopov tudi na primere večkratnih lastnih vrednosti. Ta teorija zagotavlja, da lahko z metodami iz sklopa II poiščemo lastne vrednosti singularnega dvoparametričnega problema lastnih vrednosti. Ustrezne metode so implementirane v paketu Multipareig [COBISS.SI-ID 133248515].
V okviru III.(2d) smo se ukvarjali s problemom računanja ZGV točk [arXiv2] za anizotropne elastične valovode. Problem se formulira kot singularen kvadratičen dvoparametričen problem lastnih vrednosti, ki je zelo podoben problemu dvojnih lastnih vrednosti. Na tovrstnih problemih stopnični algoritem za reševanje singularnih večparametričnih problemov lastnih vrednosti odpove, medtem ko je z novo Metodo 3 iz II.(1e) možno te probleme učinkovito rešiti. Dobljena metoda je prva, ki zna brez začetnih približkov izračunati vse ZGV točke, če problem ni prevelik za večje probleme pa smo ustrezno posplošili metodo, ki zmoti originalni večparametrični problem, in vrača približke, ki jih nato izboljšamo z Newton-Gaussovo metodo. Poleg [arXiv2] je v pripravi še drug članek z matematičnim ozadjem splošnega problema računanja ZGV točk in povezanega problema 2D lastnih vrednosti,
V okviru III.(2d) smo se ukvarjali tudi s problemom pravokotnih večparametričnih problemov lastnih vrednosti, kjer imamo eno samo enačbo z več parametri in pravokotnimi matrikami. Problem se pojavi pri računanju optimalnih parametrov ARMA in LTI modelov za analizo časovnih vrst. V članku poslanem v objavo [arXiv3] smo predstavili splošno teorijo za takšne probleme in kot prvi dokazali število rešitev za polinomski problem pravokotnih večparametričnih problemov. Razvili smo numerične metode za reševanje tovrstnih problemov z uporabo naključnih projekcij za prevedbo na večparametrični problem lastnih vrednosti oziroma s prevedbo na sistem (singularnih) matričnih šopov. Na ta način lahko za modele ARMA(1,1), ARMA(2,1) in LTI(2) parametre izračunamo dosti hitreje kot z edino drugo obstoječo metodo, ki uporablja bločne Macaulayejeve matrike. Nove metode so v okviru III.(3) že implementirane v paketu Multipareig [COBISS.SI-ID 133248515].
