SHF: Small: Scalable Spectral Sparsification of Graph Laplacians and Integrated Circuits

点击翻译按钮获取中文摘要

This research is motivated by investigations on scalable methods for design simplifications of nanoscale integrated circuits (ICs). This is to be achieved by extending the associated spectral graph sparsification framework to handle Laplacian-like matrices derived from general nonlinear IC modeling and simulation problems. The results from this research may prove to be key to the development of highly scalable computer-aided design algorithms for modeling, simulation, design, optimization, as well as verification of future nanoscale ICs that can easily involve multi-billions of circuit components. The algorithms and methodologies developed will be disseminated to leading technology companies that may include semiconductor and Electronic Design Automation companies as well as social and network companies, for potential industrial deployments. Spectral graph sparsification aims to find an ultra-sparse subgraph (a.k.a. sparsifier) such that its Laplacian can well approximate the original one in terms of its eigenvalues and eigenvectors. Since spectrally similar subgraphs can approximately preserve the distances, much faster numerical and graph-based algorithms can be developed based on these "spectrally" sparsified networks. A nearly-linear complexity spectral graph sparsification algorithm is to be developed based on a spectral perturbation approach. The proposed method is highly scalable and thus can be immediately leveraged for the development of nearly-linear time sparse matrix solvers and spectral graph (data) partitioning (clustering) algorithms for large real-world graph problems in general. The results of the research may also influence a broad range of computer science and engineering problems related to complex system/network modeling, numerical linear algebra, optimization, machine learning, computational fluid dynamics, transportation and social networks, etc.