A Nonoverlapping Domain Decomposition Method for Legendre Spectral Collocation Problems

We consider the Dirichlet boundary value problem for Poisson’s equation in an L-shaped region or a rectangle with a cross-point. In both cases, we approximate the Dirichlet problem using Legendre spectral collocation, that is, polynomial collocation at the Legendre–Gauss nodes. The L-shaped region is partitioned into three nonoverlapping rectangular subregions with two interfaces and the rectangle with the cross-point is partitioned into four rectangular subregions with four interfaces. In each rectangular subregion, the approximate solution is a polynomial tensor product that satisfies Poisson’s equation at the collocation points. The approximate solution is continuous on the entire domain and its normal derivatives are continuous at the collocation points on the interfaces, but continuity of the normal derivatives across the interfaces is not guaranteed. At the cross point, we require continuity of the normal derivative in the vertical direction. The solution of the collocation problem is first reduced to finding the approximate solution on the interfaces. The discrete Steklov–Poincaré operator corresponding to the interfaces is self-adjoint and positive definite with respect to the discrete inner product associated with the collocation points on the interfaces. The approximate solution on the interfaces is computed using the preconditioned conjugate gradient method. A preconditioner is obtained from the discrete Steklov–Poincaré operators corresponding to pairs of the adjacent rectangular subregions. Once the solution of the discrete Steklov–Poincaré equation is obtained, the collocation solution in each rectangular subregion is computed using a matrix decomposition method. The total cost of the algorithm is O(N ³), where the number of unknowns is proportional to N ².      

Pressure drop of gas–liquid Taylor flow in round micro-capillaries for low to intermediate Reynolds numbers

In this paper, a model is presented that describes the pressure drop of gas–liquid Taylor flow in round capillaries with a channel diameter typically less than 1 mm. The analysis of Bretherton (J Fluid Mech 10:166–188, 1961) for the pressure drop over a single gas bubble for vanishing liquid film thickness is extended to include a non-negligible liquid film thickness using the analysis of Aussillous and Quéré (Phys Fluids 12(10):2367–2371, 2000). This result is combined with the Hagen–Poiseuille equation for liquid flow using a mass balance-based Taylor flow model previously developed by the authors (Warnier et al. in Chem Eng J 135S:S153–S158, 2007). The model presented in this paper includes the effect of the liquid slug length on the pressure drop similar to the model of Kreutzer et al. (AIChE J 51(9):2428–2440, 2005). Additionally, the gas bubble velocity is taken into account, thereby increasing the accuracy of the pressure drop predictions compared to those of the model of Kreutzer et al. Experimental data were obtained for nitrogen–water Taylor flow in a round glass channel with an inner diameter of 250 μm. The capillary number Ca _gl varied between 2.3 × 10⁻³ and 8.8 × 10⁻³ and the Reynolds number Re _gl varied between 41 and 159. The presented model describes the experimental results with an accuracy of ±4% of the measured values.     

Analyse numerique du probleme des ondes longues en eau peu profonde

This paper deals with the study of the problem of long waves in shallow water, when viscesity is taken into account. Existence and uniqueness of the solution are established. For the numerical treatment, an implicit scheme is proposed together with results of stability and convergence.

---

---

Le présent travail a été réalisé au Laboratoire de Matématiques Appliquees de l'Université Scientitique et Médicale de Grenoble (France).     

Lower Bounds for Kernelizations and Other Preprocessing Procedures

We first present a method to rule out the existence of parameter non-increasing polynomial kernelizations of parameterized problems under the hypothesis P≠NP. This method is applicable, for example, to the problem Sat parameterized by the number of variables of the input formula. Then we obtain further improvements of corresponding results in (Bodlaender et al. in Lecture Notes in Computer Science, vol. 5125, pp. 563–574, Springer, Berlin, 2008; Fortnow and Santhanam in Proceedings of the 40th ACM Symposium on the Theory of Computing (STOC’08), ACM, New York, pp. 133–142, 2008) by refining the central lemma of their proof method, a lemma due to Fortnow and Santhanam. In particular, assuming that the polynomial hierarchy does not collapse to its third level, we show that every parameterized problem with a “linear OR” and with NP-hard underlying classical problem does not have polynomial self-reductions that assign to every instance x with parameter k an instance y with |y|=k ^O(1)⋅|x|^1−ε (here ε is any given real number greater than zero). We give various applications of these results. On the structural side we prove several results clarifying the relationship between the different notions of preprocessing procedures, namely the various notions of kernelizations, self-reductions and compressions.     

Nouvelle méthode pour améliorer la précision du premier harmonique†

In this paper, we give first a contribution to the ‘dual input describing function’ of West et al. (1956); we show how it is possible to define by means of the characteristic curve of the non-linearity alone, without knowing the mathematical expression for it. Secondly, we give a new method for determining the self-oscillation of a non-linear system dependent on reactive energy considerations. Lastly, we extend the theory to non-linear multivariable systems.

On donne une contribution à la notion de ‘double fonetion de transfert équivalente’ de West et al. (1956), et on montre comment il est possible déterminer uniquement à l'aide de la courbe de gain g(x), sans connaicirc;tre son expression mathématique. On donne une nouvelle méthode pour améliorer la précision du premier harmonique, basée sur des considérations relatives à l'énergie réactive du systéme.     

Recursivite et cones rationnels fermes par intersection

Resume Nous définissons les grammaires quasi-commutatives en modifiant légérement la definition des grammaires commutatives introduites par Crespi-Reghizzi et Mandrioli [5]. Nous obtenons, ainsi, une caractérisation grammaticale de , le plus petit c?ne rationnel clos par intersection et contenantD ₁′^*, le langage de semi-Dyck sur une lettre. Nous en déduisons que tout langage de (D ₁′*)est récursif. A l'aide d'une généralisation des ?Vector Addition Systems?, nous démontrons, ensuite, le même résultat pour les langages de , le plus petit c?ne rationnel clos par étoile et intersection, contenant le langage formé de tous les préfixes des mots deD ₁′.     

BOSS QUATTRO: an open system for parametric design

During the two past decades, engineers have shown growing interest in automatic structural optimization techniques. These were first used to solve analytical problems and were then rapidly adapted to structural sizing problems coupled to finite element analysis software. Moreover, shape optimization problems featuring complex CAD systems were addressed in the early 90’s. This article describes the capabilities of the optimization product developed by SAMTECH S.A. in Liège, Belgium. One will read here what led the company and a group of research engineers at LTAS (Laboratoire des Techniques Aéronautiques et Spatiales, Université de Liège) to the achievement of a so-called open system for parametric design. The BOSS/Quattro package is a general-purpose design program. It includes several “engines”: optimization, parametric studies, “Monte-Carlo” studies, “design of experiments” and updating. It is interesting to note that the “engines” can be easily mixed through the graphical user interface (GUI), and, this, with several analysis models. Received December 30, 2000     

On the Planar Piecewise Quadratic 1-Center Problem

In this paper we introduce a minimax model unifying several classes of single facility planar center location problems. We assume that the transportation costs of the demand points to the serving facility are convex functions {Q _i }, i=1,…,n, of the planar distance used. Moreover, these functions, when properly transformed, give rise to piecewise quadratic functions of the coordinates of the facility location. In the continuous case, using results on LP-type models by Clarkson (J. ACM 42:488–499, 1995), Matoušek et al. (Algorithmica 16:498–516, 1996), and the derandomization technique in Chazelle and Matoušek (J. Algorithms 21:579–597, 1996), we claim that the model is solvable deterministically in linear time. We also show that in the separable case, one can get a direct O(nlog n) deterministic algorithm, based on Dyer (Proceedings of the 8th ACM Symposium on Computational Geometry, 1992), to find an optimal solution. In the discrete case, where the location of the center (server) is restricted to some prespecified finite set, we introduce deterministic subquadratic algorithms based on the general parametric approach of Megiddo (J. ACM 30:852–865, 1983), and on properties of upper envelopes of collections of quadratic arcs. We apply our methods to solve and improve the complexity of a number of other location problems in the literature, and solve some new models in linear or subquadratic time complexity.     

Teoremi di confronto per gli zeri di polinomis-ortogonali

Sommaire Dans cette note on donne des théorèmes généraux qui permettent la comparaison entre les zéros des polyn?mess-orthogonaux, relatifs à fonctions poidsp _x (x),p ₀ (x), pour les quelles le rapportp ₁ (x)/p _o(x) est une fonction strictement monotone sur un certain intervalle. Ces thèorèmes, utilisés à propos, permettent d'établir des inégalités entre les zéros des polynomess-orthogonaux relatifs aux fonctions poids de type Jacobi,p(x)=(1-x)^α (1+x)^β), α, β>−1,x∈]−1,1[; inégalités qui sont connues seulement pour des valeurs particuliers de α,β,s, et du degrém du polynome.     

The octagon abstract domain

This article presents the octagon abstract domain, a relational numerical abstract domain for static analysis by abstract interpretation. It allows representing conjunctions of constraints of the form ± X ± Y ≤ c where X and Y range among program variables and c is a constant in ℤ, ℚ, or ℝ automatically inferred. Abstract elements are represented using modified Difference Bound Matrices and we use a normalization algorithm loosely based on the shortest-path closure to compute canonical representations and construct best-precision abstract transfer functions. We achieve a quadratic memory cost per abstract element and a cubic worst-case time cost per abstract operation, with respect to the number of program variables. In terms of cost and precision, our domain is in between the well-known fast but imprecise interval domain and the costly polyhedron domain. We show that it is precise enough to treat interesting examples requiring relational invariants, and hence, out of the reach of the interval domain. We also present a packing strategy that allows scaling our domain up to large programs by tuning the amount of relationality. The octagon domain was incorporated into the ASTRéE industrial-strength static analyzer and was key in proving the absence of run-time errors in large critical embedded flight control software for Airbus planes. This paper is the journal version of an earlier conference paper [44] sharing this title. However, the present version, extracted from the author’s PhD [46] is extended in many ways and enriched with new experimental results. Partially supported by the exploratory project ASTRéE of the Réseau National de recherche et d’innovation en Technologies Logicielles (RNTL).     

A permuted factors approach for the linearization of polynomial matrices

In Antoniou and Vologiannidis (Electron J Linear Algebra 11:78–87, 2004; 15:107–114, 2006), a new family of companion forms associated with a regular polynomial matrix T (s) has been presented, using products of permutations of n elementary matrices, generalizing similar results presented in Fiedler (Linear Algebra Its Appl 371:325–331, 2003) where the scalar case was considered. In this paper, extending this “permuted factors” approach, we present a broader family of companion-like linearizations, using products of up to n(n−1)/2 elementary matrices, where n is the degree of the polynomial matrix. Under given conditions, the proposed linearizations can be shown to consist of block entries where the coefficients of the polynomial matrix appear intact. Additionally, we provide a criterion for those linearizations to be block symmetric. We also illustrate several new block symmetric linearizations of the original polynomial matrix T (s), where in some of them the constraint of nonsingularity of the constant term and the coefficient of maximum degree are not a prerequisite.     

Polynomial expansion of symmetric boolean functions by the table method

Conclusion The proposed method for polynomial expansion of SBF based on construction of the triangular tableT _n(π(F)) of local codes of its derivatives has the lowest computational complexity among known methods. Constructing the table only once, the method easily determines all the “residual” functions ϑ _rl ^km for various expansion parametersk andm. Another advantage of the method is its applicability for polynomial expansion of arbitrary BF and partially symmetric BF. In this case, the base of the “triangle” is the truth table of the arbitrary BF or the local code (including convolved local code) of the partially symmetric BF. The method can be successfully used for the synthesis of a wide class of digital networks. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 59–71, November–December, 1996.     

Improved Approximation Results for the Minimum Energy Broadcasting Problem

