Computing monodromy via continuation methods on random Riemann surfaces

We consider a Riemann surface X defined by a polynomial f(x,y) of degree d, whose coefficients are chosen randomly. Hence, we can suppose that X is smooth, that the discriminant δ(x) of f has d(d−1) simple roots, Δ, and that δ(0)≠0, i.e. the corresponding fiber has d distinct points {y₁,…,y_d}. When we lift a loop 0∈γ⊂C−Δ by a continuation method, we get d paths in X connecting {y₁,…,y_d}, hence defining a permutation of that set. This is called monodromy.Here we present experimentations in Maple to get statistics on the distribution of transpositions corresponding to loops around each point of Δ. Multiplying families of “neighbor” transpositions, we construct permutations and the subgroups of the symmetric group they generate. This allows us to establish and study experimentally two conjectures on the distribution of these transpositions and on transitivity of the generated subgroups.Assuming that these two conjectures are true, we develop tools allowing fast probabilistic algorithms for absolute multivariate polynomial factorization, under the hypothesis that the factors behave like random polynomials whose coefficients follow uniform distributions.     

Curve generation of implicit functions by incremental computers

The conventional numerical solution of an implicit function f(x, y) = 0 is substantially complicated for calculating by any computer. We propose a new method representing the argument of the implicit function as a unary function of a parameter, t, if the continuous and unique solution of f(x, y) = 0 exists. The total differential $\text{d}\text{f}\text{d}\text{t}$ constitutes simultaneous differential equations of which the solution about x and y is unique. The Newton-Raphson method must be used to calculate the values near singular points of an implicit function and then the sign of dt has to be decided according to four special cases. Incremental computers are suitable for curve generation of implicit functions by the new method, because the incremental computer can perform more complex algorithms than the analog computer and can calculate faster than the digital computer. This method is easily applicable to curve generation in three-dimensional space.     

Fixed point theorem of generalized quasi-contractive mapping in cone metric space

In this paper, we introduce the generalized quasi-contractive mapping f in a cone metric space (X,d). f is called a generalized quasi-contractive if there is a real λ∈[0,1) such that for all x,y∈X,

d(fx,fy)≤λs     

On the extension of solutions of linear constant-coefficient PDE

We solve the following over-determined boundary value problem (the “extension problem”): Let R(∂) be a matrix whose entries are linear partial differential operators, with constant coefficients. Let Ω be a non-empty, open, bounded, convex set. We consider the homogeneous system R(∂)f=0 in a neighborhood of , subject to the boundary condition f=g in a neighborhood of ∂Ω. For a given g, we give a criterion for the (unique) existence of a smooth solution f to this problem. There are two obvious necessary conditions: g is smooth and R(∂)g=0 in a neighborhood of ∂Ω. We characterize the class of differential operators R(∂) for which the problem is solvable for any g satisfying the necessary conditions. Finally, in the case where the solution is non-unique, we consider the possibility of obtaining uniqueness by fixing several components of the desired solution.     

Approximate Solutions of Polynomial Equations

In this paper, we introduce “approximate solutions" to solve the following problem: given a polynomial F(x, y) over Q, where x represents an n -tuple of variables, can we find all the polynomials G(x) such that F(x, G(x)) is identically equal to a constant c in Q ? We have the following: let F(x, y) be a polynomial over Q and the degree of y in F(x, y) be n. Either there is a unique polynomial g(x)  ∈ Q [ x ], with its constant term equal to 0, such that F(x, y)  = ∑_j = 0ⁿc_j(y − g(x))^jfor some rational numbers c_j, hence, F(x, g(x)  + a)  ∈ Q for all a ∈ Q, or there are at most t distinct polynomials g₁(x),⋯ , g_t(x), t ≤ n, such that F(x, g_i(x))  ∈ Q for 1  ≤ i ≤ t. Suppose that F(x, y) is a polynomial of two variables. The polynomial g(x) for the first case, or g₁(x),⋯ , g_t(x) for the second case, are approximate solutions of F(x, y), respectively. There is also a polynomial time algorithm to find all of these approximate solutions. We then use Kronecker’s substitution to solve the case of F(x, y).     

Asymptotic equivalence between two difference systems

In this paper, we study the asymptotic equivalence between the linear system Δx(n) = A(n)x(n) and its perturbation Δy(n) = A(n)y(n)+g(n, y(n)) by using the comparison principle and supplementary projections. Furthermore, we establish some asymptotic properties for the nonlinear system Δx(n) = f(n, x(n)).     

A recursive and a grammatical characterization of the exponential-time languages

