Accurate Enclosure of the Zero Set of Multivariate Polynomials

The zero set of one general multivariate polynomial is enclosed by unions and intersections of funnel-shaped unbounded sets. There are sharper enclosures for the zero set of a polynomial in two complex variables with complex interval coefficients. Common zeros of a polynomial system can be located by an appropriate intersection of these enclosure sets in an appropriate space. The resulting domain is directly brought into polynomial equation solvers.     

A single oval of Cassini for the zeros of a polynomial

We derive two ovals of Cassini, each containing all the zeros of a polynomial. The computational cost to obtain these ovals is similar to that of the Brauer set for the companion matrix of a polynomial, although they are frequently smaller. Their derivation is based on the Gershgorin set for an appropriate polynomial of the companion matrix.     

On Newton's method with a class of rational functions

The classical Newton's method for determining a real factor of a polynomial is shown to be one member of a family of similar algorithms found by considering the roots of a class of rational functions. These algorithms are variants of the Birge Vieta method for solving polynomial equations. Methods for selecting an appropriate member of the family for a general problem are compared. Third order possibilities are shown to exist and results for a particular case are reported.     

Pincement de polynômes

Let be a semi-hyperbolic polynomial in the sense of Carleson-Jones-Yoccoz with an attracting point. The goal of this paper is to show that one can define a semi-hyperbolic deformation such that the attracting cycle becomes parabolic for the limit polynomial and that and are semi-conjugate. This deformation is defined by pinching curves in appropriate quotient spaces. Received: September 11, 1998     

Embeddings of universal algebras into simple ones

This paper is concerned with the question which conditions imply the embeddability of an algebra of a varietyV into a simple algebra ofV. It is shown that this problem can be solved by using the concept of polynomial algebras and furthermore that polynomial algebras are in a certain sense most appropriate in order to deal with this question. The applicability of this method is exhibited by examples concerning varieties of groups and rings.Presented by L. Fuchs.     

Explicit volume-preserving splitting methods for polynomial divergence-free vector fields

We present new, explicit, volume-preserving splitting methods for polynomial divergence-free vector fields of arbitrary degree (both positive and negative). The main idea is to decompose the divergence polynomial by means of an appropriate basis for polynomials: the monomial basis. For each monomial basis function, the split fields are then identified by collecting the appropriate terms in the vector field so that each split vector field is volume preserving. We show that each split field can be integrated exactly by analytical methods. Thus, the composition yields a volume preserving numerical method. Our numerical tests indicate that the methods compare favorably to standard integrators both in the quality of the numerical solution and the computational effort.     

Problems of control and information theory (Hungary)

The bezoutian matrix, which provides information concerning co-primeness and greatest common divisor of polynomials, has recently been generalized by Heinig to the case of square polynomial matrices. Some of the properties of the bezoutian for the scalar case then carry over directly. In particular, the central result of the paper is an extension of a factorization due to Barnett, which enables the bezoutian to be expressed in terms of a Kronecker matrix polynomial in an appropriate block companion matrix. The most important consequence of this result is a determination of the structure of the kernel of the bezoutian. Thus, the bezoutian is nonsingular if and only if the two polynomial matrices have no common eigenvalues (i.e., their determinants are relatively prime); otherwise, the dimension of the kernel is given in terms of the multiplicities of the common eigenvalues of the polynomial matrices. Finally, an explicit basis is developed for the kernel of the bezoutian, using the concept of Jordan chains.     

A Kind of Generalization of the Curve Type Node Configuration in R^S（S 〉 2）

A kind of generalization of the Curve Type Node Configuration is given in this paper,and it is called the generalized node configuration CTNCB in RS(S＞2).The related multivariate polynomial interpolation problem is discussed.It is proved that the CTNCB is an appropriate node configuration for the polynomial space PSn (S＞2).And the expressions of the multivariate Vandermonde determinants that are related to the Odd Curve Type Node Configuration in R2 are also obtained.     

A new,simple approach to the derivation of exact analytical formulae for the zeros of analytic functions

A very simple method for the construction of the polynomial whose zeros coincide with the zeros of an analytic function inside and along a simple closed contour in the complex plane, based on an appropriate application of the Cauchy theorem in complex analysis, is proposed. The present method was motivated by the classical Burniston-Siewert method, based on the theory of the Riemann-Hilbert boundary-value problem for the construction of the aforementioned polynomial, but, although essentially equivalent to the Burniston-Siewert method, it is much simpler.     

Recipe theorem for the Tutte polynomial for matroids,renormalization group-like approach

Using a quantum field theory renormalization group-like differential equation, we give a new proof of the recipe theorem for the Tutte polynomial for matroids. The solution of such an equation is in fact given by some appropriate characters of the Hopf algebra of isomorphic classes of matroids, characters which are then related to the Tutte polynomial for matroids. This Hopf algebraic approach also allows to prove, in a new way, a matroid Tutte polynomial convolution formula appearing in [W. Kook, V. Reiner, D. Stanton, A convolution formula for the Tutte polynomial, J. Combin. Theory Ser. B 76 (1999) 297–300] and [G. Etienne, M. Las Vergnas, External and internal elements of a matroid basis, Discrete Math. 179 (1998) 111–119].     

