Properties of nonlinear systems and convergence of the Newton-Raphson method in geometric constraint solving

The paper describes an application of a variant of the Newton-Raphson method to solution of geometric constraint problems. Sparsity and rank deficiency of the corresponding nonlinear systems are emphasized and statistical data are presented. Several ways of handling underdeterminancy and overdeterminancy in solving the Newton linear systems are considered. The behavior of Newton’s method is shown on some examples of nonlinear systems. Two algorithms for solving linear systems are proposed based on rank-revealing LU and QR factorizations. The paper is concluded with a numerical comparison of the proposed linear solvers.