In this paper we present new results on the performance of the Minimum Spanning Tree heuristic for the Minimum Energy Broadcast Routing (MEBR) problem. We first prove that, for any number of dimensions d≥2, the approximation ratio of the heuristic does not increase when the power attenuation coefficient α, that is the exponent to which the coverage distance must be raised to give the emission power, grows. Moreover, we show that, for any fixed instance, as a limit for α going to infinity, the ratio tends to the lower bound of Clementi et al. (Proceedings of the 18th annual symposium on theoretical aspects of computer science (STACS), pp. 121–131, 2001), Wan et al. (Wirel. Netw. 8(6):607–617, 2002) given by the d-dimensional kissing number, thus closing the existing gap between the upper and the lower bound. We then introduce a new analysis allowing to establish a 7.45-approximation ratio for the 2-dimensional case, thus significantly decreasing the previously known 12 upper bound (Wan et al. in Wirel. Netw. 8(6):607–617, 2002) (actually corrected to 12.15 in Klasing et al. (Proceedings of the 3rd IFIP-TC6 international networking conference, pp. 866–877, 2004)). Finally, we extend our analysis to any number of dimensions d≥2 and any α≥d, obtaining a general approximation ratio of 3 ^d −1, again independent of α. The improvements of the approximation ratios are specifically significant in comparison with the lower bounds given by the kissing numbers, as these grow at least exponentially with respect to d. The research was partially funded by the European project COST Action 293, “Graphs and Algorithms in Communication Networks” (GRAAL). Preliminary version of this paper appeared in Flammini et al. (Proceedings of ACM joint workshop on foundations of mobile computing (DIALM-POMC), pp. 85–91, 2004).     

Sur les cycles élémentaires dans les graphes et hypergraphesk-chromatiques

Résumé Le but de ce travail est celui d'obtenir une borne inférieure de la longueur des plus longues cycles élémentaires pour un graphe ou un hypergraphe de nombre chromatique donné. Ainsi on démontre que tout graphe qui n'a pas (r+1)-cliques, de degré minimal ≥d (ou de nombre chromatiqued+1) contient un cycle élémentaire de longueur ≥rd/(r−1) et tout hypergrapheH de nombre chromatique χ(H)=k contient un cycle élémentaire de longueur ≥k. On obtient aussi que tout grapheG de nombre chromatique γ(G)=k≥3 qui n'a pas de triangles contient un cycle élémentaire de longueur ≥2k−1, résultat qui est généralisé sous la forme suivante: Si le grapheG de degré minimal ≥d est 2-connexe et ne contient pas de triangles, alorsG=K _d,d′ oùd′≥d, ouG contient un cycle élémentaire de longueur ≥2d+1. On déduit que tout grapheG avec γ(G)=k≥3, qui n'a pask-cliques contient un cycle élémentaire de longueur ≥k+2, cette borne étant atteinte.

---

The aim of this paper is that to obtain a lower bound of the length of the longest elementary cycles of ak-chromatic graph or hypergraph. It is proved that any graph without (r+1)-cliques, having the minimal degree of its vertices ≥d (or the chromatic number equal tod+1) has an elementary cycle of length ≥rd/(r−1) and any hypergraphH of chromatic number χ(H)=k has an elementary cycle of length ≥k. It is obtained also that any graphG without triangles, having chromatic number γ(G)=k≥3 contains an elementary cycle of length ≥2k−1. This result is generalized in the following way: IfG is 2-connected, has minimal degree ≥d and contains no triangle, thenG=K _d,d′ withd′≥d orG has an elementary cycle of length ≥2d+1. It is derived that any graphG with γ(G)=k≥3 which does not containk-cliques has an elementary cycle of length ≥k+2, this bound being attained.

     

Efficiently Testing Sparse <Emphasis Type="Italic">GF</Emphasis>(2) Polynomials

We give the first algorithm that is both query-efficient and time-efficient for testing whether an unknown function f:{0,1} ⁿ →{−1,1} is an s-sparse GF(2) polynomial versus ε-far from every such polynomial. Our algorithm makes poly(s,1/ε) black-box queries to f and runs in time n⋅poly(s,1/ε). The only previous algorithm for this testing problem (Diakonikolas et al. in Proceedings of the 48th Annual Symposium on Foundations of Computer Science, FOCS, pp. 549–558, 2007) used poly(s,1/ε) queries, but had running time exponential in s and super-polynomial in 1/ε.     

Uncertainty,belief, and probability1

