Parallel solution of Ultra Large-scale Linear Programming based on Continuum Computing

Ultra Large-scale linear programming refers to class of problems where number of linear inequality constraints grows exponentially w.r.t. the dimension of the space. "Continuum Computing" is a generalization of powerful interior point algorithms, and involves computing with transcendental functions, often in several complex variables.
    
There are many potential applications of this work to several practical problems-e.g. Explainable AI, Topology optimization for 3D printing, Optimal mask design for 7nm lithography etc. However, our focus in this seminar will be on core mathematical technique and its parallelization on contemporary parallel machines.  
 
We show that the "Potential function" involved in the algorithm for ultra large scale LP, and it's first two derivatives can be computed in polynomial time in continuum computing paradigm, in spite of the fact that the feasible region is given by exponential number of constraints, Actual numerical cross-simulation on standard computing model and machines involves approximate numerical computation of inverse Laplace transform. We also show how establishing non-satisfiability of boolean formula, which is known to require exponentially long proofs in the standard Turing machine model can be formulated and solved using ultra large-scale linear programming. It is also believed that this task cannot be done efficiently in quantum computing model. Earlier exposition of this work from FOCM can be found in Cornell Arxive 1412.3335.pdf.  


Biography:  Karmarkar received his B.Tech in Electrical Engineering from IIT Bombay in 1978, M.S. from the California Institute of Technology in 1979, and Ph.D. in Computer Science from the University of California, Berkeley in 1983 under the supervision of Richard M. Karp. 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 briefly the scientific advisor to the chairman of the TATA group. He is currently working on a new architecture for supercomputing.