Нарендра Кармаркар
Нарендра Кришна Кармаркар | |
|---|---|
| Рожденный | около 1956 года Гвалиор , Мадхья-Прадеш , Индия |
| Альма-матер | ИИТ Бомбей (бакалавр технических наук) Калифорнийский технологический институт (Миссисипи) Калифорнийский университет в Беркли (доктор философии) |
| Известный | Алгоритм Кармаркара |
| Научная карьера | |
| Поля | Математика , информатика |
| Учреждения | Белл Лаборатории |
| Диссертация | Как справиться с NP-сложными проблемами (1983) |
| Докторантура | Ричард М. Карп [1] |
Нарендра Кришна Кармаркар (родился около 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]
Награды [ править ]
- Ассоциация вычислительной техники наградила его престижной премией Парижа Канеллакиса в 2000 году за его работу над методами внутренней точки с полиномиальным временем для линейного программирования за «конкретные теоретические достижения, которые оказали значительное и очевидное влияние на практику вычислений».
- Премия к 100-летию со дня рождения Шриниваса Рамануджана за 1999 год, врученная премьер-министром Индии.
- Премия выдающемуся выпускнику Индийского технологического института, Бомбей, 1996 г.
- Премия выдающемуся выпускнику факультета компьютерных наук и инженерии Калифорнийского университета в Беркли (1993 г.).
- Премия Фулкерсона в области дискретной математики, присуждаемая совместно Американским математическим обществом и Обществом математического программирования (1988).
- Сотрудник Bell Laboratories (с 1987 г.).
- Премия основателей Texas Instruments (1986).
- Международная премия молодым ученым Маркони (1985).
- Премия «Золотая тарелка» Американской академии достижений , вручаемая бывшим президентом США (1985). [9] [10]
- Премия Фредерика В. Ланчестера Американского общества исследования операций за лучший опубликованный вклад в исследование операций (1984).
- Золотая медаль президента Индии, ИИТ Бомбей (1978).
Ссылки [ править ]
- ^ Нарендра Кармаркар в проекте «Математическая генеалогия» .
- ^ Томсон ИСИ. «Кармаркар, Нарендра К., высоко цитируемые исследователи ISI» . Архивировано из оригинала 23 марта 2006 года . Проверено 20 июня 2009 г.
- ^ «Восемьдесят пятое ежегодное открытие» (PDF) . Калифорнийский технологический институт. 8 июня 1979 г. с. 13.
- ^ Нарендра Кармаркар в проекте «Математическая генеалогия»
- ^ Кармаркар, Нарендра (1991). «Новая параллельная архитектура для вычислений с разреженной матрицей, основанная на конечной проективной геометрии» . Материалы конференции ACM/IEEE 1991 года по суперкомпьютерам – Supercomputing '91 . стр. 358–369. дои : 10.1145/125826.126029 . ISBN 0897914597 . S2CID 6665759 .
- ^ Кармаркар, Н.К., Рамакришнан, К.Г. «Результаты вычислений алгоритма внутренней точки для крупномасштабного линейного программирования». Математическое программирование. 52: 555–586 (1991).
- ^ Амрутер, Б.С., Джоши, Р., Кармаркар, Н.К. «Архитектура проективной геометрии для научных вычислений». Материалы международной конференции по матричным процессорам для конкретных приложений, Компьютерное общество IEEE, стр. 6480 (1992).
- ^ Кармаркар, Н.К. «Новая параллельная архитектура для научных вычислений, основанная на конечной проективной геометрии». Труды по математическому программированию, современное состояние, с. 136148 (1994).
- ^ «Обладатели Золотой пластины Американской академии достижений» . www.achievement.org . Американская академия достижений .
- ^ «Вундеркинды общаются с правильными вещами» (PDF) . Новости Роки Маунтин. 30 июня 1985 г.
Внешние ссылки [ править ]
- Почетный выпускник ИИТ Бомбей 1996 г.
- Воспоминание: метод внутренней точки для линейного программирования IIT Bombay Heritage Fund
- Функция Кармаркара в Scilab
- 1957 рождений
- Живые люди
- Теоретики-компьютерщики
- Численный аналитик
- Индийские математики XX века
- Индийские математики XXI века
- Индийские ученые-компьютерщики
- Американские ученые-компьютерщики
- Ученые из Bell Labs
- Выпускники Калифорнийского университета в Беркли
- Выпускники ИИТ Бомбея
- Выпускники Калифорнийского технологического института
- Индийские эмигранты в США
- Американские исследователи операций
- Индийские исследователи операций
- Американские ученые индийского происхождения
- Люди из Гвалиора