Narendra Karmarkar
Encyclopedia
Narendra K. Karmarkar is an India
India
India , officially the Republic of India , is a country in South Asia. It is the seventh-largest country by geographical area, the second-most populous country with over 1.2 billion people, and the most populous democracy in the world...

n mathematician, renowned for developing Karmarkar's algorithm
Karmarkar's algorithm
Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time...

. He is listed as an ISI highly cited researcher
ISI highly cited researcher
ISI Highly Cited is a database of "highly cited researchers"—scientific researchers whose publications are most often cited in academic journals over the past decade, published by the Institute for Scientific Information...

.

Biography

Narendra Karmarkar was born in Gwalior to a Marathi family. Karmarkar received his B.Tech in Electrical Engineering from IIT Mumbai in 1978, M.S.
Master of Science
A Master of Science is a postgraduate academic master's degree awarded by universities in many countries. The degree is typically studied for in the sciences including the social sciences.-Brazil, Argentina and Uruguay:...

 from the California Institute of Technology
California Institute of Technology
The California Institute of Technology is a private research university located in Pasadena, California, United States. Caltech has six academic divisions with strong emphases on science and engineering...

 and Ph.D.
Ph.D.
A Ph.D. is a Doctor of Philosophy, an academic degree.Ph.D. may also refer to:* Ph.D. , a 1980s British group*Piled Higher and Deeper, a web comic strip*PhD: Phantasy Degree, a Korean comic series* PhD Docbook renderer, an XML renderer...

 in Computer Science from the University of California, Berkeley
University of California, Berkeley
The University of California, Berkeley , is a teaching and research university established in 1868 and located in Berkeley, California, USA...

.

He published his famous result in 1984 while he was working for Bell Laboratories in New Jersey
New Jersey
New Jersey is a state in the Northeastern and Middle Atlantic regions of the United States. , its population was 8,791,894. It is bordered on the north and east by the state of New York, on the southeast and south by the Atlantic Ocean, on the west by Pennsylvania and on the southwest by Delaware...

. Karmarkar was a professor at the Tata Institute of Fundamental Research
Tata Institute of Fundamental Research
The Tata Institute of Fundamental Research is a research institution in India dedicated to basic research in mathematics and the sciences. It is a Deemed University and works under the umbrella of the Department of Atomic Energy of the Government of India. It is located at Navy Nagar, Colaba, Mumbai...

 in Mumbai
Mumbai
Mumbai , formerly known as Bombay in English, is the capital of the Indian state of Maharashtra. It is the most populous city in India, and the fourth most populous city in the world, with a total metropolitan area population of approximately 20.5 million...

.

He is currently working on a new architecture for supercomputing. Some of the ideas are published at
Fab5 conference organised by MIT center for bits and atoms.

Karmarkar received a number of awards for his algorithm, among them:
  • Paris Kanellakis Award
    Paris Kanellakis Award
    The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery to honor specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing...

    , 2000 given by The Association for Computing Machinery
    Association for Computing Machinery
    The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...

    .
  • Distinguished Alumnus Award, Computer Science and Engineering, University of California, Berkeley (1993)
  • Ramanujan Prize for Computing, given by Asian Institute Informatics (1989)
  • Fulkerson Prize
    Fulkerson Prize
    The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society . Up to three awards of $1500 each are presented at each International Symposium of the MPS...

     in Discrete Mathematics given jointly by the American Mathematical Society
    American Mathematical Society
    The American Mathematical Society is an association of professional mathematicians dedicated to the interests of mathematical research and scholarship, which it does with various publications and conferences as well as annual monetary awards and prizes to mathematicians.The society is one of the...

     & Mathematical Programming Society
    Mathematical Programming Society
    Known as the Mathematical Programming Society until 2010, the Mathematical Optimization Society is an international association of researchers active in optimization...

     (1988)
  • Fellow of Bell Laboratories (1987- )
  • Texas Instruments Founders’ Prize (1986)
  • Marconi International Young Scientist Award (1985)
  • Frederick W. Lanchester Prize of the Operations Research Society of America for the Best Published Contributions to Operations Research (1984)
  • National Science Talent Award in Mathematics, India (1972, India)

Karmarkar's algorithm

Karmarkar's algorithm solves linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...

 problems in polynomial time. These problems are represented by "n" variables and "m" constraints. The previous method of solving these problems consisted of problem representation by an "x" sided solid with "y" 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 other interior point method
Interior point method
Interior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems.The interior point method was invented by John von Neumann...

s, some of which are used in current codes for solving linear programs.

Paris Kanellakis Award

The Association for Computing Machinery
Association for Computing Machinery
The Association for Computing Machinery is a learned society for computing. It was founded in 1947 as the world's first scientific and educational computing society. Its membership is more than 92,000 as of 2009...

 awarded him the prestigious Paris Kanellakis Award
Paris Kanellakis Award
The Paris Kanellakis Theory and Practice Award is granted yearly by the Association for Computing Machinery to honor specific theoretical accomplishments that have had a significant and demonstrable effect on the practice of computing...

 in 2000 for his work. The award citation reads:
For his theoretical work in devising an Interior Point method
Interior point method
Interior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems.The interior point method was invented by John von Neumann...

 for linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...

 that provably runs in polynomial time, and for his implementation work suggesting that Interior Point methods could be effective for linear programming in practice as well as theory. Together, these contributions inspired a renaissance in the theory and practice of linear programming, leading to orders of magnitude improvement in the effectiveness of widely-used commercial optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....

 codes.

Galois geometry

After working on the Interior Point Method
Interior point method
Interior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems.The interior point method was invented by John von Neumann...

, Karmarkar worked on a new architecture
Computer architecture
In computer science and engineering, computer architecture is the practical art of selecting and interconnecting hardware components to create computers that meet functional, performance and cost goals and the formal modelling of those systems....

 for supercomputing, based on concepts from finite
Finite geometry
A finite geometry is any geometric system that has only a finite number of points.Euclidean geometry, for example, is not finite, because a Euclidean line contains infinitely many points, in fact as many points as there are real numbers...

 geometry
Galois geometry
Galois geometry is the branch of finite geometry that is concerned with algebraic and analytic geometry over a finite field . More narrowly, a Galois geometry may be defined as a projective space over a finite field....

, especially projective geometry
Projective geometry
In mathematics, projective geometry is the study of geometric properties that are invariant under projective transformations. This means that, compared to elementary geometry, projective geometry has a different setting, projective space, and a selective set of basic geometric concepts...

 over finite fields.

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). This approach allows him to extend this work to the physical design of machines. He is now publishing updates on his recent work, including an extended abstract. This new paradigm was presented at IVNC, Poland on 16 July 2008, and at MIT on 25 July 2008.
Some of the recent work is published at
and Fab5 conference organised by MIT center for bits and atoms

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK