Victor Pan

Victor Pan 1996

Victor Yakovlevich Pan ( ryska : Пан Виктор Яковлевич ) är en sovjetisk och amerikansk matematiker och datavetare , känd för sin forskning om algoritmer för polynom och matrismultiplikation .

Utbildning och karriär

Pan tog sin doktorsexamen. vid Moskvas universitet 1964, under överinseende av Anatoli Georgievich Vitushkin , och fortsatte sitt arbete vid den sovjetiska vetenskapsakademin . Under den tiden publicerade han ett antal betydande artiklar och blev informellt känd som "polynomial Pan" för sitt banbrytande arbete inom området polynomberäkningar . I slutet av 1970-talet immigrerade han till USA och hade befattningar på flera institutioner inklusive IBM Research . Sedan 1988 har han undervisat vid Lehman College vid City University of New York .

Bidrag

Victor Pan är expert på beräkningskomplexitet och har utvecklat ett antal nya algoritmer . Ett av hans anmärkningsvärda tidiga resultat är ett bevis på att antalet multiplikationer i Horners metod är optimalt.

I teorin om matrismultiplikationsalgoritmer publicerade Pan 1978 en algoritm med körtid $O(n^{2.795})$ . Detta var den första förbättringen jämfört med Strassen-algoritmen efter nästan ett decennium, och startade en lång rad förbättringar av snabb matrismultiplikation som senare inkluderade Coppersmith- Winograd-algoritmen och efterföljande utvecklingar. Han skrev texten How to Multiply Matrices Faster (Springer, 1984) och kartlade den tidiga utvecklingen inom detta område. Hans algoritm från 1982 hade fortfarande rekordet 2020 för den snabbaste "praktiskt sett användbara" matrismultiplikationsalgoritmen (dvs med en liten basstorlek och hanterbara dolda konstanter). 1998, tillsammans med sin elev Xiaohan Huang, visade Pan att matrismultiplikationsalgoritmer kan dra fördel av rektangulära matriser med obalanserade bildförhållanden och multiplicera dem snabbare än de tidsgränser man skulle få med kvadratmatrismultiplikationsalgoritmer.

Sedan det arbetet har Pan återvänt till symbolisk och numerisk beräkning och till ett tidigare tema för sin forskning, beräkningar med polynom. Han utvecklade snabba algoritmer för numerisk beräkning av polynomrötter, och tillsammans med Bernard Mourrain algoritmer för multivariata polynom baserat på deras relationer till strukturerade matriser. Han skrev eller var medförfattare till flera fler böcker, om matris- och polynomberäkning, strukturerade matriser och om numeriska rotsökningsprocedurer.

Erkännande

Pan utnämndes till Distinguished Professor vid Lehman College 2000.

2013 blev han fellow i American Mathematical Society , för "bidrag till den matematiska teorin om beräkning".

Utvalda publikationer

Forskningspapper

CVP.

   Pan, V. Ja. (1966), "Om sätt att beräkna värden på polynom", Russian Math. Surveys , 21 : 105–136, doi : 10.1070/rm1966v021n01abeh004147 , MR 0207178 , S2CID 250869179

SNO.

  Pan, V. Ya. (Oktober 1978), "Strassens algoritm är inte optimal: Trilinjär teknik för att aggregera, förena och avbryta för att konstruera snabba algoritmer för matrisoperationer", Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS 1978) , IEEE , doi : 11010 /sfcs.1978.34 , S2CID 14348408

P82.

  Pan, Victor Y. (1982), "Trilinear aggregating with implicit cancelling for a new acceleration of matrix multiplification", Computers and Mathematics with Applications , 8 : 23–34, doi : 10.1016/0898-1221(82)90037-2 , MR 0644547

FRM.

  Huang, Xiaohan; Pan, Victor Y. (1998), "Snabb rektangulär matrismultiplikation och tillämpningar", Journal of Complexity , 14 (2): 257–299, doi : 10.1006/jcom.1998.0476 , MR 1629113

MPD.

  Mourrain, Bernard; Pan, Victor Y. (2000), "Multivariate polynomials, duality, and structured matrices" (PDF) , Journal of Complexity , 16 (1): 110–180, doi : 10.1006/jcom.1999.0530 , MR 17624 , J01 . Complexity best paper award)

UPP.

  Pan, Victor Y. (2002), "Univariate polynomials: nearly optimal algorithms for numerical factorization and root-finding", Journal of Symbolic Computation , 33 (5): 701–733, doi : 10.1006/jsco.2002.0531 , MR 199

Böcker

HMM.

   Pan, Victor (1984), How to Multiply Matrices Faster , Lecture Notes in Computer Science, vol. 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, Vol. 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, Del II , Studies in Computational Mathematics, vol. 16, Amsterdam: Elsevier/Academic Press, ISBN 978-0-444-52730-1

externa länkar

• Victor Pan -publikationer indexerade av Google Scholar
• Profil i American Scientist