Victor Yakovlevich Pan (en ruso : Пан Виктор Яковлевич ) es un matemático e informático soviético y estadounidense , conocido por su investigación sobre algoritmos para polinomios y multiplicación de matrices .
Educación y carrera
Pan obtuvo su Ph.D. en la Universidad de Moscú en 1964, bajo la supervisión de Anatoli Georgievich Vitushkin , [1] y continuó su trabajo en la Academia de Ciencias Soviética . Durante ese tiempo, publicó una serie de artículos importantes y se hizo conocido informalmente como "polinomio Pan" por su trabajo pionero en el área de cálculos polinomiales . A fines de la década de 1970, emigró a los Estados Unidos y ocupó cargos en varias instituciones, incluida IBM Research . Desde 1988, ha enseñado en Lehman College de la City University of New York . [2]
Contribuciones
Victor Pan es un experto en complejidad computacional y ha desarrollado varios algoritmos nuevos . Uno de sus primeros resultados notables es una prueba de que el número de multiplicaciones en el método de Horner es óptimo. [CVP]
En la teoría de los algoritmos de multiplicación de matrices , Pan en 1978 publicó un algoritmo con tiempo de ejecución. Esta fue la primera mejora sobre el algoritmo Strassen después de casi una década, y dio inicio a una larga línea de mejoras en la multiplicación rápida de matrices que luego incluyó el algoritmo Coppersmith-Winograd y desarrollos posteriores. [SNO] Escribió el texto How to Multiply Matrices Faster (Springer, 1984) examinando los primeros desarrollos en esta área. [3] [HMM] Su algoritmo de 1982 [P82] todavía tenía el récord en 2020 del algoritmo de multiplicación de matrices "prácticamente útil" más rápido (es decir, con un tamaño base pequeño y constantes ocultas manejables). [4] En 1998, con su alumno Xiaohan Huang, Pan demostró que los algoritmos de multiplicación de matrices pueden aprovechar las matrices rectangulares con relaciones de aspecto desequilibradas , multiplicándolas más rápidamente que los límites de tiempo que se obtendrían utilizando algoritmos de multiplicación de matrices cuadradas. [FRM]
Desde ese trabajo, Pan ha vuelto a la computación numérica y simbólica ya un tema anterior de su investigación, las computaciones con polinomios. Desarrolló algoritmos rápidos para el cálculo numérico de raíces polinomiales , [UP] y, con Bernard Mourrain, algoritmos para polinomios multivariados basados en sus relaciones con matrices estructuradas. [5] [MPD] También fue autor o coautor de varios libros más, sobre cálculo de matrices y polinomios, [6] [PMC] matrices estructuradas, [7] [SMP] y sobre procedimientos numéricos de búsqueda de raíces. [8] [RMN]
Reconocimiento
Pan fue nombrado profesor distinguido en Lehman College en 2000. [2]
En 2013 se convirtió en miembro de la American Mathematical Society , por "contribuciones a la teoría matemática de la computación". [9]
Publicaciones Seleccionadas
Trabajos de investigación
CVP. | Pan, V. Ja. (1966), "Sobre los medios para calcular valores de polinomios", Russian Math. Encuestas , 21 : 105–136, doi : 10.1070 / rm1966v021n01abeh004147 , MR 0207178 |
SNO. | Pan, V. Ya. (Octubre de 1978), "El algoritmo de Strassen no es óptimo: técnica trilineal de agregación, unión y cancelación para la construcción de algoritmos rápidos para operaciones matriciales", Actas del XIX Simposio Anual sobre Fundamentos de la Ciencia de la Computación (FOCS 1978) , IEEE, doi : 10.1109 /sfcs.1978.34 , S2CID 14348408 |
P82. | Pan, Victor Y. (1982), "Agregación trilineal con cancelación implícita para una nueva aceleración de la multiplicación de matrices", Computación y Matemáticas con Aplicaciones. , 8 : 23–34, doi : 10.1016 / 0898-1221 (82) 90037-2 , MR 0644547 |
FRM. | Huang, Xiaohan; Pan, Victor Y. (1998), "Multiplicación y aplicaciones rápidas de matrices rectangulares", Journal of Complexity , 14 (2): 257-299, doi : 10.1006 / jcom.1998.0476 , MR 1629113 |
MPD. | Mourrain, Bernard; Pan, Victor Y. (2000), "Polinomios multivariados, dualidad y matrices estructuradas" (PDF) , Journal of Complexity , 16 (1): 110–180, doi : 10.1006 / jcom.1999.0530 , MR 1762401(ganador, premio J. Complexity al mejor artículo) [5] |
ARRIBA. | Pan, Victor Y. (2002), "Polinomios univariados: algoritmos casi óptimos para la factorización numérica y la búsqueda de raíces", Journal of Symbolic Computation , 33 (5): 701–733, doi : 10.1006 / jsco.2002.0531 , MR 1919911 |
Libros
MMM. | Pan, Victor (1984), How to Multiply Matrices Faster , Lecture Notes in Computer Science, 179 , Berlín: Springer-Verlag, doi : 10.1007 / 3-540-13866-8 , ISBN 3-540-13866-8, S2CID 5280107[3] |
PMC. | Bini, Dario; Pan, Victor Y. (1994), Polinomios y cálculos matriciales, vol. I: Algoritmos fundamentales , Progreso en informática teórica, Boston, MA: Birkhäuser, doi : 10.1007 / 978-1-4612-0265-3 , ISBN 0-8176-3786-9, S2CID 30728536[6] |
SMP. | Pan, Victor Y. (2001), Matrices estructuradas y polinomios: Algoritmos superrápidos unificados , Nueva York: Springer-Verlag, doi : 10.1007 / 978-1-4612-0129-8 , ISBN 0-8176-4240-4[7] |
RMN. | McNamee, JM; Pan, VY (2013), Métodos numéricos para raíces de polinomios, Parte II , Estudios en matemáticas computacionales, 16 , Amsterdam: Elsevier / Academic Press, ISBN 978-0-444-52730-1[8] |
Referencias
- ^ Victor Pan en el Proyecto de genealogía de las matemáticas
- ^ a b Victor Pan, de la facultad de matemáticas de Lehman, seleccionado como profesor distinguido , Lehman College , archivado desde el original el 14 de febrero de 2018
- ^ a b Reseñas de cómo multiplicar matrices más rápido :
- Gladwell, Ian (1986), Mathematical Reviews , Lecture Notes in Computer Science, 179 , doi : 10.1007 / 3-540-13866-8 , ISBN 978-3-540-13866-2, MR 0765701 , S2CID 5280107CS1 maint: publicación periódica sin título ( enlace )
- Coppersmith, Don (julio de 1986), SIAM Review , 28 (2): 250–252, doi : 10.1137 / 1028072 , JSTOR 2030488CS1 maint: publicación periódica sin título ( enlace )
- Probert, Robert L. (noviembre-diciembre de 1986), American Scientist , 74 (6): 682, JSTOR 27854420CS1 maint: publicación periódica sin título ( enlace )
- ^ Karstadt, Elaye; Schwartz, Oded (2020), "Multiplicación de matrices, un poco más rápido", Journal of the ACM , 67 (1), doi : 10.1145 / 3364504 , MR 4061328
- ^ a b "Premios al mejor artículo" , Journal of Complexity , consultado el 16 de octubre de 2018
- ^ a b Reseñas de cálculos polinomiales y matriciales :
- Gupta, Murli M. (1995), Revisiones matemáticas , doi : 10.1007 / 978-1-4612-0265-3 , ISBN 978-1-4612-6686-0, MR 1289412 , S2CID 30728536CS1 maint: publicación periódica sin título ( enlace )
- Tate, Stephen R. (junio de 1995), ACM SIGACT News , 26 (2): 26-27, doi : 10.1145 / 202840.606473 , S2CID 4740448CS1 maint: publicación periódica sin título ( enlace )
- Eberly, Wayne (marzo de 1996), SIAM Review , 38 (1): 161–165, doi : 10.1137 / 1038020 , JSTOR 2132983CS1 maint: publicación periódica sin título ( enlace )
- Higham, Nicholas J. (abril de 1996), Matemáticas de Computación , 65 (214): 888–889, JSTOR 2153629CS1 maint: publicación periódica sin título ( enlace )
- Emiris, IZ; Galligo, A. (septiembre de 1996), ACM SIGSAM Bulletin , 30 (3): 21–23, doi : 10.1145 / 240065.570109 , S2CID 14598227CS1 maint: publicación periódica sin título ( enlace )
- ^ a b Revisión de matrices estructuradas y polinomios :
- Melman, Aaron (2002), revisiones matemáticas , doi : 10.1007 / 978-1-4612-0129-8 , ISBN 978-1-4612-6625-9, MR 1843842CS1 maint: publicación periódica sin título ( enlace )
- ^ a b Revisión de métodos numéricos para raíces de polinomios, Parte II :
- Proinov, Petko D., Revisiones matemáticas , MR 3293902CS1 maint: publicación periódica sin título ( enlace )
- ^ "List of Fellows of the American Mathematical Society" , American Mathematical Society , consultado el 22 de mayo de 2015
enlaces externos
- Publicaciones de Victor Pan indexadas por Google Scholar
- Perfil en científico estadounidense