We introduce a new probabilistic approach to dealing with uncertainty, based on the observation that probability theory does not require that every event be assigned a probability. For a nonmeasurable event (one to which we do not assign a probability), we can talk about only the inner measure and outer measure of the event. In addition to removing the requirement that every event be assigned a probability, our approach circumvents other criticisms of probability-based approaches to uncertainty. For example, the measure of belief in an event turns out to be represented by an interval (defined by the inner and outer measures), rather than by a single number. Further, this approach allows us to assign a belief (inner measure) to an event E without committing to a belief about its negation -E (since the inner measure of an event plus the inner measure of its negation is not necessarily one). Interestingly enough, inner measures induced by probability measures turn out to correspond in a precise sense to Dempster-Shafer belief functions. Hence, in addition to providing promising new conceptual tools for dealing with uncertainty, our approach shows that a key part of the important Dempster-Shafer theory of evidence is firmly rooted in classical probability theory. Cet article présente une nouvelle approche probabiliste en ce qui concerne le traitement de l'incertitude; celle-ci est basée sur l'observation que la théorie des probabilityés n'exige pas qu'une probabilityé soit assignée à chaque événement. Dans le cas d'un événement non mesurable (un événement pour lequel on n'assigne aucune probabilityé), nous ne pouvons discuter que de la mesure intérieure et de la mesure extérieure de l'évenément. En plus d'éliminer la nécessité d'assigner une probabilityéà l'événement, cette nouvelle approche apporte une réponse aux autres critiques des approches à l'incertitude basées sur des probabilityés. Par exemple, la mesure de croyance dans un événement est représentée par un intervalle (défini par la mesure intérieure et extérieure) plutǒt que par un nombre unique. De plus, cette approche nous permet d'assigner une croyance (mesure intérieure) à un événement E sans se compromettre vers une croyance à propos de sa négation -E (puisque la mesure intérieure d'un événement et la mesure intérieure de sa négation ne sont pas nécessairement une seule et unique mesure). II est intéressant de noter que les mesures intérieures qui résultent des mesures de probabilityé correspondent d'une manière précise aux fonctions de croyance de Dempster-Shafer. En plus de constituer un nouvel outil conceptuel prometteur dans le traitement de l'incertitude, cette approche démontre qu'une partie importante de la théorie de l'évidence de Dempster-Shafer est fermement ancrée dans la theorie classique des probabilityés.     

New Algorithms for Polynomial J-Spectral Factorization

In this paper new algorithms are developed for J-spectral factorization of polynomial matrices. These algorithms are based on the calculus of two-variable polynomial matrices and associated quadratic differential forms, and share the common feature that the problem is lifted from the original one-variable polynomial context to a two-variable polynomial context. The problem of polynomial J-spectral factorization is thus reduced to a problem of factoring a constant matrix obtained from the coefficient matrices of the polynomial matrix to be factored. In the second part of the paper, we specifically address the problem of computing polynomial J-spectral factors in the context of H _∞ control. For this, we propose an algorithm that uses the notion of a Pick matrix associated with a given two-variable polynomial matrix. Date received: January 1, 1998. Date revised: October 15, 1998.     

Approximation Algorithms for Reconstructing the Duplication History of Tandem Repeats

Computing the duplication history of a tandem repeated region is an important problem in computational biology (Fitch in Genetics 86:623–644, 1977; Jaitly et al. in J. Comput. Syst. Sci. 65:494–507, 2002; Tang et al. in J. Comput. Biol. 9:429–446, 2002). In this paper, we design a polynomial-time approximation scheme (PTAS) for the case where the size of the duplication block is 1. Our PTAS is faster than the previously best PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002). For example, to achieve a ratio of 1.5, our PTAS takes O(n ⁵) time while the PTAS in Jaitly et al. (J. Comput. Syst. Sci. 65:494–507, 2002) takes O(n ¹¹) time. We also design a ratio-6 polynomial-time approximation algorithm for the case where the size of each duplication block is at most 2. This is the first polynomial-time approximation algorithm with a guaranteed ratio for this case. Part of work was done during a Z.-Z. Chen visit at City University of Hong Kong.