Structural Gröbner Basis Detection

 We determine the computational complexity of deciding whether m polynomials in n variables have relatively prime leading terms with respect to some term order. This problem in NP-complete in general, but solvable in polynomial time in two different situations, when m is fixed and when n−m is fixed. Our new algorithm for the second case determines a candidate set of leading terms by solving a maximum matching problem. This reduces the problem to linear programming. Received: May 9, 1996; revised version: December 19, 1996     

An Inequality About the Largest Roots of a Polynomial

 We present an upper bound for the product of the k largest roots of a monic polynomial of degree n with complex coefficients. For that, we use the theory of compound matrices and the localization of the eigenvalues of matrices. Received: February 26, 1996; revised version: March 20, 1997     

Cryptanalysis of ‘Less Short’ RSA Secret Exponents

 In some applications of RSA, it is desirable to have a short secret exponent d. Wiener [6], describes a technique to use continued fractions (CF) in a cryptanalytic attack on an RSA cryptosystem having a ‘short’ secret exponent. Let n=p ⋅ q be the modulus of the system. In the typical case that G=gcd(p−1, q−1) is small. Wiener’s method will give the secret exponent d when d does not exceed (approximately) n ^1/4. Here, we describe a general method to compute the CF-convergents of the continued fraction expansion of the same number as in Wiener (which has denominator d ⋅ G) up to the point where the denominator of the CF-convergent exceeds approximately n ^1/4. When d<n ^1/4 this technique determines d, p, and q as does Wiener’s method. For larger values of d there is still information available on the secret key. An estimate is made of the remaining workload to determine d, p and q. Roughly speaking this workload corresponds to an exhaustive search for about 2r+8 bit, where r=ln₂ d/n ^1/4. Received: September 30, 1996; revised version: March 7, 1997     

Some Power Mappings with Low Differential Uniformity

 Differentially uniform power mappings of the form f (x)=x ^d over GF(p ⁿ ) are considered. We construct an infinite family of 2-uniform mappings in the binary case. In the nonbinary case we give two large families of k-uniform mappings with low values of k. We also show how to construct families of sequences from differentially 1-uniform power mappings, which have parameters as good as the best presently known comparable families of sequences. Received: November 4, 1996; revised version: February 14, 1997     

A Polynomial Representation of the Diffie-Hellman Mapping

 Let F _q be the finite field of order q and γ be an element of F _q of order d. The construction of an explicit polynomial of degree with the property for is described. In particular the exact degree and sparsity of f are determined. Received: February 8, 2001; revised version: August 8, 2002 Keywords: Diffie-Hellman cryptosystem, Polynomial interpolation, Degree, Sparsity. The work was partially supported by the Austrian Science Fund (FWF) under the project S8306-MAT     

Etude expérimentale du retrait du béton

Résumé Pour évaluer les déformations dues au retrait, on utilise couramment les valeurs indiquées par les normes existantes; toutefois, lorsque l'on effectue des mesures pendant une longue période, on constate que les déformations sont plus importantes que celles préconisées. Dans cet article, nous présentons des résultats expérimentaux pouvant être utilisés pour contr?ler la validité des modèles existants ou pour en développer de nouveaux, car nous avons pris en considération plusieurs paramètres. Pour décrire le retrait en fonction du temps des dessiccation, nous avons admis la fonction ɛ=a(t/b+t) ⁿ . Les coefficientsa, b etn ont été déterminés par la méthode des moindres carrés. Des mesures effectuées on peut tirer les conclusions suivantes: (i) le retrait final diminue lorsque le diamètre des échantillons augmente; (ii) le temps nécessaire pour atteindre la moitié du retrait final est, en première approximation, de la formet _1/2=A _ϕ+B _ϕ ²; (iii) l'exposantn augmente avec le diamètre et tend vers 1; la fonctionn=1−C e^−dϕ semble convenir; (iv) la différence entre le retrait des éprouvettes sciées ou moulées est négligeable; (v) pour un même volume de pate de ciment, le retrait est peu influencé par le rapport E/C; (vi) le superfluidifiant utilisé augmente faiblement le retrait mais cette augmentation est compensée par la diminution que l'on peut opérer sur le rapport E/C; (vii) le dosage en ciment n'influence pas le retrait lorsque l'ouvrabilité du béton est maintenue constante; (viii) la variabilité du retrait diminue fortement si des précautions sont prises pour mesurer les déformations pendant les premières minutes de dessiccation.

---

