Нарендра Кармаркар

Индийский математик (1956 г.р.)

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

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

биография

Кармаркар получил степень бакалавра технических наук в области электротехники в ИИТ Бомбея в 1978 году, степень магистра в Калифорнийском технологическом институте в 1979 году ^[3] и степень доктора компьютерных наук в Калифорнийском университете в Беркли в 1983 году под руководством Ричарда М. Карпа. . ^[4] Кармаркар был научным сотрудником в IBM Research (1983), членом технического персонала и научным сотрудником Исследовательского центра математических наук AT&T Bell Laboratories (1983–1998), профессором математики в Массачусетском технологическом институте (1991) в Институте. для углубленных исследований, Принстон (1996 г.), и профессор кафедры Хоми Бхабха в Институте фундаментальных исследований Тата в Мумбаи с 1998 по 2005 г. Он был научным советником председателя группы ТАТА (2006–2007 гг.). За это время Ратан Тата профинансировал его для увеличения масштаба суперкомпьютера, который он спроектировал и прототипировал в TIFR. Увеличенная модель в то время опередила суперкомпьютер в Японии и достигла лучшего рейтинга, когда-либо достигнутого Индией в области суперкомпьютеров. Он был директором-основателем лаборатории вычислительных исследований в Пуне, где проводилась работа по расширению масштабов. Он продолжает работать над своей новой архитектурой для суперкомпьютеров.

Работа

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

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

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

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

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

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

Награды

• Ассоциация вычислительной техники наградила его престижной премией Парижа Канеллакиса в 2000 году за его работу над методами внутренней точки с полиномиальным временем для линейного программирования за «конкретные теоретические достижения, которые оказали значительное и очевидное влияние на практику вычислений».
• Премия к 100-летию со дня рождения Шриниваса Рамануджана за 1999 год, вручаемая премьер-министром Индии.
• Премия выдающемуся выпускнику Индийского технологического института, Бомбей, 1996 г.
• Премия выдающемуся выпускнику факультета компьютерных наук и инженерии Калифорнийского университета в Беркли (1993 г.).
• Премия Фулкерсона в области дискретной математики, присуждаемая совместно Американским математическим обществом и Обществом математического программирования (1988).
• Сотрудник Bell Laboratories (с 1987 г.).
• Премия основателей Texas Instruments (1986).
• Международная премия молодым ученым Маркони (1985).
• Премия «Золотая тарелка» Американской академии достижений , вручаемая бывшим президентом США (1985). ^{[18] [19]}
• Премия Фредерика В. Ланчестера Американского общества исследования операций за лучший опубликованный вклад в исследование операций (1984).
• Золотая медаль президента Индии, ИИТ Бомбей (1978).

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

1. Нарендра Кармаркар в проекте «Математическая генеалогия ».
2. Томсон ISI. «Кармаркар, Нарендра К., высоко цитируемые исследователи ISI». Архивировано из оригинала 23 марта 2006 года . Проверено 20 июня 2009 г.
3. «Восемьдесят пятое ежегодное начало» (PDF) . Калифорнийский технологический институт. 8 июня 1979 г. с. 13.
4. Нарендра Кармаркар в проекте «Математическая генеалогия»
5. Кармаркар, Нарендра (1991). «Новая параллельная архитектура для вычислений с разреженной матрицей, основанная на конечной проективной геометрии». Материалы конференции ACM/IEEE 1991 года по суперкомпьютерам – Supercomputing '91 . стр. 358–369. дои : 10.1145/125826.126029. ISBN 0897914597. S2CID  6665759.
6. Кармаркар, Н.К., Рамакришнан, К.Г. «Результаты вычислений алгоритма внутренней точки для крупномасштабного линейного программирования». Математическое программирование. 52: 555–586 (1991).
7. Амрутер, Б.С., Джоши, Р., Кармаркар, Н.К. «Архитектура проективной геометрии для научных вычислений». Материалы международной конференции по прикладным матричным процессорам, Компьютерное общество IEEE, стр. 6480 (1992).
8. Кармаркар, Н.К. «Новая параллельная архитектура для научных вычислений, основанная на конечных проективных геометриях». Труды по математическому программированию, современное состояние, с. 136148 (1994).
9. Энджер, Натали (3 декабря 1984 г.). «Складывание идеального угла». Журнал Тайм . Архивировано из оригинала 4 декабря 2008 года . Проверено 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 ^{[ пустой URL-адрес ]} .
15. Кармаркар, Нарендра. «Расширенный алгоритмический подход к оптимизации». Исследования в Индии . Проверено 26 сентября 2003 г.
16. "Фокм 2014".
17. Кармаркар, Нарендра (2014). «К более широкому взгляду на теорию вычислений». arXiv : 1412.3335 [cs.NA].
18. "Обладатели Золотой пластины Американской академии достижений" . www.achievement.org . Американская академия достижений .
19. «Вундеркинды общаются с правильными вещами» (PDF) . Новости Роки Маунтин. 30 июня 1985 г.

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

• Почетный выпускник ИИТ Бомбей 1996 г.
• Воспоминание: метод внутренней точки для линейного программирования IIT Bombay Heritage Fund
• Функция Кармаркар в Scilab