# Department of Electrical Engineering IIT Bombay

### Site Tools

Action disabled: source

# H. Narayanan

### Research Interests

• Building large scale circuit simulators
• Combinatorial optimization including submodular function theory
• Large scale system partitioning.

### Courses Offered

• B.Tech. and Ph.D. from IIT Bombay.

### Work Experience

• Been a faculty member with the Electrical Engineering Department at IIT Bombay since 1974.
• He was a visiting faculty with the EECS Department at UC Berkeley, Berkeley, California during 1983-1985.
• During the period 2000-2003, he was Head of the Department of Electrical Engineering at IIT Bombay.
• During the period 1998-2006, he was convener, KVPY (Engg stream).

### Other Information

• His primary interests are in the area of Electrical Network Analysis - particularly in the use of topological methods for the efficient analysis of networks. He has supervised the building of the general purpose circuit simulator BITSIM, which uses such methods. BITSIM permits the option of using the Conjugate gradient method for solution of the linear equations which arise during circuit simulation. He is also interested in VLSI optimization problems such as partitioning where he applies the theory of submodular functions to produce efficient partitioners. He has participated in the building of VLSI circuit partitioners (related to realization through FPGAs) for industries in the US and in Japan. He is the author of the monograph, Submodular Functions and Electrical Networks (North Holland, 1997).

### Contact Information

Department of Electrical Engineering
IIT Bombay, Powai
Mumbai 400 076, India
Email : hn[AT]ee.iitb.ac.in
Phone (Internal(O)) : (0091 22) - 2576 7401
Phone (Internal(R)) : 8431
Office room no: 8431
Fax: (0091 22) - 25723707
Personal Homepage

### List of Publications

##### Journal Publications
1. (Only representative publications have been included).

In circuits the theme is essentially Network Theory Without Devices (NTWD). Also included are applications of Implicit Duality Theorem (IDT). In submodular functions the papers are essentially those related to Principal Partition and Principal Lattice of Partitions.

1. H. Narayanan and M.N. Vartak, An elementary approach to the principal partition of a matroid, Transactions of the Institute of Electronics and Communication Engineers of Japan E64 (1981) 227-234.
2. H. Narayanan, On the equivalence of Minty's painting theorem and Tellegen's theorem, International Journal of Circuit Theory and its Applications 13 (1985) 353-357 (NTWD)
3. H. Narayanan, On the decomposition of vector spaces, Linear algebra and its applications 76 (1986) 61-98 (NTWD) (IDT)
4. H. Narayanan, A unified construction of adjoint systems and networks, International Journal of Circuit Theory and its Applications 14 (1986) 263-276 (IDT)
5. H. Narayanan, Topological transformations of electrical networks, International Journal of Circuit Theory and its Applications 15 (1987) 211-233 (NTWD)(IDT)
6. H. Narayanan, On the minimum hybrid rank of a graph relative to a partition of its edges and its apppliction to electrical network analysis, International Journal of Circuit Theory and its Applications 18 (1990) 269-288 (NTWD)
7. H. Narayanan, The principal lattice of partitions of a submodular function, Linear Algebra and its Applications 144 (1991) 179-216
8. H. Narayanan, H. Saran and V.V. Vazirani, Randomized parallel algorithms for matroid union and intersection with applications to arborescences and edge disjoint spanning trees, SIAM Journal of Comput. 23 (1994) 387-397
9. H. Narayanan, A rounding technique for the polymatroid membership problem, Linear Algebra and its Applications 221 (1995) 41-57
10. H. Narayanan, Convolution and Dilworth truncation of submodular functions, Special Issue on Decision Sciences, Journal of Indian Institute of Science, Bangalore 75 (1995) 25-47
11. H. Narayanan, S. Roy and S. Patkar, Approximation algorithms for min-k-overlap using the PLP approach, Journal of Algorithms 21 (1996) 306-330
12. Sachin B. Patkar and H. Narayanan, A note on optimal covering augmentation for graphic polymatroids, Information Processing Letters, 79 (6) (2001) 285-290
13. H. Narayanan, Some applications of an Implicit Duality Theorem to connections of structures of special types including Dirac and reciprocal structures, Systems & Control Letters 45 (2) (2002) 87-95 (IDT)
14. H.K.Pillai and H.Narayanan, On duality of behavioural systems, Multidimensional Systems and Signal Processing, 49 (6) (2002) 357-383.
15. M.P.Desai,H. Narayanan,S.Patkar, The Realization of Finite State Machines by Decomposition and the Principal Lattice of Partitions of a Submodular Function, Special Issue on Submodular Functions, Discrete Applied Maths, 131, 2003, pp 299-310.
16. S.Patkar and H.Narayanan,Fast On-line/Off-line Algorithms for Optimal Reinforcement of a Network and its Connections with Principal Partition, Journal of Combinatorial Optimization 7 (2003) 45-68.
17. S.Patkar and H. Narayanan, Improving Graph Partitions using Submodular Functions, Special Issue on Submodular Functions, Discrete Applied Maths 131, 2003.
18. H. Narayanan, Minimization of Symmetric and General Submodular Functions, Special Issue on Submodular Functions, Discrete Applied Maths 131, 2003, pp 513-522.
19. H.Narayanan,Electrical Networks and Combinatorial Optimization,Annals of Indian National Academy of Engineering,1,(2004) 96-102.
20. H.Narayanan, Mathematical Programming and Electrical Networks, in{\it Operations Research with Economic and Industrial Applications: Emerging Trends edited by S.R. Mohan and S.K. Neogy, Anamaya Publishers, New Delhi 2004}.
21. H.Narayanan, On set functions that can be extended to convex functionals, {\it Linear Algebra and its Applications} {\bf 402} (2005) 74-100.
22. S.Fujishige and H.Narayanan, “Polyhedrally tight set functions and convexity”, Pacific Journal of Optimization {\bf 4} (2008) 139-151.
23. H. Narayanan: “Submodular Functions and Electrical Networks”, (2009) revised 2nd edition at

