Design and evaluation of homotopies for efficient and robust continuation

摘要

Homotopy continuation, in combination with a quasi-Newton method, can be an efficient and robust technique for solving large sparse systems of nonlinear equations. The homotopy itself is pivotal in determining the efficiency and robustness of the continuation algorithm. As the homotopy is defined implicitly by a nonlinear system of equations to which the analytical solution is by assumption unknown, many properties of the homotopy can only be studied using numerical methods. The properties of a given homotopy which have the greatest impact on the corresponding continuation algorithm are traceability and linear solver performance. Metrics are presented for the analysis and characterization of these properties. Several homotopies are presented and studied using these metrics in the context of a parallel implicit three-dimensional Newton-Krylov-Schur flow solver for computational fluid dynamics. Several geometries, grids, and flow types are investigated in the study. Additional studies include the impact of grid refinement and the application of a coordinate transformation to the homotopy as measured through the traceability and linear solver performance metrics.