Balancing the lifting values to improve the numerical stability of polyhedral homotopy continuation methods

Polyhedral homotopy continuation methods exploit the sparsity of polynomial systems so that the number of solution curves to reach all isolated soluti ons is optimal for generic systems. The numerical stability of tracing solu tion curves of polyhedral homotopies is mainly determined by the height of the powers of the continuation parameter. To reduce this height, we propose a procedure that operates as an intermediate stage between the mixed-volum e computation and the tracing of solution curves. This procedure computes n ew lifting values of the support of a polynomial system. These values prese rve the structure of the mixed-cell configuration obtained from the mixed-v olume computation and produce better-balanced powers of the continuation pa rameter in the polyhedral homotopies. (C) 2000 Elsevier Science Inc. All ri ghts reserved.