AF: Small: Algorithm Design Using Spectral Graph Theory

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

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.