2014
2015
2016
2017
2018
2019

Čtyřicátéprvní setkání Pražského informatického semináře

Zdeněk Strakoš

Příběh konjugovaných gradientů

O metodě konjugovaných gradientů, označované jako jeden z deseti nejvýznamnějších algoritmických počinů dvacátého století, se píše v každé rozumné učebnici numerické matematiky a byla implementována v mnoha běžně dostupných softwarových knihovnách. Mohlo by se tedy zdát, že jde o součást dobře pochopené matematické a informatické historie. Zjevně však tomu tak zdaleka není.

28. brezna 2019

16:15

Posluchárna E-107, FEL ČVUT
Karlovo nám. 13, Praha 2
Zobrazit na mapě

Anotace přednášky

O metodě konjugovaných gradientů, označované jako jeden z deseti nejvýznamnějších algoritmických počinů dvacátého století, se píše v každé rozumné učebnici numerické matematiky a byla implementována v mnoha běžně dostupných softwarových knihovnách. Mohlo by se tedy zdát, že jde o součást dobře pochopené matematické a informatické historie. Zjevně však tomu tak zdaleka není. Přes nepochybnou praktickou užitečnost, krásu a eleganci její matematické formulace provází metodu konjugovaných gradientů stále nepochopení, zmatky a mýty. Stručně řečeno, kořenem potíží je přetrvávající snaha o lineární zjednodušení silně nelineárního jevu. Protože je navíc metoda konjugovaných gradientů založena na krátkých rekurencích, při praktických výpočtech vlivem zaokrouhlování typicky dochází k dramatické ztrátě ortogonality a lineární nezávislosti mezi generovanými směrovými vektory.

Tím se (zdánlivě) zhroutí veškerá matematická teorie principiálně založená na ortogonalitě generovaných bází. S připomenutím prací C. Paige a A. Greenbaumové ukážeme, jak lze s využitím souvislostí metody konjugovaných gradientů (a s ní úzce svázané Lanczosovy metody) s klasickými výsledky z několika oborů matematiky lépe porozumět výpočtům zatíženým zaokrouhlovacími chybami. V závěru ukážeme výsledky z poslední doby spojující příslušnou teorii s novým pohledem na efektivitu praktických postupů při výpočtech.

Přednášející

Zdeněk Strakoš

Po absolvování matematického inženýrství na FJFI ČVUT (1981) se zaměřením na obyčejné diferenciální rovnice změnil Zdeněk Strakoš obor a několik let se věnoval paralelním počítačovým architekturám a algoritmům. S tím postupně rostl i jeho zájem o otázky nepřesnosti výpočtů, včetně numerické nestability metody konjugovaných gradientů, což vedlo ke spolupráci s A. Greenbaumovou a G. H. Golubem v devadesátých letech a k několika dlouhodobým pobytům v USA (IMA, University of Minnesota, Stanford University a Emory University). Od roku 2000 trvale působí v ČR. Ve své práci se věnuje různým oblastem výpočtové matematiky. Snaží se o vidění otázek v souvislostech a z pohledu více oborů. K metodě konjugovaných gradientů se opakovaně vrací (od prvního článku v roce 1991 k letošnímu článku o spektrální informaci u předpodmíněných eliptických parciálních diferenciálních rovnic a chování metody). Zdeněk Strakoš je spoluautorem dvou monografií (Oxford University Press, 2013; SIAM, 2015) a cca 50 článků (např. Acta Numerica, SIAM Review, IMAJNA, SIMAX, SISC, Numerische Mathematik, Parallel Computing). Je nositelem několika významných mezinárodních uznání. Mezinárodní vědecké komunitě slouží také jako člen a předseda komisí pro udělování grantů (např. ERC AdG Panel PE6 - Computer Science and Informatics, 2008-2014) a ocenění (např. ICIAM Collatz Prize 2019, SIAM G. Pólya Prize 2019).

O PRAŽSKÉM INFORMATICKÉM SEMINÁŘI

Seminář se schází zpravidla 4. čtvrtek v měsíci v 16:15 hod. (s výjimkou letních měsíců a prosince), a to buď v budově FEL ČVUT na Karlově náměstí, nebo v budově MFF UK na Malostranském náměstí.

Jeho program je tvořen hodinovou přednáškou, po níž následuje časově neomezená diskuse. Základem přednášky je něco (v mezinárodním měřítku) mimořádného nebo aspoň pozoruhodného, na co přednášející přišel a co vysvětlí způsobem srozumitelným a zajímavým i pro širší informatickou obec. Přednášky jsou standardně v angličtině.

Seminář připravuje organizační výbor ve složení Roman Barták (MFF UK), Jaroslav Hlinka (ÚI AV ČR), Michal Chytil, Pavel Kordík (FIT ČVUT), Michal Koucký (MFF UK), Jan Kybic (FEL ČVUT), Michal Pěchouček (FEL ČVUT), Jiří Sgall (MFF UK), Vojtěch Svátek (FIS VŠE), Michal Šorel (ÚTIA AV ČR), Tomáš Werner (FEL ČVUT), Filip Železný (FEL ČVUT)

Idea Pražského informatického semináře vznikla z rozhovorů představitelů několika vědeckých institucí na téma, jak odstranit zbytečnou fragmentaci informatické komunity v ČR.

Podporovatelé

Kontakt