http://www.ee.iitb.ac.in/~hn/book/ (1st edition {\it Annals of Discrete Mathematics} {\bf 54}North Holland

 (London, New York, Amsterdam)
now also available online).
##### Conference Publications

(Only representative publications have been included). The first paper is included because the general purpose circuit simulator BITSIM ( built at VLSI Design centre, IIT Bombay in 1992) which used efficient, sparse hybrid equation formulation, was based on it. The remaining are largely on partitioning, dc-analysis and applications. The theory papers are based on Principal Lattice of Partitions and Principal Partition of a submodular function.

1. H. Narayanan, A theorem on graphs and its application to network analysis, Proceedings of IEEE International Symposium on Circuits and Systems (1979) 1008-1011
2. S. Roy and H. Narayanan, A new approach to the problem of PLA partitioning using the theory of the principal lattice of partitions of a submodular function, Proceedings of the Fourth Annual ASIC Conference and Exhibit (Rochester, 1991)
3. S. Patkar and H. Narayanan, Fast algorithm for the principal partition of a graph, Proceedings of Eleventh Annual Symposium on Foundations of Software Technology and Theoretical Computer Science (FSTTCS-11) LNCS-560 (1991) 288-306
4. H. Narayanan, S. Roy and S. Patkar, Min k-cut and the principal partition of a graph, Proceedings of Second National Seminar on Theoretical Computer Science (India, 1992)
5. V.S. Ovalekar and H. Narayanan, Fast loop matrix generation for hybrid analysis and a comparison of the sparsity of the loop impedance and MNA impedance submatrices, Proceedings of IEEE International Symposium on Circuits and Systems (1992)
6. S. Patkar and H. Narayanan, Principal lattice of partitions of submodular functions on graphs: Fast algorithm for principal partition and generic rigidity, Proceedings of the Third Annual International Symposium on Algorithms and Computation (Nagoya, Japan 1992)
7. S. Patkar and H. Narayanan, Fast sequential and randomized parallel algorithms for rigidity and approximate min-k-cut, Proceedings of Twelfth Annual Symposium on FSTTCS (New Delhi, 1992) (Springer Verlag, 1992)
8. S. Roy and H. Narayanan, Application of the principal partition and principal lattice of partitions of a graph to the problem of decomposition of a finite state machine, Proceedings of the IEEE International Symposium of Circuits and Systems (Chicago, Illinois, 1993)
9. H. Narayanan, S. Patkar and K.V. Subramanian, On the membership problem over polymatroid intersection, Proceedings of the Conference of the European Chapter on Combinatorial Optimization, (Milan, Italy 1994)
10. H. Narayanan, S. Roy and S. Patkar, Approximation algorithms for min-k-overlap using the PLP approach, Proceedings of the Conference on the Mathematical Foundations of Computer Science (Bratislava, Czech Republic, 1994)
11. S.Patkar, S.Batterywala, M.Chandramouli and H.Narayanan, A New Partitioning Strategy Based on Supermodular Functions, Proceedings of 10th International Conference on VLSI Design, Hyderabad, India, (1997) 32-37
12. Shabbir H. Batterywala and H. Narayanan, Time Domain Method for Reduced Order Network Synthesis of Large RC Circuits, The proceedings of the 1998 IEEE International Symposium on Circuits and Systems, VI-82-VI-85, Monterey, California, USA, 1998
13. Shabbir H. Batterywala and H. Narayanan, Efficient DC analysis of RVJ circuits for moment and derivative computations of interconnect networks, Proceedings of 12th international conference in VLSI design, Jan. 1999, 169-174
14. H.Narayanan B.N.V.M. Gupta and M.P.Desai, A state assignment scheme targeting performance and area, Proceedings of 12th international conference in VLSI design, Jan. 1999, 378-383
15. R.Shelar, M.P.Desai and H.Narayanan, Decomposition of Finite State Machines for Area, Delay minimization, Proceedings of the 1999 IEEE International Conference on Computer Design, Austin, Texas, USA
16. Shabbir H. Batterywala and H. Narayanan, Spectral Approximation Method for Choosing `Relevant' Eigenvalues During Interconnect Analysis, Proceedings of the 3rd World Multiconference on Systemics, Cybernetics and Informatics & the 5th International Conference on Information Systems, Analysis and Synthesis, Orlando, USA, September 1999
17. H.Narayanan, On the Duality between Controllability and Observability in Behavioural Systems Theory, Proc. International Conference on Communications Control and Signal Proc. CCSP 2000, Bangalore, July 25-July 28,2000, 183-186
18. R. Shelar, H. Narayanan and M. P. Desai, Orthogonal Partitioning and Gated Clock Architecture for Low Power Realization of FSMs, Proceedings of the 13th Annual IEEE International ASIC/SOC Conference, 13-16 Sept. 2000, Washington, 266-270
19. Sachin B. Patkar, H. Narayanan, Fast Algorithm for Successive Reinforcement of a Network, Proceedings of FSTTCS2000, New Delhi, December 2000
20. H.Narayanan, Matroids representable over Modules, Electrical Network Topology and Behavioural Systems Theory, Research report of the EE Dept., IIT Bombay, May 2000 (postscript).
21. H.Narayanan, Polyhedrally tight functions and convexity, Invited Talk, ISMP2003, Aug.18-Aug.22, 2003, Copenhagen, Denmark.
22. H.Narayanan: Mathematical Programming and Electrical Networks, {\it Proceedings of the International Conference on Operations Research 2004}, January 8-10,2004, ISI Kolkata
23. H.Narayanan,Mathematical Programming and Resistor Transformer Diode Networks, ICECS 2004, Dec 13-15, Tel Aviv, Israel, 2004, 69-72
24. S.Fujishige and H.Narayanan, Polyhedrally tight set functions and Discrete Convexity, Kurims (Kyoto University Research Institute of Mathematical Sciences) preprint, September 2005.
25. Gaurav Trivedi, Madhav P. Desai and H. Narayanan, “Fast DC Analysis and its Application to Combinatorial Optimization Problems”, 19th International Conference on VLSI Design,2006,pp 695-700
26. Gaurav Trivedi, Madhav P. Desai and H. Narayanan, Parallelization of DC Analysis through Multiport Decomposition, 20th International Conference on VLSI Design,2007,pp
27. Gaurav Trivedi, Sumit Punglia and H. Narayanan, Application of DC Analyzer to combinatorial optimization problems,20th International Conference on VLSI Design,2007,pp
28. H. Narayanan, Mathematical Programming and Electrical Network Analysis II: Computational Linear Algebra through Network analysis, International Symposium on Mathematical Programming for Decision Making: Theory and Applications (ISMPDM07), ISI Delhi, January 10-11, 2007.
29. G.Trivedi and H.Narayanan, Application of Fast DC Analysis to Partitioning Hypergraphs,ISCAS 2007 pp 3407-3410.
30. V. Siva Sankar, H. Narayanan, and Sachin B. Patkar, “Exploiting Hybrid Analysis in Solving Electrical Networks ”, 22nd International Conference on VLSI Design,2009, pp 2061