A robust approach for finding all well-separated solutions of sparse systems of nonlinear equations

作者：Baharev Ali^*; Domes Ferenc; Neumaier Arnold

来源：Numerical Algorithms, 2017, 76(1): 163-189.

DOI：10.1007/s11075-016-0249-x

• Decomposition methods
• Diakoptics
• Large-scale systems of equations
• Numerical instability
• Sparse matrices
• Tearing

Tearing is a long-established decomposition technique, widely adapted across many engineering fields. It reduces the task of solving a large and sparse non-linear system of equations to that of solving a sequence of low-dimensional ones. The most serious weakness of this approach is well-known: It may suffer from severe numerical instability. The present paper resolves this flaw for the first time. The new approach requires reasonable bound constraints on the variables. The worst-case time complexity of the algorithm is exponential in the size of the largest subproblem of the decomposed system. Although there is no theoretical guarantee that all solutions will be found in the general case, increasing the so-called sample size parameter of the method improves robustness. This is demonstrated on two particularly challenging problems. Our first example is the steady-state simulation a challenging distillation column, belonging to an infamous class of problems where tearing often fails due to numerical instability. This column has three solutions, one of which is missed using tearing, but even with problem-specific methods that are not based on tearing. The other example is the Stewart-Gough platform with 40 real solutions, an extensively studied benchmark in the field of numerical algebraic geometry. For both examples, all solutions are found with a fairly small amount of sampling.

• 出版日期2017-9