Vyhledávání
PolyNumeriX: algoritmy a software pro polynomiální rovnice
Kdo jsme?
Michael Šebek
Michal je vedoucím tohoto týmu, propagátorem počítání s polynomy a autorem mnoha algoritmů, metod a jejich aplikací v systémech, signálech a řízení. Řídí vývoj softwarového balíku Polynomial Toolbox for Matlab.
Didier Henrion
Didier vytvořil mnoho efektivních algoritmů založených na Sylvestrových maticích, interpolaci a v poslední době zejména na lineárních maticových nerovnostech.Vyvinul mnoho speciálních programů zejména v kódu Matlab pro Polynomial Toolbox for Matlab.
Martin Hromčík
Martin je autorem mnoha rychlých a účinných algoritmů založených na rychlé Fourierově transformaci. Vyvinul originální metody používající FFT pro polynomiální determinant, spektrální faktorizaci a nesymetrickou plus-minus faktorizaci. Spoluopracuje na vývoji softwarového balíku Polynomial Toolbox for Matlab.
Zdeněk Hurák
Zdeněk se v týmu specializuje na metody návrhu optimálního a robustního řízení, založené zejména na minimalizaci l1 normy.
V týmu průběžně pracuje i mnoho doktorandů, v současné době Petr Kujan a Petr Augusta.
Jakým výzkumem se zabýváme
Náš tým vytváří nové originální postupy pro počítání s polynomy (mnohočleny) a maticemi polynomů a také pro řešení rovnic s polynomy a maticemi polynomů s cílem aplikovat je v systémech, signálech a řízení. Zatímco teorie využití polynomů a jejich matic např. pro návrh systémů a jejich řízení je dnes rozšířena po celém světě, dostatečně rychlé a spolehlivé algoritmy pro takové výpočty donedávna chyběly a proto do praxe pronikly polynomiální metody teprve v minulé dekádě.
Protože jsme v této oblasti dosáhli velkého pokroku, je v ní náš tým všeobecně považován za vedoucí skupinu na světě. Vyvinuli jsme mnoho originálních metod: nejprve velmi spolehlivé metody založené na Sylvestrových maticích - dnes jim říkáme "metody druhé generace" a nedávno stejně spolehlivá avšak navíc mnohem rychlejší metody používající interpolaci a rychlou Fourierovu transformaci FFT - to jsou "metody třetí generace".
Nové metody publikujeme ve špičkových mezinárodních časopisech. Takových článků členům našeho týmu již vyšlo několik desítek. Největším publikačních úspěchem jsou tři články otištěné v nejlepším časopisu oboru, americkém IEEE Transactions on Automatic Control v prestižní kategorii "velký článek". Naše publikace jsou po celém světě hojně citovány. Řídíme evropskou síť excelence výzkumných pracovišť a firem pro průmyslové aplikace polynomiálních metod EUROPOLY a mnoho mezinárodních i národních projektů v této oblasti.
Vyvinuté algoritmy nejen matematicky dokazujeme a vědecky publikujeme, ale každou samozřejmě intenzivně testujeme experimentálně a ve formě prototypových programů předáváme do průmyslu. Například česká firma PolyX s.r.o. je implementuje ve svém komerčním produktu Polynomial Toolbox for Matlab. Naše algoritmy tak úspěšně používají koncoví průmysloví uživatelé Polynomiálního Toolbox po celém světe, a to jak velké podniky, např. Lockheed Martin, SANDIA National Lab a National Instruments, (vše USA); Mitshubishi Electric, J; Petrobras, BRA, Saudi Armaco, SA, QuinetiQ, GB, tak i malé hi tech firmy Compureg, CZ, ProCS, SK a Cybernet Systems Ltd., J.
K čemu to je
V oboru systémů, signálu a řízení stále častěji počítáme nikoli s čísly, ale se složitějšími objekty, např. s polynomy. Tak třeba když k soustavě (tj. systému, který máme řídit, např. průmyslovému procesu, raketě, lodi, automobilovému motoru, ruce robota, lidskému svalu, ...) s přenosem b(s)/a(s) připojíme do zpětné vazby regulátor s přenosem y(s)/x(s), jsou vlastnosti a chování výsledného systému popsány výrazem
Protože nejčastěji všechny a(s),b(s),x(s),y(s) jsou polynomy v proměnné s, tak je polynomem i výsledné c(s) na pravé straně. Přitom matematické vlastnosti polynomu dobře vyjadřují technické vlastnosti skutečného výsledného systému (např. dynamika, rychlost, stabilita, vibrace, tlumení, citlivost na změny nebo poruchy,...). Inženýr z našeho oboru často řeší opačný problém: zákazník (majitel reálného systému popsaného tím b(s)/a(s)), s ním není spokojen a přeje si změnit jeho vlastnosti a chování. Nejlepším řešením je často řídící systém (regulátor), který pracuje ve zpětné vazbě (tj. měří chování - výstup - dané soustavy a podle toho, co naměří, vytvoří vhodný zásah - vstup do soustavy - tedy jí řídí. Pokud se nám podaří vtělit požadavky zákazníka do vlastností polynomu, pak přenos hledaného regulátoru y(s)/x(s) snadno zjistíme z výše uvedeného výrazu. Pro dané polynomy a(s),b(s),c(s) ho vyřešíme jako polynomiální rovnici s neznámými polynomy x(s),y(s). Jakmile najdeme vhodné řešení, je už hračkou vypočtený regulátor realizovat a k soustavě připojit. Úspěch přirozeně také závisí na tom, jak dobře (přesně, spolehlivě a rychle) dokážeme tu rovnici vyřešit.
Systémy, které dnes musíme řídit, jsou často mnohem složitější. Třeba proto, že mají mnoho výstupních a vstupních signálů. U nich se setkáme s trochu složitějšími rovnicemi
kde všechny objekty jsou matice polynomů, například něco jako
.
Řešit rovnice s maticemi polynomů je samozřejmě těžší. Konečně mohou být náročnější i požadavky zákazníka na řídicí systém. Ten často chce, aby výsledný systém byl optimální (choval se co možná nejlépe) a/nebo robustní (choval se rozumě, i když je popis původní systému velmi nepřesný, když se původní systém mění apod.) Pak musíme řešit ještě složitější rovnice, třeba kvadratické, jako například
nebo maticovou
V reálných situacích potkáváme stále složitější systémy, a proto je řešení výše uvedených rovnic i další výpočty či operace a manipulace s polynomy i jejich maticemi i pro počítače stále náročnější. Proto je třeba hledat a vyvíjet stále efektivnější algoritmy a metody.
Na čem konkrétně pracujeme
Předkládáme několik vybraných témat a aplikací, na kterých aktuálně pracujeme.Využití algoritmů a solverů pro strukturované matice pro řešení polynomiálních maticových rovnic
S využítím Sylvesterových matic lze lineární polynomiální maticové rovnice elegantně přepsat do tvaru lineárních rovnic s konstantami, které lze pak řešit s pomocí existujících silných algoritmů a programových balíků pro problémy lineární algebry (LAPACK, MATLAB apod.). Takto vzniklé rovnice jsou navíc silně strukturované, čehož bychom chtěli využít.
První možnou cestou k dosažení tohoto cíle je použití solverů pro pásové matice. Výhodou je existence příslušných solverů např. v balíku LAPACK, jehož funkce lze poměrně snadno volat z MATLABu a Polynomiálního toolboxu, na kterém pracujeme. Nevýhodou je pak skutečnost, že strukturu problému využijeme pouze částečně, nevyužíváme ji zcela. Naznačený postup jsme naprogramovali ve formátu prototypového programu pro Polynomial Toolbox a dosahujeme úspory výpočetního času až 80% pro polynomy vysokých stupňů. Kontakt: Martin Hromčík
Náročnější cestou je pak vývoj skutečně dedikovaných algoritmů, od začátku do konce, s uvážením veškerých souvislostí původního polynoiálního zadání a vzniklé konstantní soustavy. Vzniklé metody využívají modifikací obratů známých z moderní lineární algebry jako jsou Givensovy rotace nebo Householderovy transformace. V současnosti pracujeme na efektivní implementaci těchto nových metod a těšíme se na jejich praktické srovnání s výše zmíněným postupem. Kontakt: Didier Henrion
Polynomiální metody pro optimální řízení
Mnoho problémů řízení lze formulovat jako optimalizační problém. Na volbě zvoleného kriteria pak závisejí vlastnosti navrženého zpětnovazebního obvodu jako je kvalita potlačení vnějších poruchových signálů, sledování požadované reference, robustnost vůči změněn parametrů soustavy apod.Významným výsledkem skupiny z poslední doby je metoda pro nalezení regulátoru minimalizující tzv. l1 normu uzavřené smyčky. Algoritmus využívá polynomiální přístup a numericky spolehlivé rutiny pro polynomiální lineární a kvadratické rovnice. Kontakt: Zdeněk Hurák
Zlepšení kvality hi-fi soustav
Vložením vhodně navrženého předfiltru do audio řetězce lze dosáhnout kompenzace různých nežádoucích vlastností připojených reproduktorů. Jestliže reprosoustavu chápeme jako lineární systém aproximovaný přenosem identifikovaným z dat (měření probíhá ve zvukově izolované komoře, viz obrázek), pak tento předfiltr realizuje, aspoň teoreticky, inverzi tohoto přenosu.V praxi toto není možné ani žádoucí, například proto, že taková přímá inverze vede na nestabilní systém. Je ale možné použít sofistikovanější robustní metody pro přibližnou inverzi systému, při jejímž výpočtu je potřeba řešit lineární polynomiální rovnici a rozklad polynomu na stabilní a nestabilní část.
Na tomto problému spolupracujeme s Universzitou v Uppsale, S. Identifikace systému vede na modely neobvykle vysokých řádů, typicky 100-500, které nelze rozumně řešit běžnými metodami. Vývoj specializovaných algoritmů a solverů pro tyto problémy je naše role v této spolupráci. Kontakt: Martin Hromčík
Vícehladinový konvertor
Třífázový vícehladinový konvertor je elektronické zařízení, které převádí stejnosměrné napětí z různých zdrojů na střídavé napětí. Snahou je vypočítat optimální spínací sekvenci v můstcích stejnosměrných zdrojů, tak aby výstupní schodovitý signál byl po filtraci co nejméně deformován nešádoucími vyššími harmonickými (minimalní THD) a rovnal se pošadovanému sinusovému výstupu. Tato úloha vede na řešení speciální soustavy trigonometrických nebo po převodu na Chebyshevovy polynomy na soustavu polynomiálních rovnic o více neznámých. Tato soustava polynomiálních rovnic je řešena pomocí eliminační metody (resultant). Při řešení se provádí výpočty se speciálními polynomiálními maticemi Sylvesterova typu obrovských rozměrů, které pro vetší počet stejnosměrných zdrojů jsou doposud neřešitelné. Proto jsou dále studovány další mošnosti řešení příslušných soustav pomocí
- Groebnerových bází
- eliminace promenných pomocí dálších resultant - Dixon, Bezout a Macaulay formulace a jejich modifikace
- numerických iterativních algoritmů - řešení soustav nebo hledání globálních extrémů
Další zajímavou mošností je vyušití analytického řešení pro jednofázové zapojení, které vychází ze zobecněné Newtonovy identity. Kontakt: Petr Kujan
Polynomiální metody pro 2D a 3D systémy
Polynomiální metody a řídicí systémy obecně uvažují typicky se systémy se soustředěnými parametry popsanými například přenosem. Popsat pomocí polynomů a polynomiálních matic s více proměnnými takové soustavy, jejichž vlastnosti se vyvíjí nejen v čase, ale závisejí i na jedné nebo více prostorových souřadnicích, a navrhnout pro takové systémy smysluplné řízení pomocí polynmomiálních operací je cílem tohoto výzkumu.
Motivací výzkumu je adaptivní optika - moderní disciplína, jejímž cílem je měnit optické vlastnosti systému na základě detekovaných změn v samotném systému nebo ve vnějším prostredí. Uvažováno je deformovatelné zrcadlo nebo plech se sadou akčních členů a senzorů umístěných pod povrchem. Odvozena je přenosová funkce ze vstupní síly na výchylku plechu, tj. podíl dvou polynomů o třech promenných -- dvě proměnné odpovídají prostoru, jedna času. Rozšírením algebraické teorie řízení o metody pro vícerozměrné oboustranné polynomy bude možné navrhnout optimální regulátor řízení výchylky deformovatelného zrcadla či plechu. Vedle astronomie bude možno tyto metody využít pro řízení laserového paprsku, v očním lékařství aj. Kontakt: Petr Augusta
Kdo financuje náš výzkum
Náš výzkum je průběžně financován z různých průmyslových a státních projektů. V minulosti např. z evropských projektů Copernicus Project CP93:2424: Algorithms for CAE Based on Modern Polynomial Design Methods in Control a Copernicus Project CP97:7010 EUROPOLY – The Network of Excellence for Industrial Applications of Polynomial Methods (který vedoucí našeho týmu dokonce koordinoval) a projektu NATO PST.CLG.978481 Computer Algorithms for Polynomial Methods in Signals and Systems. Dále z dvoustranných mezinárodních projektů česko-francouzských (Barrande 97026), česko-japonských (NJ 11/98), česko-italských (NT1-25), česko-rakouských (AKTION) a česko-řeckých (12-00). V současné době tento výzkum podporuje projekt Centrum aplikované kybernetiky (MŠMT 1M0567) a grant GAČR (102/05/0011).
S kým spolupracujeme
Průběžně přímo spolupracujeme a výsledky společně publikujeme s výzkumnými týmy z LAAS CNRS Toulouse, F; University of Twente, NL; Nara Institute of Technology, J; Aristotle University of Thessaloniki, GR; a University of Upsalla, S. Softwarové implementace našich algoritmů testujeme a konzultujeme s firmami PolyX, CZ; The MathWorks, USA a Wolfram Research, USA.
Vybrané publikace
Členové našeho týmu v této oblasti publikovaly několik desítek článků ve špičkových mezinárodních vědeckých časopisech a prezentovali své výsledky na více než stovce mezinárodních konferencí po celém světě. Jejich výsledky jsou hojně citovány (renomovaná mezinárodní databáze SCI registruje téměř dvě stovky takových citací). Nejvýznamnějšími publikacemi jsou ty v prestižních časopisech, jako například
- H. Kwakernaak and M. Šebek: Polynomial J-spectral factorization. IEEE Transactions on Automatic Control, vol. AC-39, pp. 315-328, Feb. 1994.
- D. Henrion and M. Šebek: Reliable numerical methods for polynomial matrix triangularization. IEEE Transactions on Automatic Control, Vol. AC-44, No. 3, pp. 497-508, March 1999.
- D. Henrion, M. Šebek: Improved Polynomial Matrix Determinant Computation. IEEE Transactions on Circuits and Systems, Part I: Fundamental Theory and Applications, Vol. 46, No. 10, pp. 1307-1308, 1999.
- D. Henrion, D. Arzelier, D. Peaucelle and M. Šebek: An LMI Condition for Robust Stability of Polynomial Matrix Polytopes. Automatica (IFAC), Vol. 37, pp. 461-468, 2001.
- D. Henrion: LMIs for Robust SPR Design. IEEE Transactions on Circuits and Systems, Part I: Fundamental Theory and Applications, Vol. 49, No. 7, pp. 1017-1020, 2002.
- D. Henrion, M. Šebek and V. Kučera: Positive polynomials and robust stabilization by fixed-order controllers. IEEE Transactions on Automatic Control, Vol. 48, No. 7, pp. 1178-1186, July 2003.
- D. Henrion, D. Peaucelle, D. Arzelier, and M. Šebek: Ellipsoidal Approximation of the Stability Domain of a Polynomial. IEEE Transactions on Automatic Control, Vol. 48, No. 12, pp. 2255-2259, December 2003.
- D. Henrion, J. C. Zúńiga: Detecting infinite zeros in polynomial matrices. IEEE Transactions on Circuits and Systems II, Vol. 52, No. 12, pp. 744-745, 2005
- Z. Hurák, A. Bottcher and M. Šebek: Minimum Distance to the Range of a Banded Lower Triangular Toeplitz Operator in l-1 and Application in l-1 Optimal Control. SIAM SICON, Vol. 45, 1, pp.107-122, 2006.