Fast DC Analysis and Its Application to Combinatorial Optimization Problems

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Gaurav Trivedi Articles by Madhav P. Desai Articles by H. Narayanan

19th International Conference on VLSI Design held jointly with 5th International Conference on Embedded Systems Design (VLSID'06)

Hyderabad, India

January 03-January 07

ISBN: 0-7695-2502-4

	ASCII Text	x
	Gaurav Trivedi, Madhav P. Desai, H. Narayanan, "Fast DC Analysis and Its Application to Combinatorial Optimization Problems," VLSI Design, International Conference on, pp. 695-700, 19th International Conference on VLSI Design held jointly with 5th International Conference on Embedded Systems Design (VLSID'06), 2006.

	BibTex	x
	@article{ 10.1109/VLSID.2006.89, author = {Gaurav Trivedi and Madhav P. Desai and H. Narayanan}, title = {Fast DC Analysis and Its Application to Combinatorial Optimization Problems}, journal ={VLSI Design, International Conference on}, volume = {0}, year = {2006}, issn = {1063-9667}, pages = {695-700}, doi = {http://doi.ieeecomputersociety.org/10.1109/VLSID.2006.89}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - VLSI Design, International Conference on TI - Fast DC Analysis and Its Application to Combinatorial Optimization Problems SN - 1063-9667 SP695 EP700 A1 - Gaurav Trivedi, A1 - Madhav P. Desai, A1 - H. Narayanan, PY - 2006 KW - null VL - 0 JA - VLSI Design, International Conference on ER -

Gaurav Trivedi, Indian Institute of Technology - Bombay

Madhav P. Desai, Indian Institute of Technology - Bombay

H. Narayanan, Indian Institute of Technology - Bombay

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/VLSID.2006.89

Many combinatorial optimization problems such as the min cost flow problem are equivalent to the solution of appropriate DC circuits made up of positive resistors, voltage sources, current sources and ideal diodes. Simulating the DC circuit is an alternative approach to the approximate solution of such problems. However, conventional simulators such as SPICE are too slow for this purpose. This paper describes the structure and performance of a fast DC Analyzer built at EE Department, IIT Bombay specifically for solving large circuits consisting of positive resistors, voltage sources, current sources and diodes. Using the simulator, we have analyzed circuits composed of diodes, positive resistors, current and voltage sources of size upto 700,000 nodes and 1.2 million edges on a 3.0 GHz, 1 GB RAM, PIV processor in at most 1.2 Hrs. We also report a comparative study of the performance of our DC analyzer with that of fastest commercial simulator.

Citation:

Gaurav Trivedi, Madhav P. Desai, H. Narayanan, "Fast DC Analysis and Its Application to Combinatorial Optimization Problems," vlsid, pp.695-700, 19th International Conference on VLSI Design held jointly with 5th International Conference on Embedded Systems Design (VLSID'06), 2006

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.