Narendra Karmarkar - Revision history

imported>GreenC bot: Rescued 1 archive link. Wayback Medic 2.5

2021-07-21T10:10:39Z

Rescued 1 archive link. Wayback Medic 2.5

← Older revision		Revision as of 15:40, 21 July 2021
Line 43:		Line 43:

	====Current investigations====		====Current investigations====
	Currently, he is synthesizing these concepts with some new ideas he calls ''sculpturing free space'' (a non-linear analogue of what has popularly been described as ''folding the perfect corner'').<ref>{{cite web \|url=http://www.time.com/time/magazine/article/0,9171,923774,00.html \|title=Folding the Perfect Corner \|work=Time Magazine \|date=1984-12-03 \|access-date=2008-07-12 \|last=Angier \|first=Natalie}}</ref> This approach allows him to extend this work to the physical design of machines. He is now publishing updates on his recent work,<ref>{{cite web \|url=http://punetech.com/narendra-karmarkar \|title=Narendra Karmarkar's recent research \|work=punetech.com \| access-date=2008-07-12 \|date=2008-07-11 \|last=Karmarmar \|first=Narendra }}</ref> including an extended abstract.<ref>{{cite web \|url=http://punetech.com/narendra-karmarkar/extended_abstract.pdf \|title=Massively Parallel Systems and Global Optimization \|work=punetech.com Narendra Karmarkar's recent work\| access-date=2008-07-12 \|date=2008-07-11 \|last=Karmarmar \|first=Narendra }}</ref> This new paradigm was presented at [http://www.wemif.pwr.wroc.pl/ivnc08/ IVNC, Poland] on 16 July 2008,<ref>{{cite web \|url=http://punetech.com/narendra-karmarkar/OptimizationForIVNC08.pdf \|title=Vacuum nanoelectronics devices from the perspective of optimization theory \|work=punetech.com Narendra Karmarkar's recent work\| access-date=2008-07-14 \|date=2008-07-14 \|last=Karmarmar \|first=Narendra }}</ref> and at [[MIT]] on 25 July 2008.<ref>{{cite web \|url=http://www-math.mit.edu/crib/08/jul25.html \|title=Seminar on Massively Parallel Systems and Global Optimization \|work=Computation Research in Boston \|access-date=2008-07-12 \|last=Karmarkar \|first=Narendra}}</ref> Some of his recent work is published at [http://www.ieeexplore.com ieeexplore].<ref name="ieeexplore.ieee">http://ieeexplore.ieee.org/xpl/tocresult.jsp?isnumber=5166089&isYear=2009</ref> He delivered a lecture on his on going work at [[IIT Bombay]] in September 2013.<ref>{{cite web \|url=http://www.cse.iitb.ac.in/page20?talkdetails=771\|title=Advanced Algorithmic Approach to Optimization \|work=Research in India \|access-date=2003-09-26 \|last=Karmarkar \|first=Narendra}}</ref> He gave a four-part series of lectures at FOCM 2014 (Foundations of Computational Mathematics)<ref>https://www.fing.edu.uy/eventos/focm2014/</ref> titled "Towards a Broader View of Theory of Computing". First part of this lecture series is available at Cornell archive.<ref>{{Cite arXiv \|eprint = 1412.3335\|last1 = Karmarkar\|first1 = Narendra\|title = Towards a Broader View of Theory of Computing\|class = cs.NA\|year = 2014}}</ref>		Currently, he is synthesizing these concepts with some new ideas he calls ''sculpturing free space'' (a non-linear analogue of what has popularly been described as ''folding the perfect corner'').<ref>{{cite web \|url=http://www.time.com/time/magazine/article/0,9171,923774,00.html \|archive-url=https://web.archive.org/web/20081204201536/http://www.time.com/time/magazine/article/0,9171,923774,00.html \|url-status=dead \|archive-date=4 December 2008 \|title=Folding the Perfect Corner \|work=Time Magazine \|date=1984-12-03 \|access-date=2008-07-12 \|last=Angier \|first=Natalie}}</ref> This approach allows him to extend this work to the physical design of machines. He is now publishing updates on his recent work,<ref>{{cite web \|url=http://punetech.com/narendra-karmarkar \|title=Narendra Karmarkar's recent research \|work=punetech.com \| access-date=2008-07-12 \|date=2008-07-11 \|last=Karmarmar \|first=Narendra }}</ref> including an extended abstract.<ref>{{cite web \|url=http://punetech.com/narendra-karmarkar/extended_abstract.pdf \|title=Massively Parallel Systems and Global Optimization \|work=punetech.com Narendra Karmarkar's recent work\| access-date=2008-07-12 \|date=2008-07-11 \|last=Karmarmar \|first=Narendra }}</ref> This new paradigm was presented at [http://www.wemif.pwr.wroc.pl/ivnc08/ IVNC, Poland] on 16 July 2008,<ref>{{cite web \|url=http://punetech.com/narendra-karmarkar/OptimizationForIVNC08.pdf \|title=Vacuum nanoelectronics devices from the perspective of optimization theory \|work=punetech.com Narendra Karmarkar's recent work\| access-date=2008-07-14 \|date=2008-07-14 \|last=Karmarmar \|first=Narendra }}</ref> and at [[MIT]] on 25 July 2008.<ref>{{cite web \|url=http://www-math.mit.edu/crib/08/jul25.html \|title=Seminar on Massively Parallel Systems and Global Optimization \|work=Computation Research in Boston \|access-date=2008-07-12 \|last=Karmarkar \|first=Narendra}}</ref> Some of his recent work is published at [http://www.ieeexplore.com ieeexplore].<ref name="ieeexplore.ieee">http://ieeexplore.ieee.org/xpl/tocresult.jsp?isnumber=5166089&isYear=2009</ref> He delivered a lecture on his on going work at [[IIT Bombay]] in September 2013.<ref>{{cite web \|url=http://www.cse.iitb.ac.in/page20?talkdetails=771\|title=Advanced Algorithmic Approach to Optimization \|work=Research in India \|access-date=2003-09-26 \|last=Karmarkar \|first=Narendra}}</ref> He gave a four-part series of lectures at FOCM 2014 (Foundations of Computational Mathematics)<ref>https://www.fing.edu.uy/eventos/focm2014/</ref> titled "Towards a Broader View of Theory of Computing". First part of this lecture series is available at Cornell archive.<ref>{{Cite arXiv \|eprint = 1412.3335\|last1 = Karmarkar\|first1 = Narendra\|title = Towards a Broader View of Theory of Computing\|class = cs.NA\|year = 2014}}</ref>

	<br />		<br />

>Uranium Site: Reverted 1 edit by 2409:4065:E1D:E157:0:0:E9C9:5D01 (talk)

2021-05-29T06:21:38Z

Reverted 1 edit by 2409:4065:E1D:E157:0:0:E9C9:5D01 (talk)

New page

{{short description|Indian mathematician (born 1956)}}
{{Use dmy dates|date=February 2019}}
{{Use Indian English|date=February 2019}}
{{Infobox scientist
| name = Narendra Krishna Karmarkar
| image =
| birth_date = circa 1956
| birth_place = [[Gwalior]], [[Madhya Pradesh]], India
| workplaces = [[Bell Labs]]
| alma_mater = [[Indian Institute of Technology Bombay|IIT Bombay]] (B.Tech)<br />[[California Institute of Technology|Caltech]] (M.S.)<br />[[University of California, Berkeley]] (Ph.D.)
| thesis_title = Coping with NP-Hard Problems
| thesis_year = 1983
| doctoral_advisor = [[Richard M. Karp]]<ref name="mg">{{MathGenealogy|id=106239}}.</ref>
| known_for = [[Karmarkar's algorithm]]
| field = [[Mathematics]], [[Computing Science]]
}}
'''Narendra Krishna Karmarkar''' (born circa 1956) is an [[India]]n mathematician. Karmarkar developed [[Karmarkar's algorithm]]. He is listed as an [[ISI highly cited researcher]].<ref>{{Cite web
|last = Thomson ISI
|title = Karmarkar, Narendra K., ISI Highly Cited Researchers
|url = http://hcr3.isiknowledge.com/author.cgi?&link1=Browse&link2=Results&id=3416
|access-date = 2009-06-20
|url-status = dead
|archive-url = https://web.archive.org/web/20060323085057/http://hcr3.isiknowledge.com/author.cgi?&link1=Browse&link2=Results&id=3416
|archive-date = 2006-03-23
}}
</ref>

He invented one of the first provably polynomial time algorithms for [[linear programming]], which is generally referred to as an interior point method. The algorithm is a cornerstone in the field of Linear Programming. He published his famous result in 1984 while he was working for [[Bell Laboratories]] in [[New Jersey]].

==Biography==
Karmarkar received his [[B.Tech]] in Electrical Engineering from [[IIT Bombay]] in 1978, [[Master of Science|M.S.]] from the [[California Institute of Technology]] in 1979,<ref>{{cite web |url=http://caltechcampuspubs.library.caltech.edu/2515/1/June_8,_1979.pdf |title=Eighty-Fifth Annual Commencement |date=8 June 1979 |publisher=California Institute of Technology |page=13}}</ref> and [[Ph.D.]] in Computer Science from the [[University of California, Berkeley]] in 1983 under the supervision of [[Richard M. Karp]].<ref>{{mathgenealogy|id=106239}}</ref>
Karmarkar was a post-doctoral research fellow at IBM research(1983), Member of Technical Staff and fellow at Mathematical Sciences Research Center, AT&T Bell Laboratories(1983-1998), professor of mathematics at M.I.T.(1991), at Institute for Advanced study, Princeton(1996), and Homi Bhabha Chair Professor at the [[Tata Institute of Fundamental Research]] in [[Mumbai]] from 1998 to 2005. He was the scientific advisor to the chairman of the TATA group(2006-2007). During this time, he was funded by Ratan Tata to scale-up the supercomputer he had designed and prototyped at TIFR. The scaled up model ranked ahead of supercomputer in Japan at that time and achieved the best ranking India ever achieved in supercomputing. He was the founding director of Computational Research labs in Pune where the scaling up work was performed. He continues to work on his new architecture for supercomputing.

== Work ==

===Karmarkar's algorithm===
{{main|Karmarkar's algorithm}}

Karmarkar's algorithm solves [[linear programming]] problems in [[polynomial time]]. These problems are represented by a number of linear constraints involving a number of variables. The previous method of solving these problems consisted of considering the problem as a high dimensional solid with vertices, where the solution was approached by traversing from vertex to vertex. Karmarkar's novel method approaches the solution by cutting through the above solid in its traversal. Consequently, complex optimization problems are solved much faster using the Karmarkar algorithm. A practical example of this efficiency is the solution to a complex problem in communications network optimization where the solution time was reduced from weeks to days. His algorithm thus enables faster business and policy decisions. Karmarkar's algorithm has stimulated the development of several [[interior point method]]s, some of which are used in current implementations of linear program solvers.

====Galois geometry====
After working on the [[interior point method|Interior Point Method]], Karmarkar worked on a new [[computer architecture|architecture]] for [[supercomputing]], based on concepts from [[finite geometry]], especially [[projective geometry]] over [[finite fields]].<ref>{{cite web |url=http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=126029 |title=A new parallel architecture for sparse matrix computation based on finite projective geometries |work=Proceedings of the 1991 ACM/IEEE conference on Supercomputing |last=Karmarkar |first=Narendra}}</ref><ref>Karmarkar, N. K., Ramakrishnan, K.G. Computational results of an interior point algorithm for large scale linear programming., Mathematical Programming. 52: 555-586 (1991)</ref><ref>28. Amruter, B. S., Joshi, R., Karmarkar, N. K., A Projective Geometry Architecture for Scientific Computation, Proceedings of International Conference on Application Specific Array Processors, IEEE Computer Society, pp 6480 (1992).</ref><ref>Karmarkar, N. K., A New Parallel Architecture for Scientific Computation Based on Finite Projective Geometries, Proceeding of Mathematical Programming, State of the Art, pp. 136148 (1994)</ref>

====Current investigations====
Currently, he is synthesizing these concepts with some new ideas he calls ''sculpturing free space'' (a non-linear analogue of what has popularly been described as ''folding the perfect corner'').<ref>{{cite web |url=http://www.time.com/time/magazine/article/0,9171,923774,00.html |title=Folding the Perfect Corner |work=Time Magazine |date=1984-12-03 |access-date=2008-07-12 |last=Angier |first=Natalie}}</ref> This approach allows him to extend this work to the physical design of machines. He is now publishing updates on his recent work,<ref>{{cite web |url=http://punetech.com/narendra-karmarkar |title=Narendra Karmarkar's recent research |work=punetech.com | access-date=2008-07-12 |date=2008-07-11 |last=Karmarmar |first=Narendra }}</ref> including an extended abstract.<ref>{{cite web |url=http://punetech.com/narendra-karmarkar/extended_abstract.pdf |title=Massively Parallel Systems and Global Optimization |work=punetech.com Narendra Karmarkar's recent work| access-date=2008-07-12 |date=2008-07-11 |last=Karmarmar |first=Narendra }}</ref> This new paradigm was presented at [http://www.wemif.pwr.wroc.pl/ivnc08/ IVNC, Poland] on 16 July 2008,<ref>{{cite web |url=http://punetech.com/narendra-karmarkar/OptimizationForIVNC08.pdf |title=Vacuum nanoelectronics devices from the perspective of optimization theory |work=punetech.com Narendra Karmarkar's recent work| access-date=2008-07-14 |date=2008-07-14 |last=Karmarmar |first=Narendra }}</ref> and at [[MIT]] on 25 July 2008.<ref>{{cite web |url=http://www-math.mit.edu/crib/08/jul25.html |title=Seminar on Massively Parallel Systems and Global Optimization |work=Computation Research in Boston |access-date=2008-07-12 |last=Karmarkar |first=Narendra}}</ref> Some of his recent work is published at [http://www.ieeexplore.com ieeexplore].<ref name="ieeexplore.ieee">http://ieeexplore.ieee.org/xpl/tocresult.jsp?isnumber=5166089&isYear=2009</ref> He delivered a lecture on his on going work at [[IIT Bombay]] in September 2013.<ref>{{cite web |url=http://www.cse.iitb.ac.in/page20?talkdetails=771|title=Advanced Algorithmic Approach to Optimization |work=Research in India |access-date=2003-09-26 |last=Karmarkar |first=Narendra}}</ref> He gave a four-part series of lectures at FOCM 2014 (Foundations of Computational Mathematics)<ref>https://www.fing.edu.uy/eventos/focm2014/</ref> titled "Towards a Broader View of Theory of Computing". First part of this lecture series is available at Cornell archive.<ref>{{Cite arXiv |eprint = 1412.3335|last1 = Karmarkar|first1 = Narendra|title = Towards a Broader View of Theory of Computing|class = cs.NA|year = 2014}}</ref>

<br />

== Awards ==

* The [[Association for Computing Machinery]] awarded him the prestigious [[Paris Kanellakis Award]] in 2000 for his work on polynomial time interior point methods for linear programming for "specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing".

* Srinivasa Ramanujan Birth Centenary Award for 1999, presented by the Prime Minister of India.
* Distinguished Alumnus Award, Indian Institute of Technology, Bombay, 1996
* Distinguished Alumnus Award, Computer Science and Engineering, University of California, Berkeley (1993)
*[[Fulkerson Prize]] in Discrete Mathematics given jointly by the [[American Mathematical Society]] & [[Mathematical Programming Society]] (1988)
* Fellow of Bell Laboratories (1987– )
* Texas Instruments Founders' Prize (1986)
* Marconi International Young Scientist Award (1985)
* Golden Plate Award of the [[Academy of Achievement|American Academy of Achievement]], presented by former U.S. president (1985)<ref>{{cite web|title= Golden Plate Awardees of the American Academy of Achievement |website=www.achievement.org|publisher=[[American Academy of Achievement]]|url= https://achievement.org/our-history/golden-plate-awards/all-honorees/}}</ref><ref>{{cite web|title= Whiz kids rub elbows with right stuff|publisher= Rocky Mountain News| date= June 30, 1985 |url= https://achievement.org/wp-content/uploads/2020/11/RockyMountain19850630.pdf}}</ref>
*[https://web.archive.org/web/20060924005643/http://www.informs.org/article.php?id=962 Frederick W. Lanchester Prize] of the [[Operations Research Society of America]] for the Best Published Contributions to Operations Research (1984)
* President of India gold medal, I.I.T. Bombay (1978)

==References==
{{Reflist}}

==External links==
* [http://www.alumni.iitb.ac.in/details.asp?scn=18722 Distinguished Alumnus 1996]{{dead link|date=December 2017 |bot=InternetArchiveBot |fix-attempted=yes }} IIT Bombay
* [https://web.archive.org/web/20080820052613/http://www.iitbombay.org/misc/press/karmarkar.htm Flashback: An Interior Point Method for Linear Programming] IIT Bombay Heritage Fund
* [http://help.scilab.org/docs/5.5.1/en_US/karmarkar.html Karmarkar function] in [[Scilab]]

{{Kanellakis Award laureates}}
{{Authority control}}

{{DEFAULTSORT:Karmarkar, Narendra}}
[[Category:1957 births]]
[[Category:Living people]]
[[Category:Highly Cited Researchers]]
[[Category:Theoretical computer scientists]]
[[Category:Numerical analysts]]
[[Category:20th-century Indian mathematicians]]
[[Category:21st-century Indian mathematicians]]
[[Category:Indian computer scientists]]
[[Category:American computer scientists]] 
[[Category:Scientists at Bell Labs]]
[[Category:University of California, Berkeley alumni]]
[[Category:IIT Bombay alumni]]
[[Category:California Institute of Technology alumni]]
[[Category:Indian emigrants to the United States]]
[[Category:American operations researchers]]
[[Category:Indian operations researchers]]
[[Category:American academics of Indian descent]]
[[Category:People from Gwalior]]