Nonlinear reduction for solving deficient polynomial systems by continuation methods

Summary Neither continuation methods, nor symbolic elimination methods can be directly applied to compute all finite solutions to polynomial systems, because the amount of computational time is mostly not proportional to the dimension of the system and to the number of finite solutions. The notion of S-polynomials is used to developed a reduction algorithm to lower the total degree of the deficient polynomial system, so that computing the solutions at infinity can be avoided. Applying the reduction algorithm before solving the system with continuation methods, yields a reliable solution method.     

An algorithm for unimodular completion over Laurent polynomial rings

We present a new and simple algorithm for completion of unimodular vectors with entries in a multivariate Laurent polynomial ring over an infinite field K. More precisely, given n?3 and a unimodular vector V=^t(v₁,…,v_n)∈Rⁿ (that is, such that 〈v₁,…,v_n〉=R), the algorithm computes a matrix M in M_n(R) whose determinant is a monomial such that MV=^t(1,0,…,0), and thus M^-1 is a completion of V to an invertible matrix.     

Lower bounds for real solutions to sparse polynomial systems

We show how to construct sparse polynomial systems that have non-trivial lower bounds on their numbers of real solutions. These are unmixed systems associated to certain polytopes. For the order polytope of a poset P this lower bound is the sign-imbalance of P and it holds if all maximal chains of P have length of the same parity. This theory also gives lower bounds in the real Schubert calculus through the sagbi degeneration of the Grassmannian to a toric variety, and thus recovers a result of Eremenko and Gabrielov.     

A Levin-type algorithm for accelerating the convergence of Fourier series

A nonlinear sequence transformation is presented which is able to accelerate the convergence of Fourier series. It is tailored to be exact for a certain model sequence. As in the case of the Levin transformation and other transformations of Levin-type, in this model sequence the partial sum of the series is written as the sum of the limit (or antilimit) and a certain remainder, i.e., it is of Levin-type. The remainder is assumed to be the product of a remainder estimate and the sum of the first terms oftwo Poincaré-type expansions which are premultiplied by two different phase factors. This occurrence of two phase factors is the essential difference to the Levin transformation. The model sequence for the new transformation may also be regarded as a special case of a model sequence based on several remainder estimates leading to the generalized Richardson extrapolation process introduced by Sidi. An algorithm for the recursive computation of the new transformation is presented. This algorithm can be implemented using only two one-dimensional arrays. It is proved that the sequence transformation is exact for Fourier series of geometric type which have coefficients proportional to the powers of a numberq, |q|<1. It is shown that under certain conditions the algorithm indeed accelerates convergence, and the order of the convergence is estimated. Finally, numerical test data are presented which show that in many cases the new sequence transformation is more powerful than Wynn's epsilon algorithm if the remainder estimates are properly chosen. However, it should be noted that in the vicinity of singularities of the Fourier series the new sequence transformation shows a larger tendency to numerical instability than the epsilon algorithm.     

Sweeping algebraic curves for singular solutions

Many problems give rise to polynomial systems. These systems often have several parameters and we are interested to study how the solutions vary when we change the values for the parameters. Using predictor-corrector methods we track the solution paths. A point along a solution path is critical when the Jacobian matrix is rank deficient. The simplest case of quadratic turning points is well understood, but these methods no longer work for general types of singularities. In order not to miss any singular solutions along a path we propose to monitor the determinant of the Jacobian matrix. We examine the operation range of deflation and relate the effectiveness of deflation to the winding number. Computational experiments on systems coming from different application fields are presented.     

Epsilon multiplicity for graded algebras

The notion of ε-multiplicity was originally defined by Ulrich and Validashti as a limsup and they used it to detect integral dependence of modules. It is important to know if it can be realized as a limit. In this article we show that the relative ε-multiplicity of reduced standard graded algebras over an excellent local ring exists as a limit. We also obtain some important special cases of Cutkosky's results concerning ε-multiplicity, as corollaries of our main theorem.     

Every arrangement extends to a spread

Supported in part by NSA grant MDA904-89-H-2038, PSC-CUNY grant 662330, and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF grant STC88-09648.     

H-bases for polynomial interpolation and system solving

The H-basis concept allows, similarly to the Gröbner basis concept, a reformulation of nonlinear problems in terms of linear algebra. We exhibit parallels of the two concepts, show properties of H-bases, discuss their construction and uniqueness questions, and prove that n polynomials in n variables are, under mild conditions, already H-bases. We apply H-bases to the solution of polynomial systems by the eigenmethod and to multivariate interpolation.     

There are uncountably many universal topological planes

We prove the existence of uncountably many nonisomorphic topological projective planes, each universal in the sense that it contains an isomorphic copy of every pseudoline arrangement.     

Embedding theorems for classes of convex sets

