Victor Pan - Victor Pan

Victor Pan v roce 1996

Victor Yakovlevich Pan ( rusky : Пан Виктор Яковлевич ) je sovětský a americký matematik a počítačový vědec , známý pro svůj výzkum algoritmů pro polynomy a násobení matic .

Vzdělání a kariéra

Pan získal titul Ph.D. na Moskevské univerzitě v roce 1964 pod dohledem Anatolije Georgieviče Vituškina a pokračoval ve své práci v Sovětské akademii věd . Během té doby publikoval řadu významných prací a stal se neformálně známým jako „polynomial Pan“ pro svou průkopnickou práci v oblasti polynomiálních výpočtů . Na konci 70. let se přistěhoval do USA a zastával pozice v několika institucích včetně IBM Research . Od roku 1988 vyučuje na Lehman College na City University of New York .

Příspěvky

Victor Pan je odborníkem na výpočetní složitost a vyvinul řadu nových algoritmů . Jeden z jeho pozoruhodných raných výsledků je důkazem, že počet násobení v Hornerově metodě je optimální.

V teorii algoritmů násobení matic Pan v roce 1978 publikoval algoritmus s dobou běhu . Toto bylo první zlepšení oproti Strassenovu algoritmu po téměř deseti letech a odstartovalo dlouhou řadu vylepšení v rychlém násobení matic, které později zahrnovaly algoritmus Coppersmith – Winograd a následný vývoj. Napsal text How to Multiply Matrices Faster (Springer, 1984), mapující raný vývoj v této oblasti. Jeho algoritmus z roku 1982 stále držel rekord v roce 2020 v nejrychlejším „prakticky použitelném“ maticovém multiplikačním algoritmu (tj. S malou velikostí základny a zvládnutelnými skrytými konstantami). V roce 1998 Pan se svým studentem Xiaohan Huangem ukázal, že maticové multiplikační algoritmy mohou využívat výhod pravoúhlých matic s nevyváženými poměry stran , jejichž násobení je rychlejší než časové limity, které by bylo možné získat pomocí algoritmů násobení čtvercové matice.

Od té práce se Pan vrátil k symbolickému a numerickému počítání ak dřívějšímu tématu svého výzkumu, k výpočtům s polynomy. Vyvinul rychlé algoritmy pro numerický výpočet polynomiálních kořenů a s Bernardem Mourrainem algoritmy pro vícerozměrné polynomy založené na jejich vztazích ke strukturovaným maticím. Je také autorem nebo spoluautorem několika dalších knih o maticových a polynomiálních výpočtech, strukturovaných maticích a o postupech numerického hledání kořenů.

Uznání

Pan byl jmenován významným profesorem Lehman College v roce 2000.

V roce 2013 se stal kolega z amerického matematické společnosti pro „příspěvky k matematické teorii počítání“.

Vybrané publikace

Výzkumné práce

CVP. Pan, V. Ja. (1966), „O prostředcích výpočtu hodnot polynomů“, Russian Math. Průzkumy , 21 : 105–136, doi : 10,1070/rm1966v021n01abeh004147 , MR  0207178
SNO. Pan, V. Ya. (Říjen 1978), „Strassenův algoritmus není optimální: Trilineární technika agregace, spojování a rušení pro konstrukci rychlých algoritmů pro maticové operace“, Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS 1978) , IEEE, doi : 10.1109 /sfcs.1978.34 , S2CID  14348408
P82. Pan, Victor Y. (1982), "Trilineární agregace s implicitním rušením pro nové zrychlení multiplikace matice", Počítače a matematika s aplikacemi , 8 : 23–34, doi : 10,1016/0898-1221 (82) 90037-2 , MR  0644547
FRM. Huang, Xiaohan; Pan, Victor Y. (1998), „Rychlé násobení a aplikace pravoúhlé matice“, Journal of Complexity , 14 (2): 257–299, doi : 10,1006/jcom.1998.0476 , MR  1629113
MPD. Mourrain, Bernard; Pan, Victor Y. (2000), „Vícerozměrné polynomy, dualita a strukturované matice“ (PDF) , Journal of Complexity , 16 (1): 110–180, doi : 10,1006/jcom.1999.0530 , MR  1762401(vítěz, cena za nejlepší papír J. Complexity )
NAHORU. Pan, Victor Y. (2002), „Univariační polynomy: téměř optimální algoritmy pro numerickou faktorizaci a hledání kořenů“, Journal of Symbolic Computation , 33 (5): 701–733, doi : 10.1006/jsco.2002.0531 , MR  1919911

Knihy

HMM. Pan, Victor (1984), How to Multiply Matrices Faster , Lecture Notes in Computer Science, 179 , Berlin: Springer-Verlag, doi : 10.1007/3-540-13866-8 , ISBN 3-540-13866-8, S2CID  5280107
PMC. Bini, Dario; Pan, Victor Y. (1994), Polynomial and Matrix Computations, sv. I: Fundamental Algorithms , Progress in Theoretical Computer Science, Boston, MA: Birkhäuser, doi : 10.1007/978-1-4612-0265-3 , ISBN 0-8176-3786-9, S2CID  30728536
SMP. Pan, Victor Y. (2001), Structured Matrices and Polynomials: Unified Superfast Algorithms , New York: Springer-Verlag, doi : 10.1007/978-1-4612-0129-8 , ISBN 0-8176-4240-4
NMR. McNamee, JM; Pan, VY (2013), Numerical Methods for Roots of Polynomials, Part II , Studies in Computational Mathematics, 16 , Amsterdam: Elsevier/Academic Press, ISBN 978-0-444-52730-1

Reference

externí odkazy