The Computational Complexity of the Chow Form

We present a bounded probability algorithm for the computation of the Chowforms of the equidimensional components of an algebraic variety. In particular, this gives an alternative procedure for the effective equidimensional decomposition of the variety, since each equidimensional component is characterized by its Chow form. The expected complexity of the algorithm is polynomial in the size and the geometric degree of the input equation system defining the variety. Hence it improves (or meets in some special cases) the complexity of all previous algorithms for computing Chow forms. In addition to this, we clarify the probability and uniformity aspects, which constitutes a further contribution of the paper. The algorithm is based on elimination theory techniques, in line with the geometric resolution algorithm due to M. Giusti, J. Heintz, L. M. Pardo, and their collaborators. In fact, ours can be considered as an extension of their algorithm for zero-dimensional systems to the case of positive-dimensional varieties. The key element for dealing with positive-dimensional varieties is a new Poisson-type product formula. This formula allows us to compute the Chow form of an equidimensional variety from a suitable zero-dimensional fiber. As an application, we obtain an algorithm to compute a subclass of sparse resultants, whose complexity is polynomial in the dimension and the volume of the input set of exponents. As another application, we derive an algorithm for the computation of the (unique) solution of a generic overdetermined polynomial equation system.     

Homogeneous quaternionic Kähler structures of linear type

A classification of homogeneous quaternionic Kähler structures by real tensors is given and related to Fino's representation theoretic decomposition. A relationship between the modules whose dimension grows linearly and quaternionic hyperbolic space is found. To cite this article: M. Castrillón López et al., C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Equilibrium States in the Quadruple–Kerr Solution

The extended quadruple–Kerr metric is used to consider equilibrium states of four collinear Kerr particles. We explain our previous failure to solve numerically the full set of the balance equations, and we derive a self–consistent system of the axis conditions leading to the equilibrium of all four constituents which can be black holes or hyperextreme objects. The equilibrium configurations obtained in this paper exhibit similar features with those occurring in the systems of two Kerr particles, for instance, the balance of four Kerr black holes with positive masses does not seem possible. Equilibrium states of two identical compound Kerr objects are also discussed.     

A technique to construct symmetric variable-stepsize linear multistep methods for second-order systems

Some previous works show that symmetric fixed- and variable-stepsize linear multistep methods for second-order systems which do not have any parasitic root in their first characteristic polynomial give rise to a slow error growth with time when integrating reversible systems. In this paper, we give a technique to construct variable-stepsize symmetric methods from their fixed-stepsize counterparts, in such a way that the former have the same order as the latter. The order and symmetry of the integrators obtained is proved independently of the order of the underlying fixed-stepsize integrators. As this technique looks for efficiency, we concentrate on explicit linear multistep methods, which just make one function evaluation per step, and we offer some numerical comparisons with other one-step adaptive methods which also show a good long-term behaviour.

     

Corrigendum: The complexity of counting graph homomorphisms

We close a gap in the proof of Theorem 4.1 in our paper “The complexity of counting graph homomorphisms” [Random Structures Algorithms 17 (2000), 260–289]. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

Measurement of the dynamic elastic constants of short isotropic cylinders

A method based on a single test is proposed to characterize the elasticity of an isotropic homogeneous material in the shape of a cylinder of any slenderness (length-diameter) ratio. Firstly, the Rayleigh-Ritz method is used to determine the natural frequencies of the cylinders vibrating axisymmetrically. The study is focused on cylindrical samples with diameter and length of similar magnitude so that the shear modulus and the Poisson ratio can be calculated simultaneously. Subsequently, the theoretical results for cylinders of slenderness ratio between 0.1 and 3 are analyzed in order to obtain the data required to determine the elastic constants from one of the two lowest measured natural frequencies and their quotient. The analysis of the results demonstrates that any slenderness ratio is useful in the calculation of the elastic constants, although in some cases the third natural frequency should be used. Furthermore, the influence of the length-diameter quotient on the sensitivity of the method is analyzed by evaluating the systematic uncertainties for both dynamic elastic constants. Finally, the method is experimentally tested by characterizing two steel cylinders with slenderness ratios 0.1 and 1, respectively. The results demonstrate that uncertainties for both Poisson ratio and the shear modulus are smaller when the slenderness ratio is 1.     

Asymptotically balanced schemes for non-homogeneous hyperbolic systems – application to the Shallow Water equations

In this work we introduce a class of balanced numerical schemes, up to second order, for the solution of general non-homogeneous hyperbolic systems of conservation laws. We give a general technique to build such schemes. We also prove that they balance up to second order a large class of steady solutions in the whole domain but some subset whose measure tends to zero as the grid size decreases to zero. We finally present an application to Shallow Water equations that exhibit the good performances of some of the schemes introduced. To cite this article: T. Chacón Rebollo et al., C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Equivalence between mixed finite element and multi-point finite volume methods

We consider the lowest-order Raviart–Thomas mixed finite element method for elliptic problems on simplicial meshes in two or three space dimensions. This method produces saddle-point type problems for scalar and flux unknowns. We show how to easily eliminate the flux unknowns, which implies an equivalence between this method and a particular multi-point finite volume scheme, without any approximate numerical integration. We describe the stencil of the final matrix and give sufficient conditions for its symmetry and positive definiteness. We present a numerical example illustrating the performance of the proposed method. To cite this article: M. Vohralík, C. R. Acad. Sci. Paris, Ser. I 339 (2004).     

The Gross-Neveu model at finite temperature at next-to-leading order in the 1/N expansion

We present new results on the Gross-Neveu model at finite temperature and at next-to-leading order in the 1/N expansion. In particular, a new expression is obtained for the effective potential which is explicitly invariant under renormalization group transformations. The model is used as a playground to investigate various features of field theory at finite temperature. For example we verify that, as expected from general arguments, the cancellation of ultraviolet divergences takes place at finite temperature without the need for introducing counterterms beyond those of zero temperature. As well known, the discrete chiral symmetry of the (1+1)-dimensional model is spontaneously broken at zero temperature and restored, in leading order, at some temperature T_c; we find that the 1/N approximation breaks down for temperatures below T_c: as the temperature increases, the fluctuations become eventually too large to be treated as corrections, and a Landau pole invalidates the calculation of the effective potential in the vicinity of its minimum. Beyond T_c, the 1/N expansion becomes again regular: it predicts that in leading order the system behaves as a free gas of massless fermions and that, at the next-to-leading order, it remains weakly interacting. In the limit of large temperature, the pressure coincides with that given by perturbation theory with a coupling constant defined at a scale of the order of the temperature, as expected from asymptotic freedom.