We characterize the class of all languages which are acceptable in exponential time by means of recursive and grammatical methods. (i) The class of all languages which are acceptable in exponential time is uniquely characterized by the class of all (0-1)-functions which can be generated, starting with the initial functions of the Grzegorczyk-class $\text{E}$², by means of subtitution and limited recursion of the form f(x, y + 1) = h(x, y), f(x, y), f(x, l(x, y))), l(x, y) ? y. (ii) The class of all languages which are acceptable in exponential time is equal to the class of all languages generated by context-sensitive grammars with context-free control sets.     

Existence of solutions to singular integral equations

Nonnegative solutions are established for singular integral equations of the form y(t) = h(t) + ∫^T₀ k(t, s)f(s, y(s)) ds for t ∈ [0, T]. Here f may be singular at y = 0.     

An application of H differentiability to generalized complementarity problems over symmetric cones

In this paper, we focus on a generalized complementarity problems over symmetric cone GSCCP(f,g) when the underlying functions f and g are H-differentiable. By introducing the concepts of relatively uniform Cartesian P-property, relatively Cartesian P(P₀)-property, the Cartesian semimonotone (E₀)-property (strictly Cartesian semimonotone (E)-property), and the relatively regular point with respect to the merit function Ψ(x), we extend various similar results proved in GCP(f,g) to generalized complementarity problems over symmetric cone GSCCP(f,g) and establish various conditions on f and g to get a solution to GSCCP(f,g).     

On the qualitative behaviors of solutions of third order nonlinear differential equations

We present some new results about oscillation and asymptotic behavior of solutions of third order nonlinear differential equations of the form

(r₂(t)(r₁(t)y^′)^′)^′+p(t)y^′+q(t)f(y(g(t)))=0.     

Fast Computation of the Bezout and Dixon Resultant Matrices

Efficient algorithms are derived for computing the entries of the Bezout resultant matrix for two univariate polynomials of degree n and for calculating the entries of the Dixon–Cayley resultant matrix for three bivariate polynomials of bidegree (m, n). Standard methods based on explicit formulas requireO (n³) additions and multiplications to compute all the entries of the Bezout resultant matrix. Here we present a new recursive algorithm for computing these entries that uses onlyO (n²) additions and multiplications. The improvement is even more dramatic in the bivariate setting. Established techniques based on explicit formulas requireO (m⁴n⁴) additions and multiplications to calculate all the entries of the Dixon–Cayley resultant matrix. In contrast, our recursive algorithm for computing these entries uses onlyO (m²n³) additions and multiplications.     

Bounded dilation maps of hypercubes into Cayley graphs on the symmetric group

LetG andH be graphs with |V(G)≤ |V(H)|. Iff:V(G) →V(H) is a one-to-one map, we letdilation(f) be the maximum of dist _H (f x),f(y)) over all edgesxy inG where dist _H denotes distance inH. The construction of maps fromG toH of small dilation is motivated by the problem of designing small slowdown simulations onH of algorithms that were originally designed for the networkG. LetS(n), thestar network of dimension n, be the graph whose vertices are the elements of the symmetric group of degreen, two verticesx andy being adjacent ifx o (1,i) =y for somei. That is,xy is an edge ifx andy are related by a transposition involving some fixed symbol (which we take to be 1). Also letP(n), thepancake network of dimension n, be the graph whose vertices are the elements of the symmetric group of degreen, two verticesx andy being adjacent if one can be obtained from the other by reversing some prefix. That is,xy is an edge ifx andy are related byx o (1,i(2,i-1) ⋯ ([i/2], [i/2]) =y. The star network (introduced in [AHK]) has nice symmetry properties, and its degree and diameter are sublogarithmic as functions of the number of vertices, making it compare favorably with the hypercube network. These advantages ofS(n) motivate the study of how well it can simulate other parallel computation networks, in particular, the hypercube. The concern of this paper is to construct low dilation maps of hypercube networks into star or pancake networks. Typically in such problems, there is a tradeoff between keeping the dilationsmall and simulating alarge hypercube. Our main result shows that at the cost ofO (1) dilation asn→ ∞, one can embed a hypercube of near optimum dimension into the star or pancake networksS(n) orP(n). More precisely, lettingQ (d) be the hypercube of dimensiond, our main theorem is stated below. For simplicity, we state it only in the special case when the star network dimension is a power of 2. A more general result (applying to star networks of arbitrary dimension) is obtained by a simple interpolation. This author's research was done during the Spring Semester 1991, as a visiting professor in the Department of Mathematics and Statistics at Miami University.     

Investigation and application of Laplace spectra of orgraphs with the ring structure

The Laplace matrix is a square matrix L = (? _ij ) ∈ ? ^n×n in which all nondiagonal elements are nonpositive and all row sums are equal to zero. Each Laplace matrix corresponds to a weighted orgraph with positive arc weights. The problem of reality of Laplace matrix spectrum for orgraphs of a special type consisting of two “counter” Hamiltonian cycles in one of which one or two arcs are removed is studied. Characteristic polynomials of Laplace matrices of these orgraphs are expressed through polynomials Z _n (x) that can be obtained from Chebyshev second-kind polynomials P _2n (y) by the substitution of y ² = x. The obtained results relate to properties of the product of Chebyshev second-kind polynomials. A direct method for computing the spectrum of Laplace circuit matrix is given. The obtained results can be used for computing the number of spanning trees in orgraphs of the studied type. One of the possible practical applications of these results is the investigation of topology and development of new Internet protocols.     

Improved upper bounds on the L(2,1) -labeling of the skew and converse skew product graphs

An L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)−f(y)|≥2 if d(x,y)=1 and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between x and y in G. The L(2,1)-labeling number λ(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):vV(G)}=k. Griggs and Yeh conjecture that λ(G)≤Δ² for any simple graph with maximum degree Δ≥2. This paper considers the graph formed by the skew product and the converse skew product of two graphs with a new approach on the analysis of adjacency matrices of the graphs as in [W.C. Shiu, Z. Shao, K.K. Poon, D. Zhang, A new approach to the L(2,1)-labeling of some products of graphs, IEEE Trans. Circuits Syst. II: Express Briefs (to appear)] and improves the previous upper bounds significantly.     

