On the practical value of the notion ofBN-stability

The oldest concept of unconditional stability of numerical integration methods for ordinary differential systems is that ofA-stability. This concept is related to linear systems having constant coefficients and has been introduced by Dahlquist in 1963. More recently, since another contribution of Dahlquist in 1975, there has been much interest in unconditional stability properties of numerical integration methods when applied to non-linear dissipative systems (G-stability,BN-stability,A-contractivity). Various classes of implicit Runge-Kutta methods have already been shown to beBN-stable. However, contrary to the property ofA-stability, when implementing such a method for practical use this unconditional stability property may be lost. The present note clarifies this for a class of diagonally implicit methods and shows at the same time that Rosenbrock's method is notBN-stable.     

Dynamical analysis of the transmission of seasonal diseases using the differential transformation method

The aim of this paper is to apply the differential transformation method (DTM) to solve systems of nonautonomous nonlinear differential equations that describe several epidemic models where the solutions exhibit periodic behavior due to the seasonal transmission rate. These models describe the dynamics of the different classes of the populations. Here the concept of DTM is introduced and then it is employed to derive a set of difference equations for this kind of epidemic models. The DTM is used here as an algorithm for approximating the solutions of the epidemic models in a sequence of time intervals. In order to show the efficiency of the method, the obtained numerical results are compared with the fourth-order Runge–Kutta method solutions. Numerical comparisons show that the DTM is accurate, easy to apply and the calculated solutions preserve the properties of the continuous models, such as the periodic behavior. Furthermore, it is showed that the DTM avoids large computational work and symbolic computation.     

On the vertices of the -additive core

The core of a game v on N, which is the set of additive games φ dominating v such that φ(N)=v(N), is a central notion in cooperative game theory, decision making and in combinatorics, where it is related to submodular functions, matroids and the greedy algorithm. In many cases however, the core is empty, and alternative solutions have to be found. We define the k-additive core by replacing additive games by k-additive games in the definition of the core, where k-additive games are those games whose Möbius transform vanishes for subsets of more than k elements. For a sufficiently high value of k, the k-additive core is nonempty, and is a convex closed polyhedron. Our aim is to establish results similar to the classical results of Shapley and Ichiishi on the core of convex games (corresponds to Edmonds’ theorem for the greedy algorithm), which characterize the vertices of the core.     

On the Hardness of Approximating the Chromatic Number

k -colorable for some fixed . Our main result is that it is NP-hard to find a 4-coloring of a 3-chromatic graph. As an immediate corollary we obtain that it is NP-hard to color a k-chromatic graph with at most colors. We also give simple proofs of two results of Lund and Yannakakis [20]. The first result shows that it is NP-hard to approximate the chromatic number to within for some fixed ε > 0. We point here that this hardness result applies only to graphs with large chromatic numbers. The second result shows that for any positive constant h, there exists an integer , such that it is NP-hard to decide whether a given graph G is -chromatic or any coloring of G requires colors. Received April 11, 1997/Revised June 10, 1999     

Regularity results and optimal control problems for the perturbation of boussinesq equations of the ocean

We study in this article a method which computes the variability of current, density and pressure in an oceanic domain. The equations are of Navier-Stokes type for the velocity and pressure, of transport-diffusion type for the density. They are linearized around a given mean circulation and modified by the Boussinesq approximation: density variations are neglected except in the terms of gravity acceleration. The existence and uniqueness of a solution are proved for two sets of equations: first the three-dimensional problem and then the two-dimensional cyclic problem derived by assuming a sinusoidal x-dependence for the perturbation of mean flow. The latter corresponds to a modelization of tropical instability waves which are illustrated by the El Nino phenomenon.

The value of the pressure p on the surface of ocean is of great interest for physical interpretation. To define that quantity, it is necessary to have the regularity p ? H ¹. We have proved that the perturbation (u,ρ,p) of mean circulation is such that: u ? L ²(0T,H ²), ρ ? L ²(0,T H ²) and p ? L ² L ²(0,T H ¹), provided the perturbation of the windstress is sufficiently regular and satisfies compatibility relations. It is proved by means of an extension method, with even-odd reflection. We then develop a problem of control. The observation is the Variability of pressure on the surface of ocean. The control is the variability of windstress f, which acts as to forcing of the perturbation. We prove the existence and uniqueness of an optimal control, which is characterized by a set of equations including the direct problem and the adjoint problem. These results are valid for the three-dimensional problem and the two-dimensional cyclic problem.     

On the performance of the ICP algorithm

We present upper and lower bounds for the number of iterations performed by the Iterative Closest Point (ICP) algorithm. This algorithm has been proposed by Besl and McKay as a successful heuristic for matching of point sets in d-space under translation, but so far it seems not to have been rigorously analyzed. We consider two standard measures of resemblance that the algorithm attempts to optimize: The RMS (root mean squared distance) and the (one-sided) Hausdorff distance. We show that in both cases the number of iterations performed by the algorithm is polynomial in the number of input points. In particular, this bound is quadratic in the one-dimensional problem, under the RMS measure, for which we present a lower bound construction of Ω(nlogn) iterations, where n is the overall size of the input. Under the Hausdorff measure, this bound is only O(n) for input point sets whose spread is polynomial in n, and this is tight in the worst case.We also present several structural geometric properties of the algorithm under both measures. For the RMS measure, we show that at each iteration of the algorithm the cost function monotonically and strictly decreases along the vector Δt of the relative translation. As a result, we conclude that the polygonal path π, obtained by concatenating all the relative translations that are computed during the execution of the algorithm, does not intersect itself. In particular, in the one-dimensional problem all the relative translations of the ICP algorithm are in the same (left or right) direction. For the Hausdorff measure, some of these properties continue to hold (such as monotonicity in one dimension), whereas others do not.     

On the upper bounds of the minimum number of rows of disjunct matrices

A 0-1 matrix is d-disjunct if no column is covered by the union of any d other columns. A 0-1 matrix is (d; z)-disjunct if for any column C and any d other columns, there exist at least z rows such that each of them has value 1 at column C and value 0 at all the other d columns. Let t(d, n) and t(d, n; z) denote the minimum number of rows required by a d-disjunct matrix and a (d; z)-disjunct matrix with n columns, respectively. We give a very short proof for the currently best upper bound on t(d, n). We also generalize our method to obtain a new upper bound on t(d, n; z). The work of Y. Cheng and G. Lin is supported by Natural Science and Engineering Research Council (NSERC) of Canada, and the Alberta Ingenuity Center for Machine Learning (AICML) at the University of Alberta. The work of D.-Z. Du is partially supported by National Science Foundation under grant No.CCF0621829.     

On the matricial version of Fermat–Euler congruences

The congruences modulo the primary numbers n=p ^a are studied for the traces of the matrices A ⁿ and A ^n-φ(n), where A is an integer matrix and φ(n) is the number of residues modulo n, relatively prime to n. We present an algorithm to decide whether these congruences hold for all the integer matrices A, when the prime number p is fixed. The algorithm is explicitly applied for many values of p, and the congruences are thus proved, for instance, for all the primes p ≤ 7 (being untrue for the non-primary modulus n=6). We prove many auxiliary congruences and formulate many conjectures and problems, which can be used independently. Partially supported by RFBR, grant 05-01-00104. An erratum to this article is available at .     

On the Proper Homotopy Invariance of the Tucker Property

A non-compact polyhedron P is Tucker if, for any compact subset K begong to P, the fundamental group π1 （P - K） is finitely generated. The main result of this note is that a manifold which is proper homotopy equivalent to a Tucker polyhedron is Tucker. We use Poenaru＇s theory of the equivalence relations forced by the singularities of a non-degenerate simplicial map.     

On the minimization of the product of the powers of several integrals

This paper considers the minimization of the product of the powers ofn integrals, each of which depends on a functiony(x) and its derivative . The necessary conditions for the extremum are derived within the frame of the Mayer-Bolza formulation of the calculus of variations, and it is shown that the extremal arc is governed by a second-order differential equation involvingn undetermined multipliers related to the unknown values of the integrals. After the general solution is combined with the definitions of the multipliers and the end conditions, a system ofn+2 algebraic equations is obtained; it involvesn+2 unknowns, that is, then undetermined multipliers and two integration constants.The procedure discussed here can be employed in the study of shapes which are aerodynamically optimum at supersonic, hypersonic, and free-molecular flow velocities, that is, wings and fuselages having the maximum lift-to-drag ratio or the minimum drag. The problem of a slender body of revolution having the minimum pressure drag in Newtonian hypersonic flow is developed as an example. First, a general solution is derived for any pair of conditions imposed on the length, the thickness, the wetted area, and the volume. Then, a particular case is treated, that in which the thickness and the wetted area are given, while the length and the volume are free; the shape minimizing the pressure drag is a cone.This research, supported by the Office of Scientific Research, Office of Aerospace Research, United States Air Force, Grant No. AF-AFOSR-828-67, is a condensed version of the investigation described in Ref. 1. The author is indebted to Messrs. H. Y. Huang, J. C. Heideman, and J. N. Damoulakis for analytical and numerical assistance.     

