Truncated normal forms for solving polynomial systems: Generalized and efficient algorithms. (January 2021)

• Record Type: Journal Article
• Authors: Mourrain, Bernard; Telen, Simon; Van Barel, Marc
• Is Part Of: Journal of symbolic computation. Volume 102(2020)
• Page Start: 63
• Page End: 85
• Publication Date: 2021-01
• Subjects: Polynomial systems -- Truncated normal forms -- Computational algebraic geometry -- Orthogonal polynomials; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2019.10.009
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: We consider the problem of finding the isolated common roots of a set of polynomial functions defining a zero-dimensional ideal I in a ring R of polynomials over C . Normal form algorithms provide an algebraic approach to solve this problem. The framework presented in Telen et al. (2018) uses truncated normal forms (TNFs) to compute the algebra structure of R / I and the solutions of I . This framework allows for the use of much more general bases than the standard monomials for R / I . This is exploited in this paper to introduce the use of two special (non-monomial) types of basis functions with nice properties. This allows us, for instance, to adapt the basis functions to the expected location of the roots of I . We also propose algorithms for efficient computation of TNFs and a generalization of the construction of TNFs in the case of non-generic zero-dimensional systems. The potential of the TNF method and usefulness of the new results are exposed by many experiments.