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

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

A constructive approach to nodal splines

In the context of local spline interpolation methods, nodal splines have been introduced as possible fundamental functions by de Villiers and Rohwer in 1988. The corresponding local spline interpolation operator possesses the desirable property of reproducing a large class of polynomials. However, it was remarked that their definition is rather intricate so that it seems desirable to reveal the actual origin of these splines. The real source can be found in the Martensenoperator which can be obtained by two-point Hermite spline interpolation problem posed and proved by Martensen [Darstellung und Entwicklung des Restgliedes der Gregoryschen Quadraturformel mit Hilfe von Spline-Funktionen, Numer. Math. 21(1973)70–80]. On the one hand, we will show how to represent the Hermite Martensen spline recursively and, on the other hand, explicitly in terms of the B-spline by using the famous Marsden identity. Having introduced the Martensenoperator, we will show that the nodal spline interpolation operator can be obtained by a special discretization of the occurring derivatives. We will consider symmetric nodal splines of odd degree that can be obtained by our methods in a natural way.     

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.     

Squared polynomial extrapolation methods with cycling: an application to the positron emission tomography problem

Roland and Varadhan (Appl. Numer. Math., 55:215–226, 2005) presented a new idea called “squaring” to improve the convergence of Lemaréchal’s scheme for solving nonlinear fixed-point problems. Varadhan and Roland (Squared extrapolation methods: A new class of simple and efficient numerical schemes for accelerating the convergence of the EM algorithm, Department of Biostatistics Working Paper. Johns Hopkins University, , 2004) noted that Lemaréchal’s scheme can be viewed as a member of the class of polynomial extrapolation methods with cycling that uses two fixed-point iterations per cycle. Here we combine these two ideas, cycled extrapolation and squaring, and construct a new class of methods, called squared polynomial methods (SQUAREM), for accelerating the convergence of fixed-point iterations. Our main goal is to evaluate whether the squaring device is effective in improving the rate of convergence of cycled extrapolation methods that use more than two fixed-point iterations per cycle. We study the behavior of the new schemes on an image reconstruction problem for positron emission tomography (PET) using simulated data. Our numerical experiments show the effectiveness of first- and higher-order squared polynomial extrapolation methods in accelerating image reconstruction, and also their relative superiority compared to the classical, “unsquared” vector polynomial methods.     

A Note on Relative Efficiency of Axiom Systems

We introduce a notion of relative efficiency for axiom systems. Given an axiom system A_β for a theory T consistent with S¹₂, we show that the problem of deciding whether an axiom system A_α for the same theory is more efficient than A_β is II₂-hard. Several possibilities of speed-up of proofs are examined in relation to pairs of axiom systems A_α, A_β, with A_α ? A_β, both in the case of A_α, A_β having the same language, and in the case of the language of A_α extending that of A_β: in the latter case, letting Pr_α, Pr_β denote the theories axiomatized by A_α, A_β, respectively, and assuming Pr_α to be a conservative extension of Pr_β, we show that if A_α — A_β contains no nonlogical axioms, then A_α can only be a linear speed-up of A_β; otherwise, given any recursive function g and any A_β, there exists a finite extension A_α of A_β such that A_α is a speed-up of A_β with respect to g. Mathematics Subject Classification: 03F20, 03F30.     

Characterization and computation of control invariant sets for linear impulsive control systems

Impulsive control systems are suitable to describe and control a venue of real-life problems, going from disease treatment to aerospace guidance. The main characteristic of such systems is that they evolve freely in-between impulsive actions, which makes it difficult to guarantee its permanence in a given state-space region. In this work, we develop a method for characterizing and computing approximations to the maximal control invariant sets for linear impulsive control systems, which can be explicitly used to formulate a set-based model predictive controller. We approach this task using a tractable and non-conservative characterization of the admissible state sets, namely the states whose free response remains within given constraints, emerging from a spectrahedron representation of such sets for systems with rational eigenvalues. The so-obtained impulsive control invariant set is then explicitly used as a terminal set of a predictive controller, which guarantees the feasibly asymptotic convergence to a target set containing the invariant set. Necessary conditions under which an arbitrary target set contains an impulsive control invariant set (and moreover, an impulsive control equilibrium set) are also provided, while the controller performance are tested by means of two simulation examples.     

Tropical differential equations

Tropical differential equations are introduced and an algorithm is designed which tests solvability of a system of tropical linear differential equations within the complexity polynomial in the size of the system and in the absolute values of its coefficients. Moreover, we show that there exists a minimal solution, and the algorithm constructs it (in case of solvability). This extends a similar complexity bound established for tropical linear systems. In case of tropical linear differential systems in one variable a polynomial complexity algorithm for testing its solvability is designed.We prove also that the problem of solvability of a system of tropical non-linear differential equations in one variable is NP-hard, and this problem for arbitrary number of variables belongs to NP. Similar to tropical algebraic equations, a tropical differential equation expresses the (necessary) condition on the dominant term in the issue of solvability of a differential equation in power series.     

On stationary Markov processes with polynomial conditional moments

We study a class of stationary Markov processes with marginal distributions identifiable by moments such that every conditional moment of degree say m is a polynomial of degree at most m. We show that then under some additional, natural technical assumption there exists a family of orthogonal polynomial martingales. More precisely we show that such a family of processes is completely characterized by the sequence {(α_n, p_n)}_{n ? 0} where α′_ns are some positive reals while p′_ns are some monic orthogonal polynomials. Bakry and Mazet (Séminaire de Probabilit?s, vol. 37, 2003) showed that under some additional mild technical conditions each such sequence generates some stationary Markov process with polynomial regression.

We single out two important subclasses of the considered class of Markov processes. The class of harnesses that we characterize completely. The second one constitutes of the processes that have independent regression property and are stationary. Processes with independent regression property so to say generalize ordinary Ornstein–Uhlenbeck (OU) processes or can also be understood as time scale transformations of Lévy processes. We list several properties of these processes. In particular we show that if these process are time scale transforms of Lévy processes then they are not stationary unless we deal with classical OU process. Conversely, time scale transformations of stationary processes with independent regression property are not Lévy unless we deal with classical OU process.