Summary The shrinkage of concrete is generally determined using the standards. When shrinkage is measured over a long period of time, deformation is found to be larger than predicted by the standards. Therefore it seems to be interesting to measure shrinkage on different samples for a relatively long period of time. In this paper, we do not suggest a new model, but present the experimental measurements that can be used to check or develop any model. Our samples are divided into five series according to the examined parameters: (I) cylinders with different diameters; (II) prism with different dimensions; (III) different quality of cement paste; (IV) concrete with same workability but different cement content; (V) variability. The following empirical Equation 1 was used to link shrinkage and time of drying: ɛ=a (t/b+t) ⁿ . The coefficientsa, b andn were fitted using the least-square method. This allows us to see the influence of some factors on shrinkage. All samples were cast using the same aggregates and the same cement type (CPN). In some cases we also used a superplasticizer. Both axial and superficial shrinkage have been measured. As the data seem to fit correctly Equation 1 the following conclusions can be drawn: the final shrinkage,a, is decreasing linearly with increasing diameter. The slope depends on the concrete mixture. It is obvious that for a large diameter final shrinkage will reach an asymptotic line; the timet _1/2 needed to obtain half of the final shrinkage is increasing with the diameter ϕ and, as a first approximation, we gett _1/2=Aϕ+Bϕ²; therefore the theory of diffusion does not apply for small diameters; the coefficientn increases also with the diameter, it reaches asymptotically the value of 1. It varies between 0.45 and 0.8 as seen by our measurements, and the functionn=1−C e^−dϕ fits correctly. If we assume that Equation 1 describes realistically the behaviour of concrete during drying, the coefficientsa andn should not vary with the sample dimension. We should not forget that shrinkage is a complex phenomenon and therefore cannot be described by such a simple equation. From our measurement we can draw the following conclusions: (i) there is no significant difference between the shrinkage of samples cast or sawed; (ii) when the volume of cement paste is constant, shrinkage is almost uninfluenced by the W/C ratio; (iii) the superplasticizer increases shrinkage slightly, but this increase is compensated by the decrease in W/C ratio; (iv) the cement content does not influence the shrinkage, if the workability is constant; (v) variability can be drastically reduced when precautions are taken to measure deformation during the first minutes of drying.

     

Modeling curved interfaces without element-partitioning in the extended finite element method

In this paper, we model holes and material interfaces (weak discontinuities) in two-dimensional linear elastic continua using the extended finite element method on higher-order (spectral) finite element meshes. Arbitrary parametric curves such as rational Bézier curves and cubic Hermite curves are adopted in conjunction with the level set method to represent curved interfaces. Efficient computation of weak form integrals with polynomial integrands is realized via the homogeneous numerical integration scheme—a method that uses Euler's homogeneous function theorem and Stokes' theorem to reduce integration to the boundary of the domain. Numerical integration on cut elements requires the evaluation of a one-dimensional integral over a parametric curve, and hence, the need to partition curved elements is eliminated. To improve stiffness matrix conditioning, ghost penalty stabilization and the Jacobi preconditioner are used. For material interface problems, we develop an enrichment function that captures weak discontinuities on spectral meshes. Taken together, we show through numerical experiments that these advances deliver optimal algebraic rates of convergence with h-refinement (p=1,2,…,5) and exponential rates of convergence with p-refinement (p=1,2,…,7) for elastostatic problems with holes and material inclusions on Cartesian pth-order spectral finite element meshes.     

On the Time–Space Complexity of Geometric Elimination Procedures

In [25] and [22] a new algorithmic concept was introduced for the symbolic solution of a zero dimensional complete intersection polynomial equation system satisfying a certain generic smoothness condition. The main innovative point of this algorithmic concept consists in the introduction of a new geometric invariant, called the degree of the input system, and the proof that the most common elimination problems have time complexity which is polynomial in this degree and the length of the input. In this paper we apply this algorithmic concept in order to exhibit an elimination procedure whose space complexity is only quadratic and its time complexity is only cubic in the degree of the input system. Received: April 14, 1999; revised version: October 31, 2000     

Resolvent Representation for Regular Differential Ideals

 We show that the generic zeros of a differential ideal [A]:H ^∞ _A defined by a differential chain A are birationally equivalent to the general zeros of a single regular differential polynomial. This provides a generalization of both the cyclic vector construction for system of linear differential equations and the rational univariate representation of algebraic zero dimensional radical ideals. In order to achieve generality, we prove new results on differential dimension and relative orders which are of independent interest. Received: June 13, 2001; revised version: May 2, 2002 Key words: Differential algebra, Differential primitive element, Cyclic vector, Computer algebra, Resolvent.     

