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.

舒尔曼博士的研究将解决计算机科学中两个至关重要的问题：(1) 强多项式时间内的线性规划和 (2) 通过对角线平衡进行矩阵预处理。 用于线性规划的强多项式时间算法将是现实领域复杂性理论的突破。它可能会导致更难类型的凸规划（例如，半定）的算法得到改进，而目前这种算法（尽管在多项式时间内）速度慢得令人望而却步。 更好的矩阵预处理算法有可能显着改进线性代数软件包。