Виктор Пан

Виктор Яковлевич Пан ( русский : Пан Виктор Яковлевич ) — советский и американский математик и ученый-компьютерщик , известный своими исследованиями в области алгоритмов вычисления многочленов и умножения матриц .

Образование и карьера

Пан получил докторскую степень. в Московском университете в 1964 году под руководством Анатолия Георгиевича Витушкина , ^[1] и продолжил свою работу в Академии наук СССР . За это время он опубликовал ряд важных статей и стал неофициально известен как «полиномиальный Пан» за свою новаторскую работу в области полиномиальных вычислений . В конце 1970-х годов он иммигрировал в Соединенные Штаты и занимал должности в нескольких учреждениях, включая IBM Research . С 1988 года преподавал в Леман-колледже Городского университета Нью-Йорка . ^[2]

Взносы

Виктор Пан является экспертом в области вычислительной сложности и разработал ряд новых алгоритмов . Одним из его примечательных ранних результатов является доказательство того, что количество умножений в методе Хорнера оптимально. ^[ЦВП]

В теории алгоритмов умножения матриц Пан в 1978 году опубликовал алгоритм с временем выполнения $O(n^{2.795})$ . Это было первое улучшение алгоритма Штрассена почти за десятилетие, и оно положило начало длинной череде улучшений в быстром умножении матриц, которые позже включали алгоритм Копперсмита-Винограда и последующие разработки. ^[СНО] Он написал текст «Как быстрее умножать матрицы» (Springer, 1984), в котором исследовал ранние разработки в этой области. ^[3]^[ХМ] Его алгоритм 1982 года ^[С82] в 2020 году по-прежнему удерживал рекорд по самому быстрому «практически полезному» алгоритму умножения матриц (т. е. с небольшим базовым размером и управляемыми скрытыми константами). ^[4] В 1998 году вместе со своим учеником Сяоханем Хуаном Пан показал, что алгоритмы умножения матриц могут использовать преимущества прямоугольных матриц с несбалансированными соотношениями сторон , умножая их быстрее, чем временные границы, которые можно было бы получить с помощью алгоритмов умножения квадратных матриц. ^[ФРМ]

После этой работы Пан вернулся к символьным и числовым вычислениям, а также к более ранней теме своих исследований — вычислениям с полиномами. Он разработал быстрые алгоритмы численного вычисления корней многочленов . ^[ВВЕРХ]и совместно с Бернаром Морреном алгоритмы для многомерных полиномов, основанные на их отношениях со структурированными матрицами. ^[5]^[МПД]Он также является автором или соавтором еще нескольких книг по матричным и полиномиальным вычислениям. ^[6]^[ЧВК]структурированные матрицы, ^[7]^{[МЛАДШАЯ СРЕДНЯЯ ШКОЛА]} и дальшечисленные процедуры поиска корня. ^[8]^[ЯМР]

Признание

Пан был назначен заслуженным профессором Леман-колледжа в 2000 году. ^[2]

В 2013 году он стал членом Американского математического общества за «вклад в математическую теорию вычислений». ^[9]

Избранные публикации

Научные статьи

ЦВП.

Пан, В.Я. (1966), "О средствах вычисления значений многочленов", Изв. матем. Опросы , 21 : 105–136, doi : 10.1070/rm1966v021n01abeh004147 , MR 0207178 , S2CID 250869179

СНО.

Пан, В.Я. (Октябрь 1978 г.), «Алгоритм Штрассена неоптимален: трилинейная техника агрегирования, объединения и сокращения для построения быстрых алгоритмов для матричных операций», Труды 19-го ежегодного симпозиума по основам информатики (FOCS 1978) , IEEE, doi : 10.1109 /sfcs.1978.34 , S2CID 14348408

Р82.

Пан, Виктор Ю. (1982), «Трилинейное агрегирование с неявным сокращением для нового ускорения матричного умножения», Computers and Mathematics with Applications , 8 : 23–34, doi : 10.1016/0898-1221(82)90037-2 , МР 0644547

ФРМ.

Хуан, Сяохань; Пан, Виктор Ю. (1998), «Быстрое умножение прямоугольных матриц и приложения», Journal of Complexity , 14 (2): 257–299, doi : 10.1006/jcom.1998.0476 , MR 1629113

МПД.

Муррен, Бернар; Пан, Виктор Ю. (2000), «Многомерные полиномы, двойственность и структурированные матрицы» (PDF) , Journal of Complexity , 16 (1): 110–180, doi : 10.1006/jcom.1999.0530 , MR 1762401 (победитель, J по сложности ) Награда за лучшую работу ^[5]

ВВЕРХ.

