Search

In an earlier article ( Bostan et al., 2017 ), with Carlos D'Andrea, we described explicit expressions for the coefficients of the order-d polynomial subresultant of ( x − α ) m and ( x − β ) n with respect to Bernstein's set of polynomials { ( x − α ) j ( x − β ) d − j , 0 ≤ j ≤ d } , for 0 ≤ d min ⁡ { m , n } . The current paper further develops the study of these structured polynomials and shows that the coefficients of the subresultants of ( x − α ) m and ( x − β ) n with respect to the monomial basis can be computed in linear arithmetic complexity, which is faster than for arbitrary polynomials. The result is obtained as a consequence of the amazing though seemingly unnoticed fact that these subresultants are scalar multiples of Jacobi polynomials up to an affine change of variables.

In this paper we provide a new method to certify that a nearby polynomial system has a singular isolated root with a prescribed multiplicity structure. More precisely, given a polynomial system f $=(f\_1, \ldots, f\_N)\in C[x\_1, \ldots, x\_n]^N$, we present a Newton iteration on an extended deflated system that locally converges, under regularity conditions, to a small deformation of $f$ such that this deformed system has an exact singular root. The iteration simultaneously converges to the coordinates of the singular root and the coefficients of the so called inverse system that describes the multiplicity structure at the root. We use $$\alpha$$-theory test to certify the quadratic convergence, and togive bounds on the size of the deformation and on the approximation error. The approach relies on an analysis of the punctual Hilbert scheme, for which we provide a new description. We show in particular that some of its strata can be rationally parametrized and exploit these parametrizations in the certification. We show in numerical experimentation how the approximate inverse system can be computed as a starting point of the Newton iterations and the fast numerical convergence to the singular root with its multiplicity structure, certified by our criteria., Comment: International Symposium on Symbolic and Algebraic Computation, Jul 2020, Kalamata, France

This paper is concerned with certifying that a given point is near an exact root of an overdetermined or singular polynomial system with rational coefficients. The difficulty lies in the fact that consistency of overdetermined systems is not a continuous property. Our certification is based on hybrid symbolic-numeric methods to compute an exact rational univariate representation (RUR) of a component of the input system from approximate roots. For overdetermined polynomial systems with simple roots, we compute an initial RUR from approximate roots. The accuracy of the RUR is increased via Newton iterations until the exact RUR is found, which we certify using exact arithmetic. Since the RUR is well-constrained, we can use it to certify the given approximate roots using α -theory. To certify isolated singular roots, we use a determinantal form of the isosingular deflation , which adds new polynomials to the original system without introducing new variables. The resulting polynomial system is overdetermined, but the roots are now simple, thereby reducing the problem to the overdetermined case. We prove that our algorithms have complexity that are polynomial in the input plus the output size upon successful convergence, and we use worst case upper bounds for termination when our iteration does not converge to an exact RUR. Examples are included to demonstrate the approach.

We generalize Sylvester single sums to multisets and show that these sums compute subresultants of two univariate polynomials as a function of their roots independently of their multiplicity structure. This is the first closed formula for subresultants in terms of roots that works for arbitrary polynomials, previous efforts only handled special cases. Our extension involves in some cases confluent Schur polynomials and is obtained by using multivariate symmetric interpolation via an Exchange Lemma. Fil: D'Andrea, Carlos. Universidad de Barcelona; España Fil: Krick, Teresa Elena Genoveva. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas "Luis A. Santaló". Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigaciones Matemáticas "Luis A. Santaló"; Argentina Fil: Szanto, Agnes. North Carolina State University; Estados Unidos Fil: Valdettaro, Marcelo Alejandro. Universidad de Buenos Aires; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina

Triangular decomposition is a classic, widely used and well-developed way to represent algebraic varieties with many applications. In particular, there exist sharp degree bounds for a single triangular set in terms of intrinsic data of the variety it represents, and powerful randomized algorithms for computing triangular decompositions using Hensel lifting in the zero-dimensional case and for irreducible varieties. However, in the general case, most of the algorithms computing triangular decompositions produce embedded components, which makes it impossible to directly apply the intrinsic degree bounds. This, in turn, is an obstacle for efficiently applying Hensel lifting due to the higher degrees of the output polynomials and the lower probability of success. In this paper, we give an algorithm to compute an irredundant triangular decomposition of an arbitrary algebraic set $W$ defined by a set of polynomials in C[x_1, x_2, ..., x_n]. Using this irredundant triangular decomposition, we were able to give intrinsic degree bounds for the polynomials appearing in the triangular sets and apply Hensel lifting techniques. Our decomposition algorithm is randomized, and we analyze the probability of success.

We provide explicit formulae for the coefficients of the order-d polynomial subresultant of (x-\alpha)^m and (x-\beta)^n with respect to the set of Bernstein polynomials \{(x-\alpha)^j(x-\beta)^{d-j}, \, 0\le j\le d\}. They are given by hypergeometric expressions arising from determinants of binomial Hankel matrices., Comment: 18 pages, uses elsart. Revised version accepted for publication at Linear Algebra and its Applications

The theory of symmetric multivariate Lagrange interpolation is a beautiful but rather unknown tool that has many applications. Here we derive from it an Exchange Lemma that allows to explain in a simple and natural way the full description of the double sum expressions introduced by Sylvester in 1853 in terms of subresultants and their Bézout coefficients. Fil: Krick, Teresa Elena Genoveva. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigaciones Matemáticas ; Argentina Fil: Szanto, Agnes. North Carolina State University; Estados Unidos Fil: Valdettaro, Marcelo Alejandro. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina

This paper presents two new constructions related to singular solutions of polynomial systems. The first is a new deflation method for an isolated singular root. This construction uses a single linear differential form defined from the Jacobian matrix of the input, and defines the deflated system by applying this differential form to the original system. The advantages of this new deflation is that it does not introduce new variables and the increase in the number of equations is linear in each iteration instead of the quadratic increase of previous methods. The second construction gives the coefficients of the so-called inverse system or dual basis, which defines the multiplicity structure at the singular root. We present a system of equations in the original variables plus a relatively small number of new variables that completely deflates the root in one step. We show that the isolated simple solutions of this new system correspond to roots of the original system with given multiplicity structure up to a given order. Both constructions are "exact" in that they permit one to treat all conjugate roots simultaneously and can be used in certification procedures for singular roots and their multiplicity structure with respect to an exact rational polynomial system., Comment: arXiv admin note: substantial text overlap with arXiv:1501.05083

In 1853 J. Sylvester introduced a family of double sum expressions for two finite sets of indeterminates and showed that some members of the family are essentially the polynomial subresultants of the monic polynomials associated with these sets. In 2009, in a joint work with C. D'Andrea and H. Hong we gave the complete description of all the members of the family as expressions in the coefficients of these polynomials. In 2010, M.-F. Roy and A. Szpirglas presented a new and natural inductive proof for the cases considered by Sylvester. Here we show how induction also allows to obtain the full description of Sylvester's double-sums., 12 pages, uses elsart.cls and yjsco.sty

International audience; Let $f_1,\ldots,f_s \in \mathbb{K}[x_1,\ldots,x_m]$ be a system of polynomials generating a zero-dimensional ideal $\I$, where $\mathbb{K}$ is an arbitrary algebraically closed field. We study the computation of ``matrices of traces" for the factor algebra $\A := \CC[x_1, \ldots , x_m]/ \I$, i.e. matrices with entries which are trace functions of the roots of $\I$. Such matrices of traces in turn allow us to compute a system of multiplication matrices $\{M_{x_i}|i=1,\ldots,m\}$ of the radical $\sqrt{\I}$. We first propose a method using Macaulay type resultant matrices of $f_1,\ldots,f_s$ and a polynomial $J$ to compute moment matrices, and in particular matrices of traces for $\A$. Here $J$ is a polynomial generalizing the Jacobian. We prove bounds on the degrees needed for the Macaulay matrix in the case when $\I$ has finitely many projective roots in $\mathbb{P}^m_\CC$. We also extend previous results which work only for the case where $\A$ is Gorenstein to the non-Gorenstein case. The second proposed method uses Bezoutian matrices to compute matrices of traces of $\A$. Here we need the assumption that $s=m$ and $f_1,\ldots,f_m$ define an affine complete intersection. This second method also works if we have higher dimensional components at infinity. A new explicit description of the generators of $\sqrt{\I}$ are given in terms of Bezoutians.