Solvable Brioschi Resolvents

 The Brioschi resolvent y ⁵ −10Zy ³ +45Z ² y−Z ² is a key component of an algorithm for calculating the roots of a general quintic polynomial. It is obtained from the general quintic polynomial by applying two Tschirnhausen transformations. In this paper it is shown that if the quintic polynomial is a solvable polynomial, then its associated parameter Z in the Brioschi resolvent satisfies Z=g(t) where g(t) is a rational function in ℚ(t) and t is chosen from an appropriate field. Received: July 23, 2001; revised version: October 14, 2002 Keywords: Solvable quintic, Brioschi quintic, resolvent sextic, parametrization. The author was supported by a research grant from the Natural Sciences and Engineering Research Council of Canada     

Organizing distributed data bases for parallel searching

Abstract

This paper is mainly concerned with the problem of distributing a data base (i.e., a set of segments) in a computer network system so as to facilitate parallel searching. In our distributed data base model, we assume that all segments are stored in nodes. Each time a query occurs, all nodes are searched concurrently. For convenience, we define the time required to access a segment from any node as a time unit. For a network with d nodes, the response time of a query is then identical to the maximum (n ₁ , n ₂, …, n_d ), where n_i , is the number of segments that satisfies the query and is stored in node i. Unfortunately, the solution for finding an optimal way to organize a distributed data base for parallel searching is still at large. In other words, given a data base, there is no efficient polynomial time algorithm for finding an optimal arrangement of segments onto nodes. In this article, we shall present a “heuristic algorithm” based upon a multivariant analysis method in statistics to distribute a data base in a network system. Some experimental results will show that our method is indeed feasible and effective.     

Developing Strategic Alliances: A Framework for Collaborative Negotiation in Design

This work applies a theory-based framework of collaborative negotiation to some of the disputes that regularly arise during group design. Although the framework was developed to provide general support for group work, this paper focuses on its use as a design tool. The framework, embodied in our system NegotiationLens, has four facets. It: 1. Provides a negotiation method intended to produce gain for all parties. 2. Provides an efficient process for conflict resolution. 3. Develops working alliances. 4. Lets parties decide quickly when they should go their separate ways. The framework produces the above results by: • Helping parties develop well-reasoned and clearly articulated points of view (Adelson and Jordan, 1991; Conklin and Yakemovic, 1991; Conklin and Begeman, 1988; MacLean et al ., 1991). • Creating a context of committment and respect. • Moving negotiating parties away from an adversarial stance and into a collaboration. • Allowing joint construction of solutions that are more beneficial than the unilateral solutions each party initially brought to the table. We present our framework for collaborative negotiation, describe NegotiationLens, and present two cases in which it was used. We present a third case, a large design project with recurrent design conflicts, and argue how NegotiationLens could have been of benefit there.     

Algorithms for Computing Sparse Shifts for Multivariate Polynomials

In this paper, we investigate the problem of finding t-sparse shifts for multivariate polynomials. Given a polynomial f∈ℱ[x ₁, x ₂, …, x _n ] of degree d, and a positive integer t, we consider the problem of representing f(x) as a ?-linear combination of the power products of u _i where u _i = x _i −b _i for some b _i ∈?, an extension of ℱ, for i = 1, …, n, i.e., f = ∑ _j F _j u ^αj , in which at most t of the F _j are non-zero. We provide sufficient conditions for uniqueness of sparse shifts for multivariate polynomials, prove tight bounds on the degree of the polynomial being interpolated in terms of the sparsity bound t and a bound on the size of the coefficients of the polynomial in the standard representation, and describe two new efficient algorithms for computing sparse shifts for a multivariate polynomial. Received: January 30, 1996; revised version: January 15, 2000     

Lattice Structure and Linear Complexity of Nonlinear Pseudorandom Numbers

 It is shown that a q-periodic sequence over the finite field F _q passes an extended version of Marsaglia's lattice test for high dimensions if and only if its linear complexity is large. The consequences of this result for nonlinear and inversive pseudorandom number generators are worked out. Received: October 2, 2001 Keywords: Pseudorandom number generator, Nonlinear method, Inversive method, Linear complexity, Marsaglia's lattice test.     

