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

本研究的动机是调查可扩展的方法，设计简化的纳米级集成电路（IC）。这是通过扩展相关的谱图稀疏化框架来处理来自一般非线性IC建模和仿真问题的类拉普拉斯矩阵来实现的。这项研究的结果可能被证明是开发高度可扩展的计算机辅助设计算法的关键，这些算法用于建模、仿真、设计、优化以及未来纳米级IC的验证，这些纳米级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.