Нарендра Кармаркар - Narendra Karmarkar

Нарендра Кришна Кармаркар
Родившийся15 ноября 1955 г.
Гвалиор, Мадхья-Прадеш, Индия
Альма-матерИИТ Бомбей (B.Tech)
Калтех (РС.)
Калифорнийский университет в Беркли (Кандидат наук.)
ИзвестенАлгоритм Кармаркара
Научная карьера
ПоляМатематика, Компьютерная наука
УчрежденияBell Labs
ТезисКак справиться с NP-трудными проблемами (1983)
ДокторантРичард М. Карп[1]

Нарендра Кришна Кармаркар (1955 г.р.) Индийский математик. Кармаркар разработан Алгоритм Кармаркара. Он указан как ISI высоко цитируемый исследователь.[2]

Он изобрел один из первых алгоритмов доказуемо полиномиального времени для линейное программирование, который обычно называют методом внутренней точки. Алгоритм является краеугольным камнем в области линейного программирования. Он опубликовал свой знаменитый результат в 1984 году, когда работал на Bell Laboratories в Нью-Джерси.

биография

Кармаркар получил B.Tech в области электротехники от ИИТ Бомбей в 1978 г. РС. от Калифорнийский технологический институт в 1979 г.[3] и Кандидат наук. в области компьютерных наук из Калифорнийский университет в Беркли в 1983 г. под руководством Ричард М. Карп.[4]Кармаркар был научным сотрудником исследовательского центра IBM (1983 г.), членом технического персонала и научным сотрудником Исследовательского центра математических наук, AT&T Bell Laboratories (1983–1998 гг.), Профессором математики в Массачусетском технологическом институте (1991 г.) в Институте перспективных исследований. , Принстон (1996), и профессор кафедры Хоми Бхабха в Институт фундаментальных исследований Тата в Мумбаи с 1998 по 2005 год. Кармаркар был профинансирован Ратаном Татой для создания лабораторий вычислительных исследований в Пуне. Он создал команду из более чем 50 докторов наук для этой команды. Он был научным советником председателя группы TATA (2006-2007). В настоящее время он работает над новой архитектурой для суперкомпьютеров.

Работа

Алгоритм Кармаркара

Основная статья: Алгоритм Кармаркара

Алгоритм Кармаркара решает линейное программирование проблемы в полиномиальное время. Эти проблемы представлены рядом линейных ограничений, включающих ряд переменных. Предыдущий метод решения этих задач заключался в рассмотрении задачи как твердого тела большой размерности с вершинами, где решение достигалось путем перехода от вершины к вершине. Новый метод Кармаркара приближается к решению, пересекая указанное выше твердое тело. Следовательно, сложные задачи оптимизации решаются намного быстрее с помощью алгоритма Кармаркара. Практическим примером такой эффективности является решение сложной проблемы оптимизации сети связи, когда время решения сократилось с недель до дней. Таким образом, его алгоритм позволяет быстрее принимать деловые и политические решения. Алгоритм Кармаркара стимулировал развитие нескольких методы внутренней точки, некоторые из которых используются в текущих реализациях решателей линейных программ.

Геометрия Галуа

После работы над Метод внутренней точки, Кармаркар работал над новым архитектура за суперкомпьютеры на основе концепций из конечная геометрия, особенно проективная геометрия над конечные поля.[5][6][7][8]

Текущие расследования

В настоящее время он синтезирует эти концепции с некоторыми новыми идеями, которые он называет лепка свободного пространства (нелинейный аналог того, что обычно называют складывание идеального угла).[9] Такой подход позволяет ему распространить эту работу на физический дизайн машин. Сейчас он публикует обновления о своей недавней работе,[10] включая расширенную аннотацию.[11] Эта новая парадигма была представлена ​​на IVNC, Польша 16 июля 2008 г.,[12] и в Массачусетский технологический институт 25 июля 2008 г.[13] Некоторые из его недавних работ опубликованы на ieeexplore.[14] Он прочел лекцию о своей работе в ИИТ Бомбей в сентябре 2013 г.[15] Он прочитал цикл лекций из четырех частей на FOCM 2014 (Основы вычислительной математики).[16] под названием «К более широкому взгляду на теорию вычислений». Первая часть этой серии лекций доступна в архиве Корнелла.[17]