On the Prime Spectrum of X-Injective Modules

Let R be a commutative ring and M an R-module. The purpose of this article is to introduce a new class of modules over R called X-injective R-modules, where X is the prime spectrum of M. This class contains the family of top modules and that of weak multiplication modules properly. In this article our concern is to extend the properties of multiplication, weak multiplication, and top modules to this new class of modules. Furthermore, for a top module M, we study some conditions under which the prime spectrum of M is a spectral space for its Zariski topology.     

On the use of splines for the numerical solution of nonlinear two-point boundary value problems

Cubic splines on splines and quintic spline interpolations are used to approximate the derivative terms in a highly accurate scheme for the numerical solution of two-point boundary value problems. The storage requirement is essentially the same as for the usual trapezoidal rule but the local accuracy is improved fromO(h ³) to eitherO(h ⁶) orO(h ⁷), whereh is the net size. The use of splines leads to solutions that reflect the smoothness of the slopes of the differential equations.     

The modulator of the local time

Let x(t), 0 ≦ t ≦ 1, be a real measurable function having a local time α(x, t) which is a continuous function of t for almost all x. It is also assumed that, for some m ≧ 2 and some real interval B, α^m(x, 1) is integrable over B. The modulator is a function M_m(t, B), t > 0, denned in terms of α. It is shown that the modulator serves as a measure of the smoothness of the L_m(B)-valued function α(., t) with respect to t. Then it is shown that the modulator plays a central role in precisely describing certain irregularity properties of x(t). The results are applied to the case where x(t) is the sample function of a real stochastic process. In this way new results are obtained for large classes of Gaussian and Markov processes.     

On the Floer homology of cotangent bundles

This paper concerns Floer homology for periodic orbits and for a Lagrangian intersection problem on the cotangent bundle T* M of a compact orientable manifold M. The first result is a new L^∞ estimate for the solutions of the Floer equation, which allows us to deal with a larger—and more natural—class of Hamiltonians. The second and main result is a new construction of the isomorphism between the Floer homology and the singular homology of the free loop space of M in the periodic case, or of the based loop space of M in the Lagrangian intersection problem. The idea for the construction of such an isomorphism is to consider a Hamiltonian that is the Legendre transform of a Lagrangian on T M and to construct an isomorphism between the Floer complex and the Morse complex of the classical Lagrangian action functional on the space of W^1,2 free or based loops on M. © 2005 Wiley Periodicals, Inc.     

A Study of the Direct Spectral Transform for the Defocusing Davey-Stewartson II Equation the Semiclassical Limit

The defocusing Davey-Stewartson II equation has been shown in numerical experiments to exhibit behavior in the semiclassical limit that qualitatively resembles that of its one-dimensional reduction, the defocusing nonlinear Schrödinger equation, namely the generation from smooth initial data of regular rapid oscillations occupying domains of space-time that become well-defined in the limit. As a first step to studying this problem analytically using the inverse scattering transform, we consider the direct spectral transform for the defocusing Davey-Stewartson II equation for smooth initial data in the semiclassical limit. The direct spectral transform involves a singularly perturbed elliptic Dirac system in two dimensions. We introduce a WKB-type method for this problem, proving that it makes sense formally for sufficiently large values of the spectral parameter k by controlling the solution of an associated nonlinear eikonal problem, and we give numerical evidence that the method is accurate for such k in the semiclassical limit. Producing this evidence requires both the numerical solution of the singularly perturbed Dirac system and the numerical solution of the eikonal problem. The former is carried out using a method previously developed by two of the authors, and we give in this paper a new method for the numerical solution of the eikonal problem valid for sufficiently large k. For a particular potential we are able to solve the eikonal problem in closed form for all k, a calculation that yields some insight into the failure of the WKB method for smaller values of k. Informed by numerical calculations of the direct spectral transform, we then begin a study of the singularly perturbed Dirac system for values of k so small that there is no global solution of the eikonal problem. We provide a rigorous semiclassical analysis of the solution for real radial potentials at k=0, which yields an asymptotic formula for the reflection coefficient at k=0 and suggests an annular structure for the solution that may be exploited when k ≠ 0 is small. The numerics also suggest that for some potentials the reflection coefficient converges pointwise as ɛ↓ 0 to a limiting function that is supported in the domain of k-values on which the eikonal problem does not have a global solution. It is expected that singularities of the eikonal function play a role similar to that of turning points in the one-dimensional theory. © 2019 Wiley Periodicals, Inc.     