Rank and eigenvalues of a supersymmetric tensor, the multivariate homogeneous polynomial and the algebraic hypersurface it defines

A real n-dimensional homogeneous polynomial f(x) of degree m and a real constant c define an algebraic hypersurface S whose points satisfy f(x)=c. The polynomial f can be represented by Ax^m where A is a real mth order n-dimensional supersymmetric tensor. In this paper, we define rank, base index and eigenvalues for the polynomial f, the hypersurface S and the tensor A. The rank is a nonnegative integer r less than or equal to n. When r is less than n, A is singular, f can be converted into a homogeneous polynomial with r variables by an orthogonal transformation, and S is a cylinder hypersurface whose base is r-dimensional. The eigenvalues of f, A and S always exist. The eigenvectors associated with the zero eigenvalue are either recession vectors or degeneracy vectors of positive degree, or their sums. When c⁄=0, the eigenvalues with the same sign as c and their eigenvectors correspond to the characterization points of S, while a degeneracy vector generates an asymptotic ray for the base of S or its conjugate hypersurface. The base index is a nonnegative integer d less than m. If d=k, then there are nonzero degeneracy vectors of degree k−1, but no nonzero degeneracy vectors of degree k. A linear combination of a degeneracy vector of degree k and a degeneracy vector of degree j is a degeneracy vector of degree k+j−m if k+j≥m. Based upon these properties, we classify such algebraic hypersurfaces in the nonsingular case into ten classes.     

Cylindrical decomposition for systems transcendental in the first variable

We present a generalization of the Cylindrical Algebraic Decomposition (CAD) algorithm to systems of equations and inequalities in functions of the form p(x,f₁(x),…,f_m(x),y₁,…,y_n), where p∈Q[x,t₁,…,t_m,y₁,…,y_n] and f₁(x),…,f_m(x) are real univariate functions such that there exists a real root isolation algorithm for functions from the algebra Q[x,f₁(x),…,f_m(x)]. In particular, the algorithm applies when f₁(x),…,f_m(x) are real exp-log functions or tame elementary functions.     

Substitutions into propositional tautologies

We prove that there is a polynomial time substitution (y₁,…,yn):=g(x₁,…,xk) with k?n such that whenever the substitution instance A(g(x₁,…,xk)) of a 3DNF formula A(y₁,…,yn) has a short resolution proof it follows that A(y₁,…,yn) is a tautology. The qualification “short” depends on the parameters k and n.     

Asymptotic behaviour of the solutions of second order functional differential equations

This paper presents integral criteria to determine the asymptotic behaviour of the solutions of second order nonlinear differential equations of the type y^″(x)+q(x)f(y(x))=0, with q(x)>0 and f(y) odd and positive for y>0, as x tends to +∞. It also compares them with the results obtained by Chanturia (1975) in [11] for the same problem.