Награды

  • В Ассоциация вычислительной техники наградил его престижным Премия Пэрис Канеллакис в 2000 году за его работу над методами внутренней точки с полиномиальным временем для линейного программирования для «конкретных теоретических достижений, которые оказали значительное и очевидное влияние на практику вычислений».

Рекомендации

  1. ^ Нарендра Кармаркар на Проект "Математическая генеалогия".
  2. ^ Томсон ISI. "Кармаркар, Нарендра К., Цитируемые исследователи ISI". Архивировано из оригинал 23 марта 2006 г.. Получено 20 июн 2009.
  3. ^ «Восемьдесят пятое ежегодное открытие» (PDF). Калифорнийский технологический институт. 8 июня 1979 г. с. 13.
  4. ^ Нарендра Кармаркар на Проект "Математическая генеалогия"
  5. ^ Кармаркар, Нарендра. «Новая параллельная архитектура для вычисления разреженных матриц на основе конечных проективных геометрий». Материалы конференции ACM / IEEE 1991 г. по суперкомпьютерам.
  6. ^ Кармаркар, Н.К., Рамакришнан, К.Г. Результаты вычислений алгоритма внутренней точки для крупномасштабного линейного программирования., Математическое программирование. 52: 555-586 (1991).
  7. ^ 28. Амрутер Б. С., Джоши Р., Кармаркар Н. К. Архитектура проективной геометрии для научных вычислений, Труды Международной конференции по специализированным процессорам для массивов, IEEE Computer Society, стр. 6480 (1992).
  8. ^ Кармаркар, Н. К., Новая параллельная архитектура для научных вычислений, основанная на конечной проективной геометрии, Процесс математического программирования, Современное состояние, стр. 136148 (1994)
  9. ^ Анжер, Натали (3 декабря 1984 г.). «Складывание идеального угла». Журнал Тайм. Получено 12 июля 2008.
  10. ^ Кармармар, Нарендра (11 июля 2008 г.). "Недавнее исследование Нарендры Кармаркара". punetech.com. Получено 12 июля 2008.
  11. ^ Кармармар, Нарендра (11 июля 2008 г.). «Массивно параллельные системы и глобальная оптимизация» (PDF). punetech.com Недавние работы Нарендры Кармаркар. Получено 12 июля 2008.
  12. ^ Кармармар, Нарендра (14 июля 2008 г.). «Устройства вакуумной наноэлектроники с точки зрения теории оптимизации» (PDF). punetech.com Недавние работы Нарендры Кармаркар. Получено 14 июля 2008.
  13. ^ Кармаркар, Нарендра. «Семинар по параллельным системам и глобальной оптимизации». Вычислительные исследования в Бостоне. Получено 12 июля 2008.
  14. ^ http://ieeexplore.ieee.org/xpl/tocresult.jsp?isnumber=5166089&isYear=2009
  15. ^ Кармаркар, Нарендра. «Продвинутый алгоритмический подход к оптимизации». Исследования в Индии. Получено 26 сентября 2003.
  16. ^ https://www.fing.edu.uy/eventos/focm2014/
  17. ^ Кармаркар, Нарендра (2014). «К более широкому взгляду на теорию вычислений». arXiv:1412.3335 [cs.NA ].
  18. ^ "Золотые медали Американской академии достижений". www.achievement.org. Американская академия достижений.
  19. ^ «Вундеркинды натирают локти правильными вещами» (PDF). Новости Скалистых гор. 30 июня 1985 г.

внешняя ссылка