Earlier results expressing multivariate subresultants as ratios of two subdeterminants of the Macaulay matrix are extended to Jouanolou matrices. These matrix constructions are generalizations of the classical Macaulay matrices and involve matrices of significantly smaller size. Equivalence of the various subresultant constructions is proved. The resulting subresultant method improves the efficiency of previous methods to compute the solution of over-determined polynomial systems.

We give the first known bound for orders of differentiations in differential Nullstellensatz for both partial and ordinary algebraic differential equations. This problem was previously addressed by A. Seidenberg but no complete solution was given. Our result is a complement to the corresponding result in algebraic geometry, which gives a bound on degrees of polynomial coefficients in effective Nullstellensatz., Comment: 25 pages; improved bound; simplified main argument; more detailed proofs

In 1853 Sylvester introduced a family of double-sum expressions for two finite sets of indeterminates and showed that some members of the family are essentially the polynomial subresultants of the monic polynomials associated with these sets. A question naturally arises: What are the other members of the family? This paper provides a complete answer to this question. The technique that we developed to answer the question turns out to be general enough to characterize all members of the family, providing a uniform method.

A general subresultant method is introduced to compute elements of a given ideal with few terms and bounded coefficients. This subresultant method is applied to solve over-determined polynomial systems by either finding a triangular representation of the solution set or by reducing the problem to eigenvalue computation. One of the ingredients of the subresultant method is the computation of a matrix that satisfies certain requirements, called the subresultant properties. Our general framework allows us to use matrices of significantly smaller size than previous methods. We prove that certain previously known matrix constructions, in particular, Macaulay’s, Chardin’s and Jouanolou’s resultant and subresultant matrices possess the subresultant properties. However, these results rely on some assumptions about the regularity of the over-determined system to be solved. The appendix, written by Marc Chardin, contains relevant results on the regularity of n homogeneous forms in n variables.

International audience; This paper presents two new constructions related to singular solutions of polynomial systems. The first is a new deflation method for an isolated singular root. This construc-tion uses a single linear differential form defined from the Jacobian matrix of the input, and defines the deflated system by applying this differential form to the original system. The advantages of this new deflation is that it does not introduce new variables and the increase in the number of equations is linear instead of the quadratic increase of previous methods. The second construction gives the coefficients of the so-called inverse system or dual basis, which defines the multiplicity structure at the singular root. We present a system of equations in the original variables plus a relatively small number of new vari-ables. We show that the roots of this new system include the original singular root but now with multiplicity one, and the new variables uniquely determine the multiplicity structure. Both constructions are "exact", meaning that they permit one to treat all conjugate roots simultaneously and can be used in certification procedures for singular roots and their multiplicity structure with respect to an exact rational polynomial system.

We present a solution for the classical univariate rational interpolation problem by means of (univariate) subresultants. In the case of Cauchy interpolation (interpolation without multiplicities), we give explicit formulas for the solution in terms of symmetric functions of the input data, generalizing the well-known formulas for Lagrange interpolation. In the case of the osculatory rational interpolation (interpolation with multiplicities), we give determinantal expressions in terms of the input data, making explicit some matrix formulations that can independently be derived from previous results by Beckermann and Labahn., Comment: 14 pages, revised version accepted for publication in the Journal of Symbolic Computation

International audience; We propose a generalization of the Weierstrass iteration for over-constrained systems of equations and we prove that the proposed method is the Gauss-Newton iteration to find the nearest system which has at least k common roots and which is obtained via a perturbation of prescribed structure. In the univariate case we show the connection of our method to the optimization problem formulated by Karmarkar and Lakshman for the nearest GCD. In the multivariate case we generalize the expressions of Karmarkar and Lakshman, and give explicitly several iteration functions to compute the optimum. The arithmetic complexity of the iterations is detailed.