一类插值多项式算子与无界函数逼近

将经典“试探函数组”1,x,x^2应用于扩展乘数法,建立了一个判别线性正算子能否改造为逼近任何无界连续函数的充要条件。利用该条件给出了一类变形的插值多项式算子的收敛性定理,得到了具有一般性的结论。     

多项式Laplace算子的特征值估计

讨论了多项式Laplace算子Dirichlet问题,首先通过选取适当的函数,根据RayLeigh-Ritz不等式,得到了该问题用前k个特征值来估计第k+1个特征值的不等式,然后通过选取适当的系数,发现不等式蕴含成庆明和杨洪苍的结论及吴发恩和曹林芬的结论,且根据Chebyshev不等式等,证明了该不等式优于陈祖墀和钱春林的结论.     

An extended version of Schur-Cohn-Fujiwara theorem in stability theory

This paper is concerned with root localization of a complex polynomial with respect to the unit circle in the more general case. The classical Schur-Cohn-Fujiwara theorem converts the inertia problem of a polynomial to that of an appropriate Hermitian matrix under the condition that the associated Bezout matrix is nonsingular. To complete it, we discuss an extended version of the Schur-Cohn-Fujiwara theorem to the singular case of that Bezout matrix. Our method is mainly based on a perturbation technique for a Bezout matrix. As an application of these results and methods, we further obtain an explicit formula for the number of roots of a polynomial located on the upper half part of the unit circle as well.     

A simple randomised algorithm for convex optimisation

We consider maximising a concave function over a convex set by a simple randomised algorithm. The strength of the algorithm is that it requires only approximate function evaluations for the concave function and a weak membership oracle for the convex set. Under smoothness conditions on the function and the feasible set, we show that our algorithm computes a near-optimal point in a number of operations which is bounded by a polynomial function of all relevant input parameters and the reciprocal of the desired precision, with high probability. As an application to which the features of our algorithm are particularly useful we study two-stage stochastic programming problems. These problems have the property that evaluation of the objective function is #P-hard under appropriate assumptions on the models. Therefore, as a tool within our randomised algorithm, we devise a fully polynomial randomised approximation scheme for these function evaluations, under appropriate assumptions on the models. Moreover, we deal with smoothing the feasible set, which in two-stage stochastic programming is a polyhedron.     

The linear factorization of polynomial operator pencils

Sufficient conditions are found for the linear factorization of polynomial operator pencils of arbitrary order in a Banach space. This factorization is generated by the solution of an appropriate operator equation.Translated from Matematicheskie Zametki, Vol. 13, No. 4, pp. 551–559, April, 1973.The author wishes to express his thanks to A. G. Kostyuchenko for the formulation of the problem.     

On some iteration functions for the simultaneous computation of multiple complex polynomial zeros

Second order methods for simultaneous approximation of multiple complex zeros of a polynomial are presented. Convergence analysis of new iteration formulas and an efficient criterion for the choice of the appropriate value of a root are discussed. A numerical example is given which demonstrates the effectiveness of the presented methods.     

Networks of polynomial pieces with application to the analysis of point clouds and images

We consider Hölder smoothness classes of surfaces for which we construct piecewise polynomial approximation networks, which are graphs with polynomial pieces as nodes and edges between polynomial pieces that are in ‘good continuation’ of each other. Little known to the community, a similar construction was used by Kolmogorov and Tikhomirov in their proof of their celebrated entropy results for Hölder classes.We show how to use such networks in the context of detecting geometric objects buried in noise to approximate the scan statistic, yielding an optimization problem akin to the Traveling Salesman. In the same context, we describe an alternative approach based on computing the longest path in the network after appropriate thresholding.For the special case of curves, we also formalize the notion of ‘good continuation’ between beamlets in any dimension, obtaining more economical piecewise linear approximation networks for curves.We include some numerical experiments illustrating the use of the beamlet network in characterizing the filamentarity content of 3D data sets, and show that even a rudimentary notion of good continuity may bring substantial improvement.     

An extremal problem for the derivative of a rational function

Erd?s’ well-known problem on the maximum absolute value of the derivative of a polynomial on a connected lemniscate is extended to the case of a rational function. Moreover, under the assumption that certain lemniscates are connected, a sharp upper bound for the absolute value of the derivative of a rational function at any point in the plane different from the poles is found. The role of the extremal function is played by an appropriate Zolotarev fraction.     

Characterization of tomographic reconstructions which commute with rigid motions

This note considers linear reconstruction operators for parallel beam tomography when the number of radiographs is finite. It is shown that if such reconstructions are continuous and commute with rigid motions in an appropriate sense, then they must be representable as convolution operators with a polynomial kernel whose degree depends on the number of radiographs.     

On the location of the zeros of a generalized polynomial

A determinantal formula, based on an appropriate extension of the definition of subresultants, is derived for the location of the number of zeros of a generalized polynomial in the upper half plane.