多元整系数多项式因式分解的一种理论和算法

本文将ｔ（ｔ是大于２的整数）元整系数多项式看成为系数为ｔ－２元整系数多项式的二元多项式，建立了多元整系数多项式因式分解的一种新理论，进而得到了分解多元整系数多项式的一个有力的算法。     

A note on the computational complexity of graph vertex partition

A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstädt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59-73] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such thatG-Sis a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such thatG-Sis a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that G-S is a tree.     

On the use of homogeneous polynomials to develop anisotropic yield functions with applications to sheet forming

This paper investigates the capabilities of several non-quadratic polynomial yield functions to model the plastic anisotropy of orthotropic sheet metal (plane stress). Fourth, sixth and eighth-order homogeneous polynomials are considered. For the computation of the coefficients of the fourth-order polynomial an improved set of analytic formulas is proposed. For sixth and eighth-order polynomials the identification uses optimization. Simple constraints on the optimization process are shown to lead to real-valued convex functions. A general method to extend the above plane stress criteria to full 3D stress states is also suggested. Besides their simplicity in formulation, it is found that polynomial yield functions are capable to model a wide range of anisotropic plastic properties (e.g., the Numisheet’93 mild steel, AA2008-T4, AA2090-T3). The yield functions have then been implemented into a commercial finite element code as constitutive subroutines. The deep drawing of square (Numisheet’93) and cylindrical (AA2090-T3) cups have been simulated. In both cases excellent agreement with experimental data is obtained. In particular, it is shown that non-quadratic polynomial yield functions can simulate cylindrical cups with six or eight ears. We close with a discussion on earing and further examples.     

On polynomial digraphs

Let Φ(x,y) be a bivariate polynomial with complex coefficients. The zeroes of Φ(x,y) are given a combinatorial structure by considering them as arcs of a directed graph G(Φ). This paper studies some relationship between the polynomial Φ(x,y) and the structure of G(Φ).     

Norm Bounds for Ehrhart Polynomial Roots

M. Beck et al. found that the roots of the Ehrhart polynomial of a d-dimensional lattice polytope are bounded above in norm by 1+(d+1)!. We provide an improved bound which is quadratic in d and applies to a larger family of polynomials.     

Chaotic polynomials on Banach spaces

We show the existence of chaotic (in the sense of Devaney) polynomials on Banach spaces of q-summable sequences. Such polynomials P consist of composition of the backward shift with a certain fixed polynomial p of one complex variable on each coordinate. In general we also prove that P is chaotic in the sense of Auslander and Yorke if and only if 0 belongs to the Julia set of p.     

ON THE EXISTENCE OF GLOBAL GENERAL SOLUTIONS OF POLYNOMIAL SYSTEMS

ＯＮＴＨＥＥＸＩＳＴＥＮＣＥＯＦＧＬＯＢＡＬＧＥＮＥＲＡＬＳＯＬＵＴＩＯＮＳＯＦ　ＰＯＬＹＮＯＭＩＡＬＳＹＳＴＥＭＳＺＨＡＯＸＩＡＯＱＩＡＮＧ（赵晓强）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏ...     

Implementing an efficient minimum capacity cut algorithm

In this paper, we present an efficient implementation of theO(mn + n ² logn) time algorithm originally proposed by Nagamochi and Ibaraki (1992) for computing the minimum capacity cut of an undirected network. To enhance computation, various ideas are added so that it can contract as many edges as possible in each iteration. To evaluate the performance of the resulting implementation, we conducted extensive computational experiments, and compared the results with that of Padberg and Rinaldi's algorithm (1990), which is currently known as one of the practically fastest programs for this problem. The results indicate that our program is considerably faster than Padberg and Rinaldi's program, and its running time is not significantly affected by the types of the networks being solved.Corresponding author.     

STABILIZATION OF UNITARY GROUPSOVER POLYNOMIAL RINGS

ＳＴＡＢＩＬＩＺＡＴＩＯＮＯＦＵＮＩＴＡＲＹＧＲＯＵＰＳＯＶＥＲＰＯＬＹＮＯＭＩＡＬＲＩＮＧＳ￥ＹＯＵＨＯＮＧＡｂｓｔｒａｃｔ：Ｔｈｅａｕｔｈｏｒｓｔｕｄｉｅｓｔｈｅｓｔａｂｉｌｉｚａｔｉｏｎｆｏｒｔｈｅｕｎｉｔａｒｙｇｒｏｕｐｓｏｖｅｒｐｏｌｙｎｏ...     

On Nondeterminism,Enumeration Reducibility and Polynomial Bounds

Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e-reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non-deterministic polynomial time reducibility. We define the polynomial time e-degrees as the equivalence classes under this reducibility and investigate their structure on the recursive sets, showing in particular that the pe-degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy.