AF: Small: Algorithm Design Using Spectral Graph Theory

谱图理论或代数图理论，也被称为，是对图的特征值和特征向量之间的关系及其组合性质的研究。该项目将专注于进一步加深我们对这种关系的理解，并利用这种理解来设计新的高效算法。包括在这个算法问题列表将是快速和可靠的线性系统求解和图分区。这些新算法将被用来寻找更好、更有效的算法来解决图像处理、医学成像、机器学习、线性和非线性优化等问题。使能技术将包括用于计算对称对角主导系统的极端特征值的线性功或O（m log m）功算法。该项目将使用图论的思想和技术，如图稀疏器、图切割和斯坦纳树。这些图论思想将与数值方法如Krylov子空间方法、内点法和预处理方法相结合来设计和分析这些新算法。在可能的情况下，基本算法的代码及其应用程序将通过网络提供给研究人员。谱图理论在计算机科学中的应用已经变得越来越重要和流行。一个值得注意的应用是b谷歌专利的对网页排序的算法。其他应用包括图像处理，特别是医学图像分割和去噪。该项目将结合数值分析和图论的最佳思想，进一步为这些问题领域设计更好的算法。目标是设计对运行时间和鲁棒性都有很强保证的算法，以便这些算法适用于关键应用，例如临床医生办公室的实时图像处理。传播不仅包括期刊和会议出版物，还包括一年两次的谱图理论课和在本科生和研究生算法课上的谱图理论讲座。

Spectral Graph Theory or Algebraic Graph Theory, as it is also known, is the study of the relationship between the eigenvalues and eigenvectors of graphs and their combinatorial properties. The project will focus on furthering our understanding of this relationship and exploit this understanding to design new and efficient algorithms. Included in this list of algorithmic problems will be fast and reliable linear system solvers and graph partitioners. These new algorithms will in turn be used to find better and more efficient algorithms for problems in image processing, medical imaging, machine learning, and linear and non-linear optimizations. Enabling technology will include linear-work or O(m log m)-work algorithms for computing extreme eigenvalues of symmetric diagonally dominate systems. The project will uses ideas and techniques from graph theory such as graph sparsifiers, graph cuts, and Steiner trees. These graph theoretic ideas will be combined with numerical methods such as Krylov subspaces methods, interior point methods, and preconditioning methods to design and analyze these new algorithms. When possible, code for the basic algorithms and their applications will be made available over the web to researchers.The use of Spectral Graph Theory in computer science applications has become increasingly important and popular. A notable application is the algorithm patented by Google to rank order web pages. Other applications include image processing, in particular, medical image segmentation and denoising. This project will further contribute to the design of better algorithms for these problem domains by combining the best ideas from numerical analysis and graph theory. The goal is to design algorithms with very strong guarantees for both run time and robustness so that these algorithms will be appropriate for critical applications such as real-time image processing in a clinician's office. Dissemination will not only include journal and conference publications, but also giving a biannual spectral graph theory class and spectral graph theory lectures in both undergraduate and graduate algorithm classes.