The lattice of ideals of a polynomial semiring

We show that for a semiringR, the following statements are equivalent: (1)R is a ring, (2) every left ideal ofR[X], the semiring of polynomials overR, is subtractive, (3) the lattice of left ideals ofR[X] is modular.Presented by R. W. Quackenbush.     

On the colored Tutte polynomial of a graph of bounded treewidth

We observe that a formula given by Negami [Polynomial invariants of graphs, Trans. Amer. Math. Soc. 299 (1987) 601-622] for the Tutte polynomial of a k-sum of two graphs generalizes to a colored Tutte polynomial. Consequently, an algorithm of Andrzejak [An algorithm for the Tutte polynomials of graphs of bounded treewidth, Discrete Math. 190 (1998) 39-54] may be directly adapted to compute the colored Tutte polynomial of a graph of bounded treewidth in polynomial time. This result has also been proven by Makowsky [Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Discrete Appl. Math. 145 (2005) 276-290], using a different algorithm based on logical techniques.     

On the orthogonality of residual polynomials\newline of minimax polynomial preconditioning

Summary. This paper studies polynomials used in polynomial preconditioning for solving linear systems of equations. Optimum preconditioning polynomials are obtained by solving some constrained minimax approximation problems. The resulting residual polynomials are referred to as the de Boor-Rice and Grcar polynomials. It will be shown in this paper that the de Boor-Rice and Grcar polynomials are orthogonal polynomials over several intervals. More specifically, each de Boor-Rice or Grcar polynomial belongs to an orthogonal family, but the orthogonal family varies with the polynomial. This orthogonality property is important, because it enables one to generate the minimax preconditioning polynomials by three-term recursive relations. Some results on the convergence properties of certain preconditioning polynomials are also presented. Received February 1, 1992/Revised version received July 7, 1993     

On chromatic and flow polynomial unique graphs

It is known that the chromatic polynomial and flow polynomial of a graph are two important evaluations of its Tutte polynomial, both of which contain much information of the graph. Much research is done on graphs determined entirely by their chromatic polynomials and Tutte polynomials, respectively. Oxley asked which classes of graphs or matroids are determined by their chromatic and flow polynomials together. In this paper, we found several classes of graphs with this property. We first study which graphic parameters are determined by the flow polynomials. Then we study flow-unique graphs. Finally, we show that several classes of graphs, ladders, Möbius ladders and squares of n-cycle are determined by their chromatic polynomials and flow polynomials together. A direct consequence of our theorem is a result of de Mier and Noy [A. de Mier, M. Noy, On graphs determined by their Tutte polynomial, Graphs Comb. 20 (2004) 105-119] that these classes of graphs are Tutte polynomial unique.     

Is the polynomial so perfidious?

