Polynomial interpolation in several variables,cubature formulae,and ideals[*]Supported by the National Science Foundation under Grant DMS-9802265.

We discuss polynomial interpolation in several variables from a polynomial ideal point of view. One of the results states that if I is a real polynomial ideal with real variety and if its codimension is equal to the cardinality of its variety, then for each monomial order there is a unique polynomial that interpolates on the points in the variety. The result is motivated by the problem of constructing cubature formulae, and it leads to a theorem on cubature formulae which can be considered an extension of Gaussian quadrature formulae to several variables. This revised version was published online in June 2006 with corrections to the Cover Date.     

The Neumann problem on ellipsoids

The Neumann problem on an ellipsoid in \(\mathbf {R}^n\) asks for a function harmonic inside the ellipsoid whose normal derivative is some specified function on the ellipsoid. We solve this problem when the specified function on the ellipsoid is a normalized polynomial (a polynomial divided by the norm of the normal vector arising from the definition of the ellipsoid). Specifically, we give a necessary and sufficient condition for a solution to exist, and we show that if a solution exists then it is a polynomial whose degree is at most the degree of the polynomial giving the specified function. Furthermore, we give an algorithm for computing this solution. We also solve the corresponding generalized Neumann problem and give an algorithm for computing its solution.     

A discrete adapted hierarchical basis solver for radial basis function interpolation

In this paper we develop a discrete Hierarchical Basis (HB) to efficiently solve the Radial Basis Function (RBF) interpolation problem with variable polynomial degree. The HB forms an orthogonal set and is adapted to the kernel seed function and the placement of the interpolation nodes. Moreover, this basis is orthogonal to a set of polynomials up to a given degree defined on the interpolating nodes. We are thus able to decouple the RBF interpolation problem for any degree of the polynomial interpolation and solve it in two steps: (1) The polynomial orthogonal RBF interpolation problem is efficiently solved in the transformed HB basis with a GMRES iteration and a diagonal (or block SSOR) preconditioner. (2) The residual is then projected onto an orthonormal polynomial basis. We apply our approach on several test cases to study its effectiveness.     

A Refined Schwarz Lemma for the Spectral Nevanlinna-Pick Problem

The spectral Nevanlinna–Pick problem asks for necessary and sufficient conditions for the existence of a holomorphic map from the unit disc to the set of $n\times n$ complex matrices with spectral radius less than 1, that interpolates given data. Some versions of the Schwarz lemma, obtained by Ransford and Nokrane, and by Bharali, provide necessary conditions. We prove a refined version of their results, which makes it possible to treat problems with more than two interpolation points.     

Gradient map of isoparametric polynomial and its application to Ginzburg-Landau system

In this note, we study properties of the gradient map of the isoparametric polynomial. For a given isoparametric hypersurface in sphere, we calculate explicitly the gradient map of its isoparametric polynomial which turns out many interesting phenomenons and applications. We find that it should map not only the focal submanifolds to focal submanifolds, isoparametric hypersurfaces to isoparametric hypersurfaces, but also map isoparametric hypersurfaces to focal submanifolds. In particular, it turns out to be a homogeneous polynomial automorphism on certain isoparametric hypersurface. As an immediate consequence, we get the Brouwer degree of the gradient map which was firstly obtained by Peng and Tang with moving frame method. Following Farina's construction, another immediate consequence is a counterexample of the Brézis question about the symmetry for the Ginzburg-Landau system in dimension 6, which gives a partial answer toward the Open problem 2 raised by Farina.     

Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations

Summary. By providing a matrix version of Koenig's theorem we reduce the problem of evaluating the coefficients of a monic factor r(z) of degree h of a power series f(z) to that of approximating the first h entries in the first column of the inverse of an Toeplitz matrix in block Hessenberg form for sufficiently large values of n. This matrix is reduced to a band matrix if f(z) is a polynomial. We prove that the factorization problem can be also reduced to solving a matrix equation for an matrix X, where is a matrix power series whose coefficients are Toeplitz matrices. The function is reduced to a matrix polynomial of degree 2 if f(z) is a polynomial of degreeN and . These reductions allow us to devise a suitable algorithm, based on cyclic reduction and on the concept of displacement rank, for generating a sequence of vectors that quadratically converges to the vector having as components the coefficients of the factor r(z). In the case of a polynomial f(z) of degree N, the cost of computing the entries of given is arithmetic operations, where is the cost of solving an Toeplitz-like system. In the case of analytic functions the cost depends on the numerical degree of the power series involved in the computation. From the numerical experiments performed with several test polynomials and power series, the algorithm has shown good numerical properties and promises to be a good candidate for implementing polynomial root-finders based on recursive splitting strategies. Applications to solving spectral factorization problems and Markov chains are also shown. Received September 9, 1998 / Revised version received November 14, 1999 / Published online February 5, 2001     

Quadrilateral finite elements of FVS type and class C^\rho

Summary. Let be some partition of a planar polygonal domain into quadrilaterals. Given a smooth function , we construct piecewise polynomial functions of degree for odd, and for even on a subtriangulation of . The latter is obtained by drawing diagonals in each , and is a composite quadrilateral finite element generalizing the classical cubic Fraeijs de Veubeke and Sander (or FVS) quadrilateral. The function interpolates the derivatives of up to order at the vertices of . Polynomial degrees obtained in this way are minimal in the family of interpolation schemes based on finite elements. Received April 30, 1992 / Revised version received June 3, 1994     

Behavioral Models for List Decoding

Recently it has been shown that list decoding of Reed-Solomon codes may be translated into a bivariate interpolation problem. The data consist of pairs in a finite field and the aim is to find a bivariate polynomial that interpolates the given pairs and is minimal with respect to some criterion. We present a systems theoretic approach to this interpolation problem. With the data points we associate a set of time series, also called trajectories. For this set of trajectories we construct the Most Powerful Unfalsified Model (MPUM). This is the smallest possible model that explains these trajectories. The bivariate polynomial is then derived from a specific polynomial representation of the MPUM.     

Quadrature rules based on partial fraction expansions

Quadrature rules are typically derived by requiring that all polynomials of a certain degree be integrated exactly. The nonstandard issue discussed here is the requirement that, in addition to the polynomials, the rule also integrates a set of prescribed rational functions exactly. Recurrence formulas for computing such quadrature rules are derived. In addition, Fejér's first rule, which is based on polynomial interpolation at Chebyshev nodes, is extended to integrate also rational functions with pre-assigned poles exactly. Numerical results, showing a favorable comparison with similar rules that have been proposed in the literature, are presented. An error analysis of a representative test problem is given. This revised version was published online in June 2006 with corrections to the Cover Date.     

Über B. Buchbergers verfahren,systeme algebraischer gleichungen zu lösen

An algorithm of B. Buchberger's is extended to polynomial rings over a Noetherian ring. In a specialized version, it can be used for computing “elimination ideals”. Over fields, it provides the determination of the minimal prime ideals which contain the given ideal, except that the primeness must be proved with other methods. Estimates for computing time are not given.     

The 16th Hilbert problem on algebraic limit cycles

For real planar polynomial differential systems there appeared a simple version of the 16th Hilbert problem on algebraic limit cycles: Is there an upper bound on the number of algebraic limit cycles of all polynomial vector fields of degree m? In [J. Llibre, R. Ramírez, N. Sadovskaia, On the 16th Hilbert problem for algebraic limit cycles, J. Differential Equations 248 (2010) 1401-1409] Llibre, Ramírez and Sadovskaia solved the problem, providing an exact upper bound, in the case of invariant algebraic curves generic for the vector fields, and they posed the following conjecture: Is1+(m−1)(m−2)/2the maximal number of algebraic limit cycles that a polynomial vector field of degree m can have?In this paper we will prove this conjecture for planar polynomial vector fields having only nodal invariant algebraic curves. This result includes the Llibre et al.?s as a special one. For the polynomial vector fields having only non-dicritical invariant algebraic curves we answer the simple version of the 16th Hilbert problem.     

Applying sieving to the computation of quadratic class groups

We present a new algorithm for computing the ideal class group of an imaginary quadratic order which is based on the multiple polynomial version of the quadratic sieve factoring algorithm. Although no formal analysis is given, we conjecture that our algorithm has sub-exponential complexity, and computational experience shows that it is significantly faster in practice than existing algorithms.

     