An algebraic slice in the coadjoint space of the Borel and the Coxeter element

Let g be a complex simple Lie algebra and b a Borel subalgebra. The algebra Y of polynomial semi-invariants on the dual b^? of b is a polynomial algebra on rank g generators (Grothendieck and Dieudonné (1965–1967)) [16]. The analogy with the semisimple case suggests there exists an algebraic slice to coadjoint action, that is an affine translate y+V of a vector subspace of b^? such that the restriction map induces an isomorphism of Y onto the algebra R[y+V] of regular functions on y+V. This holds in type A and even extends to all biparabolic subalgebras (Joseph (2007)) [20]; but the construction fails in general even with respect to the Borel. Moreover already in type C(2) no algebraic slice exists.Very surprisingly the exception of type C(2) is itself an exception. Indeed an algebraic slice for the coadjoint action of the Borel subalgebra is constructed for all simple Lie algebras except those of types B(2m), C(n) and F(4).Outside type A, the slice obtained meets an open dense subset of regular orbits, even though the special point y of the slice is not itself regular. This explains the failure of our previous construction.     

Extremal Bases for the Adjoint Representations of the Simple Lie Algebras

We construct n distinct weight bases, which we call extremal bases, for the adjoint representation of each simple Lie algebra 𝔤 of rank n: One construction for each simple root. We explicitly describe actions of the Chevalley generators on the basis elements. We show that these extremal bases are distinguished by their “supporting graphs” in three ways. (In general, the supporting graph of a weight basis for a representation of a semisimple Lie algebra is a directed graph with colored edges that describe the supports of the actions of the Chevalley generators on the elements of the basis.) We show that each extremal basis constructed is essentially the only basis with its supporting graph (i.e., each extremal basis is solitary), and that each supporting graph is a modular lattice. Each extremal basis is shown to be edge-minimizing: Its supporting graph has the minimum number of edges. The extremal bases are shown to be the only edge-minimizing as well as the only modular lattice weight bases (up to scalar multiples) for the adjoint representation of 𝔤. The supporting graph for an extremal basis is shown to be a distributive lattice if and only if the associated simple root corresponds to an end node for a “branchless” simple Lie algebra, i.e., type A, B, C, F, or G. For each extremal basis, basis elements for the Cartan subalgebra are explicitly expressed in terms of the h _i Chevalley generators.     

On the toughness index of planar graphs

The toughness indexτ(G) of a graph G is defined to be the largest integer t such that for any S ? V(G) with |S| > t, c(G - S) < |S| - t, where c(G - S) denotes the number of components of G - S. In particular, 1-tough graphs are exactly those graphs for which τ(G) ≥ 0. In this paper, it is shown that if G is a planar graph, then τ(G) ≥ 2 if and only if G is 4-connected. This result suggests that there may be a polynomial-time algorithm for determining whether a planar graph is 1-tough, even though the problem for general graphs is NP-hard. The result can be restated as follows: a planar graph is 4-connected if and only if it remains 1-tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4-connected planar graph yields a Hamiltonian graph.     

On the Distribution of the Sums of Binomial Coefficients Modulo a Prime

 Let be the binomial coefficient modulo b (b prime), with if l is greater than c, and let be the sum of binomial coefficients modulo b, that is (mod b). We prove the following property: the for which the couples c, l verify and are uniformly distributed in the residue classes modulo b as n tends to infinity. The method, using the Perron-Frobenius theory, applies also to and gives a new proof of the well known result for the non-zero binomial coefficients modulo b. (Received 21 June 1999; in revised form 13 July 2000)     

An exact test of the accuracy of binary classification models based on the probability distribution of the average rank

We propose a new way to evaluate the discriminatory power of models that generate a continuous value as the basis for performing a binary classification task. Our hypothesis test uses the average rank of the k successes in the sample of size n, based on those continuous values. We derive the probability mass function for the average rank from the coefficients of a Gaussian polynomial distribution that results from randomly sampling k distinct positive integers, all n or less. The significance level of the test is found by counting the number of arrangements that produce average ranks more extreme than the one observed. Recursive relationships can be used to calculate the values necessary to compute the p-value. For large values of k and n, for which exact computation might be prohibitive, we present numerical results which indicate that the critical values of the distribution are nearly linear in n for a fixed k and that the coefficients of the linear relationships are nonlinear functions of k and the desired percentile. We develop regression models for those relationships to approximate the number of arrangements in order to make the test practical for large values of k and n.