Summary. Wilkinson, in [1], has given a comprehensive account of the numerical difficulties of working with polynomials on a floating point computer. The object of this note is to attempt to rehabilitate the polynomial to a certain extent. In particular it is shown here that polynomial deflation can be performed satisfactorily by a method akin to `backward recursion'. Error analyses and examples are given to illustrate the stability of the process. Received October 4, 1993 / Revised version received July 14, 1993     

Recurrence relations for polynomial sequences via Riordan matrices

We give recurrence relations for any family of generalized Appell polynomials unifying so some known recurrences for many classical sequences of polynomials. Our main tool to get our goal is the Riordan group. We use the product of Riordan matrices to interpret some relationships between different polynomial families. Moreover using the Hadamard product of series we get a general recurrence relation for the polynomial sequences associated to the so called generalized umbral calculus.     

A strongly polynomial minimum cost circulation algorithm

A new algorithm is presented for the minimum cost circulation problem. The algorithm is strongly polynomial, that is, the number of arithmetic operations is polynomial in the number of nodes, and is independent of both costs and capacities.     

A Generalization of the One-Step Theorem for Matrix Polynomials

In this paper we give a new proof of Krein's Theorem for orthogonal matrix polynomials based on a "one-step" version of the theorem. This parallels the proof given in [3] of Krein's Theorem in the scalar case.     

Regular Legendrian knots and the HOMFLY polynomial of immersed plane curves

We show that every unframed knot type in has a representative obtained by the Legendrian lifting of an immersed plane curve. This gives a positive answer to the question asked by V.I.Arnold in [3]. The Legendrian lifting lowers the framed version of the HOMFLY polynomial [20] to generic plane curves. We prove that the induced polynomial invariant can be completely defined in terms of plane curves only. Moreover it is a genuine, not Laurent, polynomial in the framing variable. This provides an estimate on the Bennequin-Tabachnikov number of a Legendrian knot. Received: 17 April 1996 / Revised: 12 May 1999 / Published online: 28 June 2000     

A new type of Hermite matrix polynomial series

Conventional Hermite polynomials emerge in a great diversity of applications in mathematical physics, engineering, and related fields. However, in physical systems with higher degrees of freedom it will be of practical interest to extend the scalar Hermite functions to their matrix analogue. This work introduces various new generating functions for Hermite matrix polynomials and examines existence and convergence of their associated series expansion by using Mehler’s formula for the general matrix case. Moreover, we derive interesting new relations for even- and odd-power summation in the generating-function expansion containing Hermite matrix polynomials. Some new results for the scalar case are also presented.     

Orthogonality of residual polynomials used in minimax polynomial preconditioning

Summary. A polynomial from , the set of polynomials of degree less or equal , is called minimax residual polynomial on a compact set if it has least max-norm on among all polynomials from with fixed lowest coefficient or with two fixed lowest coefficients. It is pointed out that recently published results on orthogonality of minimax residual polynomials on two intervals by H. Jiang [5] are direct consequences of results of the author on orthogonality properties of classical minimal polynomials with respect to the max-norm. In fact, as is demonstrated, even more general and stronger results hold. Received May 26, 1994 / Revised version received September 28, 1994     

Massively parallel computation of many-variable polynomial interpolation

In this paper, we present homogeneous polynomials in many variables. We show how the hypercube representation of these polynomials (introduced by Beauzamy et al. in [1], and derived from Bombieri's work in Beauzamy et al. [2]) allows us to build interpolation polynomials, that is, polynomials taking prescribed values at prescribed points in . We then show that the construction is robust and give quantitative estimates on how the constructed polynomial is perturbed if either the data, the points, or both are perturbed. The theorems, constructions, and algorithms answer questions asked by Dr. Ken Clark, U.S. Army Research Office.

In the final part of the paper, we present the explicit algorithms, implemented on the Connection Machines CM200 and CM5 at the Etablissement Technique Central de l'Armement, Arcueil. This algorithm is efficient, especially when the number of variables is high, and it takes all advantage of the massively parallel architecture.     

Smooth polynomial expansions of piecewise-differentiable functions

This paper proposes an extension of the expansions of analytic functions in the A_n polynomials defined by Adomian [1] to consider piecewise-differentiable functions.     

Solving systems of polynomial equations by bounded and real homotopy

Summary The homotopy method for solving systems of polynomial equations proposed by Chow, Mallet-Paret and Yorke is modified in two ways. The first modification allows to keep the homotopy solution curves bounded, the second one to work with real polynomials when solving a system of real equations. For the first method numerical results are presented.     

On Factorization of Trigonometric Polynomials

We give a new proof of the operator version of the Fejér-Riesz Theorem using only ideas from elementary operator theory. As an outcome, an algorithm for computing the outer polynomials that appear in the Fejér-Riesz factorization is obtained. The extremal case, where the outer factorization is also *-outer, is examined in greater detail. The connection to Aglers model theory for families of operators is considered, and a set of families lying between the numerical radius contractions and ordinary contractions is introduced. The methods are also applied to the factorization of multivariate operator-valued trigonometric polynomials, where it is shown that the factorable polynomials are dense, and in particular, strictly positive polynomials are factorable. These results are used to give results about factorization of operator valued polynomials over , in terms of rational functions with fixed denominators.     

A polynomial cycle canceling algorithm for submodular flows

Submodular flow problems, introduced by Edmonds and Giles [2], generalize network flow problems. Many algorithms for solving network flow problems have been generalized to submodular flow problems (cf. references in Fujishige [4]), e.g. the cycle canceling method of Klein [9]. For network flow problems, the choice of minimum-mean cycles in Goldberg and Tarjan [6], and the choice of minimum-ratio cycles in Wallacher [12] lead to polynomial cycle canceling methods. For submodular flow problems, Cui and Fujishige [1] show finiteness for the minimum-mean cycle method while Zimmermann [16] develops a pseudo-polynomial minimum ratio cycle method. Here, we prove pseudo-polynomiality of a larger class of the minimum-ratio variants and, by combining both methods, we develop a polynomial cycle canceling algorithm for submodular flow problems. Received July 22, 1994 / Revised version received July 18, 1997? Published online May 28, 1999     

Preemptive scheduling of interval orders is polynomial

In 1979, Papadimitriou and Yannakakis gave a polynomial time algorithm for the scheduling of jobs requiring unit completion times when the precedence constraints form an interval order. The authors solve here the corresponding problem, for preemptive scheduling (a job can be interrupted to work on more important tasks, and completed at a later time, subject to the usual scheduling constraints.) The m-machine preemptive scheduling problem is shown to have a polynomial algorithm, for both unit time and variable execution times as well, when the precedence constraints are given by an interval order.     

Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems

Summary. The eigenproblem method calculates the solutions of systems of polynomial equations . It consists in fixing a suitable polynomial and in considering the matrix corresponding to the mapping where the equivalence classes are modulo the ideal generated by The eigenspaces contain vectors, from which all solutions of the system can be read off. This access was investigated in [1] and [16] mainly for the case that is nonderogatory. In the present paper, we study the case where have multiple zeros in common. We establish a kind of Jordan decomposition of reflecting the multiplicity structure, and describe the conditions under which is nonderogatory. The algorithmic analysis of the eigenproblem in the general case is indicated. Received May 20, 1994     

Orthogonal polynomial eigenfunctions of second-order partial differerential equations

In this paper, we show that for several second-order partial differential equations

which have orthogonal polynomial eigenfunctions, these polynomials can be expressed as a product of two classical orthogonal polynomials in one variable. This is important since, otherwise, it is very difficult to explicitly find formulas for these polynomial solutions. From this observation and characterization, we are able to produce additional examples of such orthogonal polynomials together with their orthogonality that widens the class found by H. L. Krall and Sheffer in their seminal work in 1967. Moreover, from our approach, we can answer some open questions raised by Krall and Sheffer.