Rådström's embedding theorem states that the nonempty compact convex subsets of a normed vector space can be identified with points of another normed vector space such that the embedding map is additive, positively homogeneous, and isometric. In the present paper, extensions of Rådström's embedding theorem are proven which provide additional information on the embedding space. These results include those of Hörmander who proved a similar embedding theorem for the nonempty closed bounded convex subsets of a Hausdorff locally convex vector space. In contrast to Hörmander's approach via support functionals, all embedding theorems of the present paper are proven by a refinement of Rådström's original method which is constructive and does not rely on Zorn's lemma. This paper also includes a brief discussion of some actual or potential applications of embedding theorems for classes of convex sets in probability theory, mathematical economics, interval mathematics, and related areas.     

Optimality conditions for non-finite valued convex composite functions

Burke (1987) has recently developed second-order necessary and sufficient conditions for convex composite optimization in the case where the convex function is finite valued. In this note we present a technique for reducing the infinite valued case to the finite valued one. We then use this technique to extend the results in Burke (1987) to the case in which the convex function may take infinite values. We conclude by comparing these results with those established by Rockafellar (1989) for the piecewise linear-quadratic case.Dedicated to the memory of Robin W. ChaneyResearch supported in part by the National Science Foundation under grants DMS-8602399 and DMS-8803206, and by the Air Force Office of Scientific Research under grant ISSA-860080.Research supported in part by the Natural Sciences and Engineering Research Council of Canada under grant OGP41983.     

Asymptotic structure for solutions of the Cauchy problem for Burgers type equations

Large time asymptotic structure for solutions of the Cauchy problem for a generalized Burgers equation is determined. In particular, Gelfand’s question about location of viscous shock waves for such equations is answered.     

Wong-Zakai approximations for stochastic differential equations

The aim of this paper is to give a wide introduction to approximation concepts in the theory of stochastic differential equations. The paper is principally concerned with Zong-Zakai approximations. Our aim is to fill a gap in the literature caused by the complete lack of monographs on such approximation methods for stochastic differential equations; this will be the objective of the author's forthcoming book. First, we briefly review the currently-known approximation results for finite- and infinite-dimensional equations. Then the author's results are preceded by the introduction of two new forms of correction terms in infinite dimensions appearing in the Wong-Zakai approximations. Finally, these results are divided into four parts: for stochastic delay equations, for semilinear and nonlinear stochastic equations in abstract spaces, and for the Navier-Stokes equations. We emphasize in this paper results rather than proofs. Some applications are indicated.The author's research was partially supported by KBN grant No. 2 P301 052 03.     

Remarks on some basic concepts in the KKM theory

In the KKM theory, some authors adopt the concepts of the compact closure (ccl), compact interior (cint), transfer compactly closed-valued multimap, transfer compactly l.s.c. multimap, and transfer compactly local intersection property, respectively, instead of the closure, interior, closed-valued multimap, l.s.c. multimap, and possession of a finite open cover property. In this paper, we show that such adoption is inappropriate and artificial. In fact, any theorem with a term with “transfer” attached is equivalent to the corresponding one without “transfer”. Moreover, we can invalidate terms with “compactly” attached by giving a finer topology on the underlying space. In such ways, we obtain simpler formulations of KKM type theorems, Fan-Browder type fixed point theorems, and other results in the KKM theory on abstract convex spaces.     

Laplace’s method for iterated complex Brownian integrals

A kind of Laplace’s method is developped for iterated stochastic integrals where integrators are complex standard Brownian motions. Then it is used to extend properties of Bougerol and Jeulin’s path transform in the random case when simple representations of complex semisimple Lie algebras are not supposed to be minuscule.     

A mathematical flat integral realization and a large deviation result for the free Euclidean field

In this paper, we give a nonstandard construction of the free Euclidean field via S-white noise. This provides a flat integral realization of the free Euclidean field measure, which extends N. J. Cutland's flat integral representation of Wiener measure. Moreover, we show how a Cameron-Martin type formula for translations of the free field measure and a Schilder type large deviation principle for the scalar free field measure can be deduced from our nonstandard construction.SFB 237 Essen-Bochum-Düseldorf; BiBoS-Research Centre; CERFIM, Locarno, Switzerland.     

Ultra-analytic effect of Cauchy problem for a class of kinetic equations

The smoothing effect of the Cauchy problem for a class of kinetic equations is studied. We firstly consider the spatially homogeneous nonlinear Landau equation with Maxwellian molecules and inhomogeneous linear Fokker-Planck equation to show the ultra-analytic effects of the Cauchy problem. Those smoothing effect results are optimal and similar to heat equation. In the second part, we study a model of spatially inhomogeneous linear Landau equation with Maxwellian molecules, and show the analytic effect of the Cauchy problem.