The Complexity of Computing the Hilbert Polynomial of Smooth Equidimensional Complex Projective Varieties

We continue the study of counting complexity begun in [13], [14], [15] by proving upper and lower bounds on the complexity of computing the Hilbert polynomial of a homogeneous ideal. We show that the problem of computing the Hilbert polynomial of a smooth equidimensional complex projective variety can be reduced in polynomial time to the problem of counting the number of complex common zeros of a finite set of multivariate polynomials. The reduction is based on a new formula for the coefficients of the Hilbert polynomial of a smooth variety. Moreover, we prove that the more general problem of computing the Hilbert polynomial of a homogeneous ideal is polynomial space hard. This implies polynomial space lower bounds for both the problems of computing the rank and the Euler characteristic of cohomology groups of coherent sheaves on projective space, improving the #P-lower bound in Bach [1].     

A Modification of Lagrange Interpolation

A modification of Lagrange interpolation based on the zeros of the Chebyshev polynomial of the second kind is constructed, which interpolates at many ofgiven data. Thus, for this node-system the main result gives an affimative answer to a problem suggested by Bernstein in 1930. Moreover, our modification has a Timan-Gopengauz type approximation rate.     

On the cost of computing roots of polynomials

Recently Smale has obtained probabilistic estimates of the cost of computing a zero of a polynomial using a global version of Newton's method. Roughly speaking, his result says that, with the exception of a set of polynomials where the method fails or is very slow, the cost grows as a polynomial in the degree. He also asked whether similar results hold for PL homotopy methods. This paper gives such a result for a special algorithm of the PL homotopy type devised by Kuhn. Its main result asserts that the cost of computing some zero of a polynomial of degreen to an accuracy of ε (measured by the number of evaluations of the polynomial) grows no faster than O(n ³ log₂(n/ε)). This is a worst case analysis and holds for all polynomials without exception. This work was supported, in part, by National Science Foundation Grant MCS79-10027 and, in part, by a fellowship of the Guggenheim Foundation.     

Normal forms of families of maps in the Poincaré domain

An analog of Brushlinskaya’s theorem about normal forms of deformations of vector fields in the Poincaré domain is proved; namely, it is proved that for each analytic map whose linear part at a fixed point belongs to the Poincaré domain and has different eigenvalues, the analytic normal form of a deformation of this map is polynomial and contains (in addition to the linear part) only monomials that are resonant for the unperturbed map. A global (with respect to the parameter) version of this theorem is also proved.     

A polynomial-time complexity bound for the computation of the singular part of a Puiseux expansion of an algebraic function

In this paper we present a refined version of the Newton polygon process to compute the Puiseux expansions of an algebraic function defined over the rational function field. We determine an upper bound for the bit-complexity of computing the singular part of a Puiseux expansion by this algorithm, and use a recent quantitative version of Eisenstein's theorem on power series expansions of algebraic functions to show that this computational complexity is polynomial in the degrees and the logarithm of the height of the polynomial defining the algebraic function.

     

Numerical integration over the square in the presence of algebraic/logarithmic singularities with an application to aerodynamics

Tensor-product formulae based on one-dimensional Gaussian quadratures are developed for evaluating double integrals of the type indicated in the title. If the singularities occur only along the diagonal and the regular part of the integrand is a polynomial of total degree d, the formulae can be made exact by choosing the number of quadrature points larger than, or equal to, 1?+?d/2. Numerical examples are given as well as an application to a problem in aerodynamics.     

Polynomial Algorithms for a Class of Discrete Minmax Linear Programming Problems

We consider the problem of obtaining integer solutions to a minmax linear programming problem. Although this general problem is NP-complete, it is shown that a restricted version of this problem can be solved in polynomial time. For this restricted class of problems two polynomial time algorithms are suggested, one of which is strongly polynomial whenever its continuous analogue and an associated linear programming problem can be solved by a strongly polynomial algorithm. Our algorithms can also be used to obtain integer solutions for the minmax transportation problem with an inequality budget constraint. The equality constrained version of this problem is shown to be NP-complete. We also provide some new insights into the solution procedures for the continuous minmax linear programming problem.