MSPA-ENG: Scalable Sparse Matrix Algorithms and Software for Nonlinear Optimization

MSPA-ENG：用于非线性优化的可扩展稀疏矩阵算法和软件

• 批准号: 0620286
• 负责人: William Hager
• 金额: $ 46万
• 依托单位: University of Florida
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-08-01 至 2010-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0620286&HistoricalAwards=false
• 关键词: MSPA; ENG; Scalable; Sparse; Matrix

This project will develop algorithms, mathematics, and scalable parallel software for active set techniques in nonlinear optimization. The research will continue the development of robust, high-performance algorithms, including further applications of a new conjugate gradient method to nonlinear optimization. Techniques for modifying a Cholesky factorization after a small rank change will now be developed in the context of incomplete Cholesky preconditioners. Parallel implementations of both modification routines and factorization routines will formulated. The sequential subspace method for sphere constrained optimization will be developed into a general algorithm suitable, for example, for trust region methods in nonlinear optimization. An improved graph partitioning algorithm will be developed which uses an optimization algorithm to achieve high quality partitions and a multilevel strategy to achieve speed.Although the focus is nonlinear optimization, the algorithms which are developed will have broad impact in the many areas of computational science that require the solution of large, sparse linear systems. The algorithms for modifying a Cholesky factorization could be applied to preconditioners for iterative schemes used in primal-dual interior point methods in linear programming, to sensitivity analysis in linear programming, to least-squares problems in statistics, to the analysis of electrical circuits and power systems, to structural mechanics, to the analysis of the effects of boundary condition changes in partial differential equations, to domain decomposition methods, to boundary element methods, and to the simulation of a lightning flash. The graph partitioning algorithm could be used in circuit board and micro-chip design, in sparse matrix pivoting strategies, in parallel computing to balance processor loads and to minimize communication between processors, and in molecular dynamics simulations. To maximize the impact of the research, high-quality software will be developed and made widely available.

该项目将为非线性优化中的活动集技术开发算法、数学和可扩展的并行软件。 该研究将继续开发稳健的高性能算法，包括进一步将新的共轭梯度法应用于非线性优化。现在将在不完整的 Cholesky 预处理器的背景下开发在小等级变化后修改 Cholesky 分解的技术。 将制定修改例程和因式分解例程的并行实现。用于球体约束优化的顺序子空间方法将发展成为适用于例如非线性优化中的信赖域方法的通用算法。将开发一种改进的图分区算法，该算法使用优化算法来实现高质量分区，并使用多级策略来实现速度。虽然重点是非线性优化，但所开发的算法将在计算科学的许多领域产生广泛的影响需要解决大型稀疏线性系统。修改 Cholesky 分解的算法可应用于线性规划中原对偶内点方法中使用的迭代方案的预处理器、线性规划中的灵敏度分析、统计学中的最小二乘问题、电路和功率分析系统、结构力学、偏微分方程中边界条件变化的影响分析、域分解方法、边界元方法以及闪电模拟。图分区算法可用于电路板和微芯片设计、稀疏矩阵旋转策略、并行计算以平衡处理器负载并最小化处理器之间的通信以及分子动力学模拟。 为了最大限度地发挥研究的影响，将开发高质量的软件并广泛使用。