Analysis of normal-form algorithms for solving systems of polynomial equations
Parkinson, Suzanna 1Ringer, Hayden 2Wall, Kate 3Parkinson, Erik 4Erekson, Lukas 3Christensen, Daniel 3Jarvis, Tyler J.3
扫码查看
点击上方二维码区域，可以放大扫码查看
作者信息
1. Univ Chicago
2. Virginia Tech
3. Brigham Young Univ
4. Emergent Trading
折叠
Abstract
We examine several of the normal-form multivariate polynomial rootfinding methods of Telen, Mourrain, and Van Barel and some variants of those methods. We analyze the performance of these variants in terms of their asymptotic temporal complexity as well as speed and accuracy on a wide range of numerical experiments. All variants of the algorithm are problematic for systems in which many roots are very close together. We analyze the performance on one such system in detail, namely the "devastating example "that Noferini and Townsend used to demonstrate instability of resultant-based methods. We demonstrate that the problems with the devastating example arise from having a large number of roots very close to each other. We also show that a small number of clustered roots does not cause numerical problems for these methods. We conjecture that the clustering of many roots is the primary source of problematic examples. (C) 2022 Elsevier B.V. All rights reserved.
Key words
Polynomial systems/Macaulay matrix/Numerical linear algebra/Moller-Stetter matrices/Normal forms
NSTL
Elsevier