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

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

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.