Пан, Виктор Ю. (2002), «Одномерные полиномы: почти оптимальные алгоритмы числовой факторизации и поиска корней», Journal of Символические вычисления , 33 (5): 701–733, doi : 10.1006/jsco.2002.0531 , MR 1919911

Книги

ХМ.

Пан, Виктор (1984), Как быстрее умножать матрицы , Конспект лекций по информатике, том. 179, Берлин: Springer-Verlag, номер номера : 10.1007/3-540-13866-8 , ISBN. 3-540-13866-8 , S2CID 5280107 ^[3]

ЧВК.

Бини, Дарио; Пан, Виктор Ю. (1994), Полиномиальные и матричные вычисления, Vol. I: Фундаментальные алгоритмы , Прогресс в теоретической информатике, Бостон, Массачусетс: Биркхойзер, номер документа : 10.1007/978-1-4612-0265-3 , ISBN 0-8176-3786-9 , S2CID 30728536 ^[6]

МЛАДШАЯ СРЕДНЯЯ ШКОЛА.

Пан, Виктор Ю. (2001), Структурированные матрицы и полиномы: унифицированные сверхбыстрые алгоритмы , Нью-Йорк: Springer-Verlag, doi : 10.1007/978-1-4612-0129-8 , ISBN 0-8176-4240-4 ^[7]

ЯМР.

МакНэми, Дж. М.; Пан, В.Я. (2013), Численные методы поиска корней полиномов, Часть II , Исследования по вычислительной математике, том. 16, Амстердам: Elsevier/Academic Press, ISBN 978-0-444-52730-1 ^[8]

Ссылки

^ Виктор Пэн в проекте «Математическая генеалогия»
^ Jump up to: ^а ^б Виктор Пан с математического факультета Lehman выбран заслуженным профессором Lehman College , заархивировано из оригинала 14 февраля 2018 г.
^ Jump up to: ^а ^б
Обзоры о том, как быстрее умножать матрицы :
- Гладуэлл, Ян (1986), Математические обзоры , Конспекты лекций по информатике, 179 , номер документа : 10.1007/3-540-13866-8 , ISBN 978-3-540-13866-2 , МР 0765701 , S2CID 5280107 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
- Копперсмит, Дон (июль 1986 г.), SIAM Review , 28 (2): 250–252, doi : 10.1137/1028072 , JSTOR 2030488 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
- Проберт, Роберт Л. (ноябрь – декабрь 1986 г.), американский ученый , 74 (6): 682, JSTOR 27854420. {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
^ Карштадт, Илай; Шварц, Одед (2020), «Умножение матриц, немного быстрее», Журнал ACM , 67 (1): 1–31, doi : 10.1145/3364504 , MR 4061328 , S2CID 211041916
^ Jump up to: ^а ^б «Награда за лучшую статью» , Journal of Complexity , получено 16 октября 2018 г.
^ Jump up to: ^а ^б
Обзоры полиномиальных и матричных вычислений :
- Гупта, Мурли М. (1995), Математические обзоры , номер документа : 10.1007/978-1-4612-0265-3 , ISBN 978-1-4612-6686-0 , МР 1289412 , S2CID 30728536 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
- Тейт, Стивен Р. (июнь 1995 г.), ACM SIGACT News , 26 (2): 26–27, doi : 10.1145/202840.606473 , S2CID 4740448 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
- Эберли, Уэйн (март 1996 г.), SIAM Review , 38 (1): 161–165, doi : 10.1137/1038020 , JSTOR 2132983 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
- Хайэм, Николас Дж. (апрель 1996 г.), Математика вычислений , 65 (214): 888–889, JSTOR 2153629 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
- Эмирис, ИЗ; Галлиго, А. (сентябрь 1996 г.), Бюллетень ACM SIGSAM , 30 (3): 21–23, doi : 10.1145/240065.570109 , S2CID 14598227 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
^ Jump up to: ^а ^б
Обзор структурированных матриц и полиномов :
- Мелман, Аарон (2002), Математические обзоры , номер документа : 10.1007/978-1-4612-0129-8 , ISBN 978-1-4612-6625-9 , МР 1843842 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
^ Jump up to: ^а ^б
Обзор численных методов поиска корней многочленов, часть II :
- Проинов Петко Д., Математическое обозрение , MR 3293902 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
^ «Список членов Американского математического общества» , Американское математическое общество , получено 22 мая 2015 г.

Внешние ссылки

Публикации Виктора Пана , индексируемые Google Scholar
Профиль в журнале American Scientist

[mgp-1] Виктор Пэн в проекте «Математическая генеалогия»

[lehman-2] Jump up to: ^а ^б Виктор Пан с математического факультета Lehman выбран заслуженным профессором Lehman College , заархивировано из оригинала 14 февраля 2018 г.

[how-3] Jump up to: ^а ^б Обзоры о том, как быстрее умножать матрицы :
Гладуэлл, Ян (1986), Математические обзоры , Конспекты лекций по информатике, 179 , номер документа : 10.1007/3-540-13866-8 , ISBN 978-3-540-13866-2 , МР 0765701 , S2CID 5280107 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
Копперсмит, Дон (июль 1986 г.), SIAM Review , 28 (2): 250–252, doi : 10.1137/1028072 , JSTOR 2030488 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
Проберт, Роберт Л. (ноябрь – декабрь 1986 г.), американский ученый , 74 (6): 682, JSTOR 27854420. {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )

[4] Гладуэлл, Ян (1986), Математические обзоры , Конспекты лекций по информатике, 179 , номер документа : 10.1007/3-540-13866-8 , ISBN 978-3-540-13866-2 , МР 0765701 , S2CID 5280107 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )

[5] Копперсмит, Дон (июль 1986 г.), SIAM Review , 28 (2): 250–252, doi : 10.1137/1028072 , JSTOR 2030488 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )

[6] Проберт, Роберт Л. (ноябрь – декабрь 1986 г.), американский ученый , 74 (6): 682, JSTOR 27854420. {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )

[KS-4] Карштадт, Илай; Шварц, Одед (2020), «Умножение матриц, немного быстрее», Журнал ACM , 67 (1): 1–31, doi : 10.1145/3364504 , MR 4061328 , S2CID 211041916

[jcbpa-5] Jump up to: ^а ^б «Награда за лучшую статью» , Journal of Complexity , получено 16 октября 2018 г.

[polymat-6] Jump up to: ^а ^б Обзоры полиномиальных и матричных вычислений :
Гупта, Мурли М. (1995), Математические обзоры , номер документа : 10.1007/978-1-4612-0265-3 , ISBN 978-1-4612-6686-0 , МР 1289412 , S2CID 30728536 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
Тейт, Стивен Р. (июнь 1995 г.), ACM SIGACT News , 26 (2): 26–27, doi : 10.1145/202840.606473 , S2CID 4740448 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
Эберли, Уэйн (март 1996 г.), SIAM Review , 38 (1): 161–165, doi : 10.1137/1038020 , JSTOR 2132983 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
Хайэм, Николас Дж. (апрель 1996 г.), Математика вычислений , 65 (214): 888–889, JSTOR 2153629 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )
Эмирис, ИЗ; Галлиго, А. (сентябрь 1996 г.), Бюллетень ACM SIGSAM , 30 (3): 21–23, doi : 10.1145/240065.570109 , S2CID 14598227 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )

[10] Гупта, Мурли М. (1995), Математические обзоры , номер документа : 10.1007/978-1-4612-0265-3 , ISBN 978-1-4612-6686-0 , МР 1289412 , S2CID 30728536 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )

[11] Тейт, Стивен Р. (июнь 1995 г.), ACM SIGACT News , 26 (2): 26–27, doi : 10.1145/202840.606473 , S2CID 4740448 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )

[12] Эберли, Уэйн (март 1996 г.), SIAM Review , 38 (1): 161–165, doi : 10.1137/1038020 , JSTOR 2132983 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )

[13] Хайэм, Николас Дж. (апрель 1996 г.), Математика вычислений , 65 (214): 888–889, JSTOR 2153629 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )

[14] Эмирис, ИЗ; Галлиго, А. (сентябрь 1996 г.), Бюллетень ACM SIGSAM , 30 (3): 21–23, doi : 10.1145/240065.570109 , S2CID 14598227 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )

[struc-7] Jump up to: ^а ^б Обзор структурированных матриц и полиномов :
Мелман, Аарон (2002), Математические обзоры , номер документа : 10.1007/978-1-4612-0129-8 , ISBN 978-1-4612-6625-9 , МР 1843842 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )

[16] Мелман, Аарон (2002), Математические обзоры , номер документа : 10.1007/978-1-4612-0129-8 , ISBN 978-1-4612-6625-9 , МР 1843842 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )

[numroot-8] Jump up to: ^а ^б Обзор численных методов поиска корней многочленов, часть II :
Проинов Петко Д., Математическое обозрение , MR 3293902 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )

[18] Проинов Петко Д., Математическое обозрение , MR 3293902 {{citation}}: CS1 maint: периодическое издание без названия ( ссылка )

[fams-9] «Список членов Американского математического общества» , Американское математическое общество , получено 22 мая 2015 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Базы данных авторитетного контроля
Международный	ЯВЛЯЮТСЯ ВИАФ WorldCat
Национальный	Германия Израиль Бельгия Соединенные Штаты Чешская Республика Нидерланды
академики	ДБЛП Google Академика MathSciNet Проект математической генеалогии zbMATH
Другой	ИдРеф