Narendra Karmarkar

Narendra Krishna Karmarkar
Geboren ca. 1956
Gwalior, Madhya Pradesh, Indien
Alma Mater IIT Bombay (B.Tech)
Caltech (FRAU.)
Universität von Kalifornien, Berkeley (Ph.D.)
Bekannt für Karmarkars Algorithmus
Wissenschaftliche Karriere
Felder Mathematik, Informatik
Institutionen Bell Labs
These Bewältigung mit NP-harten Problemen (1983)
Doktorand Richard M. Karp[1]

Narendra Krishna Karmarkar (geboren um 1956) ist ein indischer Mathematiker. Karmarkar entwickelte sich Karmarkars Algorithmus. Er ist als eine aufgeführt ISI stark zitierter Forscher.[2]

Er erfand einen der ersten nachweislich polynomialen Zeitalgorithmen für Lineares Programmieren, was im Allgemeinen als Innenpunktmethode bezeichnet wird. Der Algorithmus ist ein Eckpfeiler im Bereich der linearen Programmierung. Er veröffentlichte 1984 sein berühmtes Ergebnis, als er arbeitete Glockenlabors in New Jersey.

Biografie

Karmarkar erhielt seine B.Tech in Elektrotechnik von IIT Bombay 1978,, FRAU. von dem Kalifornisches Institut der Technologie 1979,,[3] und Ph.D. in Informatik von der Universität von Kalifornien, Berkeley im Jahr 1983 unter der Aufsicht von Richard M. Karp.[4] Karmarkar war Post-Doktoral-Forschungsergebnis bei IBM Research (1983), Mitglied des technischen Stabs und Stipendiatin am Forschungszentrum Mathematical Sciences, AT & T Bell Laboratories (1983-1998), Professor für Mathematik bei M.I.T. (1991), am Institut für Advantht Study , Princeton (1996) und Homi Bhabha -Vorsitzender Professor bei der Tata Institute of Fundamental Research in Mumbai Von 1998 bis 2005. Er war der wissenschaftliche Berater des Vorsitzenden der Tata Group (2006-2007). Während dieser Zeit wurde er von Ratan Tata finanziert, um den Supercomputer zu skalieren, den er bei TIFR entworfen und prototypisiert hatte. Das skalierte Modell stand zu dieser Zeit vor Supercomputer in Japan und erreichte das beste Ranglisten, das Indien jemals beim Supercomputing erreicht hat. Er war Gründungsdirektor von Computational Research Labs in Pune, wo die Skalierung von Arbeiten durchgeführt wurde. Er arbeitet weiterhin an seiner neuen Architektur für Supercomputing.

Arbeit

Karmarkars Algorithmus

Hauptartikel: Karmarkars Algorithmus

Karmarkars Algorithmus löst Lineares Programmieren Probleme in Polynomzeit. Diese Probleme werden durch eine Reihe linearer Einschränkungen dargestellt, an denen eine Reihe von Variablen beteiligt sind. Die vorherige Methode zur Lösung dieser Probleme bestand darin, das Problem als einen hohen dimensionalen Feststoff mit Scheitelpunkten zu betrachten, bei dem die Lösung durch Überqueren von Scheitelpunkt zu Scheitelpunkt angegangen wurde. Die neuartige Methode von Karmarkar nähert sich der Lösung, indem sie das oben genannte Feststoff in seiner Durchquerung durchschneidet. Folglich werden komplexe Optimierungsprobleme mit dem Karmarkar -Algorithmus viel schneller gelöst. Ein praktisches Beispiel für diese Effizienz ist die Lösung für ein komplexes Problem in der Optimierung des Kommunikationsnetzwerks, bei dem die Lösungszeit von Wochen auf Tage reduziert wurde. Sein Algorithmus ermöglicht somit schnellere Geschäfts- und Richtlinienentscheidungen. Karmarkars Algorithmus hat die Entwicklung von mehreren angeregt InnenpunktmethodenEinige davon werden in aktuellen Implementierungen linearer Programmlöser verwendet.

Galois Geometrie

Nach der Arbeit an der InnenpunktmethodeKarmarkar arbeitete an einem neuen die Architektur zum Supercomputingbasierend auf Konzepten von Endliche Geometrie, besonders projektive Geometrie Über endliche Felder.[5][6][7][8]

Aktuelle Untersuchungen

