Symbolic and numeric methods for exploiting structure in constructing resultant matrices (Q1600039)

The authors describe the construction of sparse resultant, or Newton, matrices to compute solutions of nonlinear systems. By exploiting the quasi-Toeplitz structure of the Newton matrix the time complexity of the problem is decreased by roughly one order of magnitude. Fast and numerically stable methods for determining the rank of a rectangular matrix, as well as exact polynomial arithmetic algorithms are used, under a particular model of sparseness, to provide for bounds, linear in the number of variables and number of non-zero terms. Examples analysed elsewhere are used to illustrate the approach.