In this paper, we study iterative methods on the coefficients of the rational univariate representation (RUR) of a given algebraic set, called a global Newton iterations. We compare two natural approaches to define locally quadratically convergent iterations: the first one involves Newton iteration applied to the approximate roots individually and then interpolation to find the RUR of these approximate roots; the second one considers the coefficients in the exact RUR as zeroes of a high dimensional map defined by polynomial reduction and applies Newton iteration on this map. We prove that over fields with a p-adic valuation these two approaches give the same iteration function. However, over fields equipped with the usual Archimedean absolute value they are not equivalent. In the latter case, we give explicitly the iteration function for both approaches. Finally, we analyze the parallel complexity of the different versions of the global Newton iteration, compare them, and demonstrate that they can be efficiently computed. The motivation for this study comes from the certification of approximate roots of overdetermined and singular polynomial systems via the recovery of an exact RUR from approximate numerical data.

In this paper we present an analogue of the lattice basis reduction algorithm of A.K. Lenstra, H.W. Lenstra and L. Lovasz for the case of an indefinite non-degenerate symmetric bilinear form. The algorithm produces a reduced basis with similar size properties as in the Euclidean case. As an application, we present an algorithm, which finds zero divisors in rings isomorphic to M2(Z) in polynomial time.

Preface List of contributors 1. The state of the art in Smale's 7th problem C. Beltran 2. The shape of data Gunnar Carlsson 3. Upwinding in finite element systems of differential forms S. H. Christiansen 4. On the complexity of computing quadrature formulas for SDEs S. Dereich, T. Muller-Gronbach and K. Ritter 5. The quantum walk of F. Riesz F. A. Grunbaum and L. Velazquez 6. Modulated Fourier expansions for continuous and discrete oscillatory systems E. Hairer and Ch. Lubich 7. The dual role of convection in 3D Navier-Stokes equations T. Y. Hou, Z. Shi and S. Wang 8. Algebraic and differential invariants Evelyne Hubert 9. Through the kaleidoscope: symmetries, groups and Chebyshev-approximations from a computational point of view H. Munthe-Kaas, M. Nome and B. N. Ryland 10. Sage: creating a viable free open source alternative to Magma, Maple, Mathematica and MATLAB W. Stein.

LetA be a finite dimensional associative algebra over the fieldF whereF is a finite (algebraic) extension of the function fieldF q(X 1,...,X m). Here Fq denotes the finite field ofq elements (q=pl for a primep). We address the problem of computing the Jacobson radical Rad (A) ofA and the problem of computing the minimal ideals of the radical-free part (Wedderburn decomposition). The algebraA is given by structure constants overF andF is given by structure constants overF q(X 1,...,X m). We give algorithms to find these structural components ofA. Our methods run in polynomial time ifm is constant, in particular in the casem=1. The radical algorithm is deterministic. Our method for computing the Wedderburn decomposition ofA uses randomization (for factoring univariate polynomials overF q).

In this tutorial we will focus on the solution of polynomial systems given with inexact coefficients using hybrid symbolic-numeric methods. In particular, we will concentrate on systems that are over-constrained or have roots with multiplicities. These systems are considered ill-posed or ill-conditioned by traditional numerical methods and they try to avoid them. On the other hand, traditional symbolic methods are not designed to handle inexactness. Ill-conditioned polynomial equation systems arise very frequently in many important applications areas such as geometric modeling, computer vision, fluid dynamics, etc.

International audience; Let $f_1,\ldots,f_s \in \mathbb{K}[x_1,\ldots,x_m]$ be a system of polynomials generating a zero-dimensional ideal $\I$, where $\mathbb{K}$ is an arbitrary algebraically closed field. Assume that the factor algebra $\A=\mathbb{K}[x_1,\ldots,x_m]/\I$ is Gorenstein and that we have a bound $\delta>0$ such that a basis for $\A$ can be computed from multiples of $f_1,\ldots,f_s$ of degrees at most $\delta$. We propose a method using Sylvester or Macaulay type resultant matrices of $f_1,\ldots,f_s$ and $J$, where $J$ is a polynomial of degree $\delta$ generalizing the Jacobian, to compute moment matrices, and in particular matrices of traces for $\A$. These matrices of traces in turn allow us to compute a system of multiplication matrices $\{M_{x_i}|i=1,\ldots,m\}$ of the radical $\sqrt{\I}$, following the approach in the previous work by Janovitz-Freireich, R\'{o}nyai and Szántó. Additionally, we give bounds for $\delta$ for the case when $\I$ has finitely many projective roots in $\mathbb{P}^m_\CC$. \end{abstract}

We present a method based on Dickson's lemma to compute the "approximate radical" of a zero dimensional ideal I in C[x1, . . ., xm] which has zero clusters: the approximate radical ideal has exactly one root in each cluster for sufficiently small clusters. Our method is "global" in the sense that it does not require any local approximation of the zero clusters: it reduces the problem to the computation of the numerical nullspace of the so called "matrix of traces", a matrix computable from the generating polynomials of I. To compute the numerical nullspace of the matrix of traces we propose to use Gaussian elimination with pivoting or singular value decomposition. We prove that if I has k distinct zero clusters each of radius at most epsilon in the max-norm, then k steps of Gauss elimination on the matrix of traces yields a submatrix with all entries asymptotically bounded by epsilon^2. We also show that the (k+1)-th singular value of the matrix of traces is O(epsilon^2). The resulting approximate radical has one root in each cluster with coordinates which are the arithmetic mean of the cluster, up to an error term asymptotically bounded by epsilon^2. In the univariate case our method gives an alternative to known approximate square-free factorization algorithms which is simpler and its accuracy is better understood., 31 pages, submitted for publication

In 1853 Sylvester stated and proved an elegant formula that expresses the polynomial subresultants in terms of the roots of the input polynomials. Sylvester's formula was also recently proved by Lascoux and Pragacz by using multi-Schur functions and divided differences. In this paper, we provide an elementary proof that uses only basic properties of matrix multiplication and Vandermonde determinants., Comment: 9 pages, no figures, simpler proof of the main results thanks to useful comments made by the referees. To appear in Journal of Symbolic Computation

We present a method based on Dickson's lemma to compute the "approximate radical" of a zero dimensional ideal I in C[x1, . . . , xm] which has zero clusters: the approximate radical ideal has exactly one root in each cluster for sufficiently small clusters. Our method is "global" in the sense that it does not require any local approximation of the zero clusters: it reduces the problem to the computation of the numerical nullspace of the so called "matrix of traces", a matrix computable from the generating polynomials of I. To compute the numerical nullspace of the matrix of traces we propose to use Gauss elimination with pivoting, and we prove that if I has k distinct zero clusters each of radius at most e in the ∞-norm, then k steps of Gauss elimination on the matrix of traces yields a submatrix with all entries asymptotically equal to e2. We also prove that the computed approximate radical has one root in each cluster with coordinates which are the arithmetic mean of the cluster, up to an error term asymptotically equal to e2. In the univariate case our method gives an alternative to known approximate square-free factorization algorithms which is simpler and its accuracy is better understood.

We give rational expressions for the subresultants of n+1 generic polynomials f_1,..., f_{n+1} in n variables as a function of the coordinates of the common roots of f_1,..., f_n and their evaluation in f_{n+1}. We present a simple technique to prove our results, giving new proofs and generalizing the classical Poisson product formula for the projective resultant, as well as the expressions of Hong for univariate subresultants in roots., 22 pages, no figures, elsart style, revised version of the paper presented in MEGA 2005, accepted for publication in Journal of Algebra

In this paper we give an elimination algorithm for differential difference polynomial systems. We use the framework of a generalization of Ore algebras, where the independent variables are non-commutative. We prove that for certain term orderings, Buchberger's algorithm applied to differential difference systems terminates and produces a Grobner basis. Therefore, differential-difference algebras provide a new instance of non-commutative graded rings which are effective Grobner structures.