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

本研究的动机是对纳米级集成电路（ic）设计简化的可扩展方法的研究。这将通过扩展相关的谱图稀疏化框架来实现，以处理从一般非线性集成电路建模和仿真问题派生的类拉普拉斯矩阵。这项研究的结果可能被证明是开发高度可扩展的计算机辅助设计算法的关键，用于建模、仿真、设计、优化，以及验证未来的纳米级集成电路，这些集成电路很容易涉及数十亿个电路元件。开发的算法和方法将传播给领先的技术公司，其中可能包括半导体和电子设计自动化公司以及社交和网络公司，用于潜在的工业部署。谱图稀疏化的目的是寻找一个超稀疏子图（又称稀疏子图），使其拉普拉斯函数在特征值和特征向量方面能够很好地近似于原始子图。由于频谱相似的子图可以近似地保持距离，因此可以基于这些“频谱”稀疏网络开发更快的数值和基于图的算法。提出了一种基于谱摄动方法的近线性复杂性谱图稀疏化算法。所提出的方法具有高度可扩展性，因此可以立即用于开发近线性时间稀疏矩阵求解器和谱图（数据）划分（聚类）算法，用于一般的大型现实世界图问题。研究结果还可能影响与复杂系统/网络建模、数值线性代数、优化、机器学习、计算流体动力学、交通运输和社会网络等相关的广泛的计算机科学和工程问题。

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.