AF: EAGER: Algorithms in Linear Algebra and Optimization

AF：EAGER：线性代数和优化算法

• 批准号: 1038578
• 负责人: Leonard Schulman
• 金额: $ 30万
• 依托单位: California Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-01-01 至 2013-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1038578&HistoricalAwards=false
• 关键词: AF; EAGER; Algorithms; Linear; Algebra

Dr. Schulman's research will tackle two problems of central importance in computer science: (1) Linear programming in strongly polynomial time and (2) Matrix pre-conditioning by diagonal balancing. A strongly polynomial-time algorithm for linear programming would be a breakthrough in complexity theory over the real field. It may lead to improved algorithms for harder types ofconvex programming (e.g., semidefinite) which (albeit in polynomial time) are currently prohibitively slow. Better algorithms for matrix preconditioning have the potentially to significantly improve linear algebra software packages.

Schulman博士的研究将解决计算机科学中两个重要的核心问题：（1）强多项式时间的线性规划和（2）对角平衡的矩阵预处理。 线性规划的强多项式时间算法是复杂性理论在真实的领域的一个突破。它可能会导致更难的凸规划类型的改进算法（例如，半定的），其（尽管在多项式时间内）目前非常慢。 更好的矩阵预处理算法有可能显着改善线性代数软件包。