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

University Of Florida, Gainesville FL

Investigators

Abstract

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.