Derzeit synthetisiert er diese Konzepte mit einigen neuen Ideen, die er nennt Skulptur freier Speicherplatz (ein nichtlineares Analogon dessen, was im Volksmund beschrieben wurde als Falten Sie die perfekte Ecke).[9] Dieser Ansatz ermöglicht es ihm, diese Arbeit auf das physische Design von Maschinen auszudehnen. Er veröffentlicht jetzt Updates zu seinen jüngsten Arbeiten,[10] einschließlich einer erweiterten Zusammenfassung.[11] Dieses neue Paradigma wurde bei präsentiert IVNC, Polen am 16. Juli 2008,[12] und bei MIT am 25. Juli 2008.[13] Einige seiner jüngsten Arbeiten werden bei veröffentlicht IEEExplore.[14] Er hielt einen Vortrag über seine laufende Arbeit bei IIT Bombay Im September 2013.[15] Er hielt eine vierteilige Serie von Vorträgen bei FOCM 2014 (Grundlagen der Computermathematik)[16] Mit dem Titel "Auf dem Weg zu einer breiteren Sichtweise der Computertheorie". Der erste Teil dieser Vorlesungsreihe ist im Cornell Archive erhältlich.[17]

Auszeichnungen

Verweise

  1. ^ Narendra Karmarkar Bei der Mathematik Genealogie -Projekt.
  2. ^ Thomson Isi. "Karmarkar, Narendra K., ISI hoch zitierte Forscher". Archiviert von das Original am 23. März 2006. Abgerufen 20. Juni 2009.
  3. ^ "Achtundachtzig jährliches Beginn" (PDF). Kalifornisches Institut der Technologie. 8. Juni 1979. p. 13.
  4. ^ Narendra Karmarkar Bei der Mathematik Genealogie -Projekt
  5. ^ Karmarkar, Narendra (1991). "Eine neue parallele Architektur für die spärliche Matrixberechnung basierend auf endlichen projektiven Geometrien". Proceedings der ACM/IEEE -Konferenz von 1991 über Supercomputing - Supercomputing '91. Verfahren der ACM/IEEE -Konferenz von 1991 über Supercomputing. S. 358–369. doi:10.1145/125826.126029. ISBN 0897914597. S2CID 6665759.
  6. ^ Karmarkar, N. K., Ramakrishnan, K.G. Computerergebnisse eines Innenpunktalgorithmus für die lineare Programmierung in großem Maßstab., Mathematische Programmierung. 52: 555-586 (1991)
  7. ^ 28. Amrater, B. S., Joshi, R., Karmarkar, N. K., Eine projektive Geometriearchitektur für wissenschaftliche Berechnung, Proceedings of International Conference on Application Special Array Processors, IEEE Computer Society, S. 6480 (1992).
  8. ^ Karmarkar, N. K., eine neue parallele Architektur für wissenschaftliche Berechnungen, die auf endlichen projektiven Geometrien basiert, Verfahren der mathematischen Programmierung, Stand der Technik, S. 136148 (1994)
  9. ^ Angier, Natalie (3. Dezember 1984). "Die perfekte Ecke falten". Time Magazine. Archiviert von das Original am 4. Dezember 2008. Abgerufen 12. Juli 2008.
  10. ^ Karmarmar, Narendra (11. Juli 2008). "Narendra Karmarkars jüngste Forschung". punetech.com. Abgerufen 12. Juli 2008.
  11. ^ Karmarmar, Narendra (11. Juli 2008). "Massiv parallele Systeme und globale Optimierung" (PDF). Punetech.com Narendra Karmarkars jüngste Arbeit. Abgerufen 12. Juli 2008.
  12. ^ Karmarmar, Narendra (14. Juli 2008). "Vakuum -Nanoelektronikgeräte aus der Perspektive der Optimierungstheorie" (PDF). Punetech.com Narendra Karmarkars jüngste Arbeit. Abgerufen 14. Juli 2008.
  13. ^ Karmarkar, Narendra. "Seminar über massiv parallele Systeme und globale Optimierung". Berechnungsforschung in Boston. Abgerufen 12. Juli 2008.
  14. ^ http://ieeexplore.ieee.org/xpl/tocresult.jsp?isNumber=5166089&isyear=2009
  15. ^ Karmarkar, Narendra. "Erweiterter algorithmischer Ansatz zur Optimierung". Forschung in Indien. Abgerufen 26. September 2003.
  16. ^ "FOCM 2014".
  17. ^ Karmarkar, Narendra (2014). "Auf dem Weg zu einer breiteren Sichtweise der Theorie des Computers". Arxiv:1412.3335 [cs.na].
  18. ^ "Golden Plate Preisträger der American Academy of Achievement". www.achievement.org. Amerikanische Akademie der Leistung.
  19. ^ "Whiz Kids reiben Ellbogen mit richtigen Sachen" (PDF). Rocky Mountain News. 30. Juni 1985.

Externe Links