Narendra Karmarkar - Narendra Karmarkar

Narendra Krishna Karmarkar
narozený15. listopadu 1955
Gwalior, Madhya Pradesh, Indie
Alma materIIT Bombay (B tech)
Caltech (SLEČNA.)
University of California, Berkeley (Ph.D.)
Známý jakoKarmarkarův algoritmus
Vědecká kariéra
PoleMatematika, Počítačová věda
InstituceBell Labs
TezeŘešení NP-těžkých problémů (1983)
Doktorský poradceRichard M. Karp[1]

Narendra Krishna Karmarkar (narozen 1955) je indický matematik. Karmarkar vyvinut Karmarkarův algoritmus. Je uveden jako ISI vysoce citovaný výzkumník.[2]

Vynalezl jeden z prvních prokazatelně polynomiálních časových algoritmů pro lineární programování, který se obecně označuje jako metoda vnitřního bodu. Algoritmus je základním kamenem v oblasti lineárního programování. Svůj slavný výsledek zveřejnil v roce 1984, když pracoval pro Bell Laboratories v New Jersey.

Životopis

Karmarkar přijal jeho B tech v elektrotechnice od IIT Bombay v roce 1978, SLEČNA. z Kalifornský technologický institut v roce 1979,[3] a Ph.D. v informatice z University of California, Berkeley v roce 1983 pod dohledem Richard M. Karp.[4]Karmarkar byl postdoktorandským výzkumným pracovníkem ve společnosti IBM research (1983), členem technického týmu a pracovníkem ve Výzkumném centru pro matematické vědy, AT&T Bell Laboratories (1983-1998), profesorem matematiky na MIT (1991), na Institutu pro pokročilé studium , Princeton (1996), a profesor Homi Bhabha na Tata Institute of Fundamental Research v Bombaj od roku 1998 do roku 2005. Společnost Karmarkar byla financována společností Ratan Tata za účelem vytvoření laboratoří pro výpočetní výzkum v Pune. Pro tento tým vytvořil tým 50 a více výzkumníků Phd. Byl vědeckým poradcem předsedy skupiny TATA (2006-2007). V současné době pracuje na nové architektuře superpočítačů.

Práce

Karmarkarův algoritmus

Hlavní článek: Karmarkarův algoritmus

Karmarkarův algoritmus řeší lineární programování problémy v polynomiální čas. Tyto problémy představuje řada lineárních omezení zahrnujících řadu proměnných. Předchozí metoda řešení těchto problémů spočívala v tom, že jsme problém považovali za vysoce dimenzionální těleso s vrcholy, kde k řešení bylo přistupováno procházením od vrcholu k vrcholu. Karmarkarova nová metoda přistupuje k řešení proříznutím výše uvedeného tělesa v jeho průchodu. V důsledku toho jsou složité optimalizační problémy řešeny mnohem rychleji pomocí Karmarkarova algoritmu. Praktickým příkladem této efektivity je řešení komplexního problému v optimalizaci komunikační sítě, kde byla doba řešení zkrácena z týdnů na dny. Jeho algoritmus tak umožňuje rychlejší obchodní a politická rozhodnutí. Karmarkarův algoritmus stimuloval vývoj několika vnitřní bodové metody, z nichž některé se používají v současných implementacích řešičů lineárních programů.

Galoisova geometrie

Po práci na Metoda vnitřního bodu, Karmarkar pracoval na novém architektura pro superpočítač, na základě konceptů z konečná geometrie, zvláště projektivní geometrie přes konečná pole.[5][6][7][8]

Současná vyšetřování

