AF: Small: Algorithm Design Using Spectral Graph Theory

AF：小：使用谱图理论的算法设计

• 批准号: 1018463
• 负责人: Gary Miller
• 金额: $ 49.82万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1018463&HistoricalAwards=false
• 关键词: AF; Small; Algorithm; Design; Using

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.

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