2014

2015

2016

2017

2018

2019

2020

2022

2023

2024

Č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í.

Anotace Přednášející Poster

2024
2023
2022
2020
2019
2018
2017
2016
2015
2014

Přehrát záznam

28. brezna 2019

16:15

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

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.

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).

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.