On Intrinsic Bounds in the Nullstellensatz

 Let k be a field and  f ₁, . . . ,  f _s be non constant polynomials in k[X ₁, . . . , X _n ] which generate the trivial ideal. In this paper we define an invariant associated to the sequence  f ₁, . . . ,  f _s : the geometric degree of the system. With this notion we can show the following effective Nullstellensatz: if δ denotes the geometric degree of the trivial system  f ₁, . . . ,  f _s and d :=max _j  deg( f _j ), then there exist polynomials p ₁, . . . , p _s ∈k[X ₁, . . . , X _n ] such that 1=∑ _j  p _j  f _j and deg p _j   f _j ≦3n ²δd. Since the number δ is always bounded by (d+1) ^n-1 , one deduces a classical single exponential upper bound in terms of d and n, but in some cases our new bound improves the known ones. Received November 24, 1995, revised version January 19, 1996     

Numerical analyses for the prediction of the splitting strength of beams loaded perpendicular-to-grain by dowel-type connections

The paper presents a parametric numerical study on the splitting strength of timber beams loaded perpendicular-to-grain by dowel-type connections. The main aims of the numerical investigations are: (1) find out the influence of main connection parameters on the splitting strength of beams; (2) compare the above evaluated influences with the ones proposed by the first author in a recently developed semi-empirical prediction formula. The first part of the paper presents the mentioned new semi-empirical prediction formula which has been developed by means of a survey on experimental data from literature. The formula is presented in its main aspects and later its prediction capability is discussed and compared with the ones of formulae embodied in new European and German design codes for timber structures. The second part of the paper reports the main results of parametric numerical analyses carried out in the framework of Linear Elastic Fracture Mechanics (LEFM) by means of a crack propagation approach. The analyses are performed on beams of different size loaded at mid-span by both single and multiple dowel connections. The main investigated parameters are the connection width (l _r), the connection depth (h _m), and the number of rows of fasteners (n). They are analysed for different beam heights (h) and for different distances of the most distant row of fasteners from beam loaded edge (h _e). The numerical results are compared with available experimental test data and with the relationships embodied in the above-mentioned semi-empirical prediction formula.

---

Résumé L’article présente les résultats d’une étude numérique paramétrique qui analyse la résistance à la fissuration de poutres en bois chargées perpendiculairement aux fibres de connexions, avec des connecteurs cylindriques. Le but principal de cette étude numérique est: (1) déterminer l’influence des paramètres principaux des connexions sur la résistance à fissuration des poutres; (2) comparer les résultats obtenus avec les résultats proposés par Ballerini dans une formule récente de prédiction semi-empirique. La première partie de l’article présente la formula citée de prédiction semi-empirique développée sur base d’une analyse des données expérimentales disponibles dans le texte. La formule est illustrée dans ses aspects principaux et par la suite sa capacité prévisible est comparée avec celle des formules adoptées par les récentes normes européennes et allemandes pour les structures en bois. La seconde partie de l’article reprend les principaux résultats de l’analyse numérique paramétrique développés dans le domaine de la Mécanique de la Fracture Linéaire Elastique (LEFM) à l’aide d’analyses avec propagation de fissure. Les analyses concernent des poutres de différentes dimensions chargées en ligne de connexions avec un ou plusieurs connecteurs cylindriques. Les paramètres principaux étudiés sont la largeur (l_r), la hauteur (h_m) et le nombre de lignes des connecteurs (n) de la connexion. Les analyses concernaient des poutres de différentes hauteurs (h) et placés à différentes distances par rapport au bord des poutres de la ligne des connecteurs plus éloignée (h_e). Les résultats numériques sont comparés avec les données expérimentales disponibles et les études prévues par la formule citée de prédiction semi-empirique.

     

On Tanner Codes: Minimum Distance and Decoding

 A bound on the minimum distance of Tanner codes / expander codes of Sipser and Spielman is obtained. Furthermore, a generalization of a decoding algorithm of Zémor to Tanner codes is presented. The algorithm can be implemented using the same complexity as that of Zémor and has a similar error-correction capability. Explicit families of Tanner codes are presented for which the decoding algorithm is applicable. Received: March 2, 2001; revised version: November 28, 2001 Key words: Tanner codes, Expander codes, LDPC codes, Decoding, Minimum distance, Expander graphs, Ramanujan graphs, N-gons, Multi-partite graphs.     

Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields

A depth 3 arithmetic circuit can be viewed as a sum of products of linear functions. We prove an exponential complexity lower bound on depth 3 arithmetic circuits computing some natural symmetric functions over a finite field F. Also, we study the complexity of the functions f : D ⁿ →F for subsets D⊂F. In particular, we prove an exponential lower bound on the complexity of depth 3 arithmetic circuits computing some explicit functions f:(F ^*) ⁿ →F (in particular, the determinant of a matrix). Received: July 7, 1998; revised version: January 13, 2000