V současné době syntetizuje tyto koncepty s novými nápady, které nazývá vytvarování volného prostoru (nelineární analog toho, co bylo populárně popsáno jako skládání dokonalého rohu).[9] Tento přístup mu umožňuje rozšířit tuto práci na fyzický návrh strojů. Nyní publikuje novinky o své nedávné práci,[10] včetně rozšířeného abstraktu.[11] Toto nové paradigma bylo představeno na IVNC, Polsko dne 16. července 2008,[12] a v MIT dne 25. července 2008.[13] Některé z jeho nedávných prací jsou publikovány na tj. prozkoumat.[14] Přednesl přednášku o tom, jak chodí do práce IIT Bombay v září 2013.[15] Uskutečnil čtyřdílnou sérii přednášek na FOCM 2014 (Foundations of Computational Mathematics)[16] s názvem „Směrem k širšímu pohledu na teorii práce s počítačem“. První část této přednáškové řady je k dispozici v archivu Cornell.[17]


Ocenění

  • The Sdružení pro výpočetní techniku mu udělil prestižní ocenění Paris Kanellakis Award v roce 2000 za práci na metodách polynomiálního vnitřního bodu času pro lineární programování pro „konkrétní teoretické úspěchy, které měly významný a prokazatelný vliv na praxi výpočtu“.

Reference

  1. ^ Narendra Karmarkar na Matematický genealogický projekt.
  2. ^ Thomson ISI. „Karmarkar, Narendra K., vysoce citovaní vědci z ISI“. Archivovány od originál dne 23. března 2006. Citováno 20. června 2009.
  3. ^ „Osmdesáté páté roční zahájení“ (PDF). Kalifornský technologický institut. 8. června 1979. s. 13.
  4. ^ Narendra Karmarkar na Matematický genealogický projekt
  5. ^ Karmarkar, Narendra. „Nová paralelní architektura pro výpočet řídké matice na základě konečných projektivních geometrií“. Sborník konference ACM / IEEE z roku 1991 o superpočítači.
  6. ^ Karmarkar, N. K., Ramakrishnan, K.G. Výpočtové výsledky algoritmu vnitřního bodu pro lineární programování ve velkém měřítku., Matematické programování. 52: 555-586 (1991)
  7. ^ 28. Amruter, B. S., Joshi, R., Karmarkar, N. K., A Projektive Geometry Architecture for Scientific Computation, Proceedings of International Conference on Application Specific Array Processors, IEEE Computer Society, pp 6480 (1992).
  8. ^ Karmarkar, N. K., Nová paralelní architektura pro vědecké výpočty založené na konečných projektivních geometriích, Proceeding of Mathematical Programming, State of the Art, str. 136148 (1994)
  9. ^ Angier, Natalie (3. prosince 1984). „Skládání dokonalého rohu“. Časopis Time. Citováno 12. července 2008.
  10. ^ Karmarmar, Narendra (11. července 2008). „Nedávný výzkum Narendry Karmarkarové“. punetech.com. Citováno 12. července 2008.
  11. ^ Karmarmar, Narendra (11. července 2008). „Masivně paralelní systémy a globální optimalizace“ (PDF). punetech.com Nedávná práce Narendry Karmarkarové. Citováno 12. července 2008.
  12. ^ Karmarmar, Narendra (14. července 2008). „Vakuová nanoelektronická zařízení z pohledu teorie optimalizace“ (PDF). punetech.com Nedávná práce Narendry Karmarkarové. Citováno 14. července 2008.
  13. ^ Karmarkar, Narendra. „Seminář o masivně paralelních systémech a globální optimalizaci“. Výpočetní výzkum v Bostonu. Citováno 12. července 2008.
  14. ^ http://ieeexplore.ieee.org/xpl/tocresult.jsp?isnumber=5166089&isYear=2009
  15. ^ Karmarkar, Narendra. „Pokročilý algoritmický přístup k optimalizaci“. Výzkum v Indii. Citováno 26. září 2003.
  16. ^ https://www.fing.edu.uy/eventos/focm2014/
  17. ^ Karmarkar, Narendra (2014). "Směrem k širšímu pohledu na teorii práce s počítačem". arXiv:1412.3335 [cs.NA ].
  18. ^ „Ocenění Golden Plate of the American Academy of Achievement“. www.achievement.org. Americká akademie úspěchu.
  19. ^ „Svižné děti si třou lokty správnými věcmi“ (PDF). Rocky Mountain News. 30. června 1985.

externí odkazy