Large strain solutions of rubber components

A Mooney-Rivlin material model for plane strain and axisymmetric analyses of rubber has been implemented in the ADINA computer code.

Using a consistent penalty method, derived from a regularized mixed formulation, the nonlinear incompressibility constraint is weakened by a properly chosen projection procedure. The hydrostatic pressure (proportional to the penalty function and discontinuous at interelement boundaries) may assume constant or linear elementwise variation, optimally matching the assumed displacement fields in four or nine node elements, respectively. Numerical studies on convergence rates and stability properties of pressure solutions give results that agree well with predictions made on the basis of the theory for the linear constraint case.

The code has been used in the practical design of a highly strained rubber diaphragm in a sheet metal forming press. The pressure load was kept perpendicular to deformed surfaces and the growth of contact areas between rubber and metal boundaries during the forming process was simulated by introducing successive constraints in repeated restart runs.     

Parameter and shape sensitivity of thermo-viscoelastic response

Gradient-based optimization methods are still most efficient methods for solving structural optimization problems. The sensitivity formulation has been one of the central issues in the gradient-based optimization algorithm. Thermo-viscoelastic constitutive and parameter sensitivity formulation are presented in this paper. The model considered is composed of two coupled subproblems: the transient heat transfer problem and a rheological, viscoelastic material model known in literature as the standard model. Design variables considered are with material and shape-defining parameters. The investigation includes a finite element formulation and implementation in an object-oriented finite element environment. Results of numerical analysis are presented.     

Approximating the Bandwidth of Caterpillars

A caterpillar is a tree in which all vertices of degree three or more lie on one path, called the backbone. We present a polynomial time algorithm that produces a linear arrangement of the vertices of a caterpillar with bandwidth at most O(log n/log log n) times the local density of the caterpillar, where the local density is a well known lower bound on the bandwidth. This result is best possible in the sense that there are caterpillars whose bandwidth is larger than their local density by a factor of Ω(log n/log log n). The previous best approximation ratio for the bandwidth of caterpillars was O(log n). We show that any further improvement in the approximation ratio would require using linear arrangements that do not respect the order of the vertices of the backbone. We also show how to obtain a (1+ε) approximation for the bandwidth of caterpillars in time . This result generalizes to trees, planar graphs, and any family of graphs with treewidth .     

Approximating CSG trees of moving objects

A discussion of the relationship between two solid representation schemes is presented: CSG trees and recursive spatial subdivision exemplified by the bintree, a generalization of the quadtree and octree. Detailed algorithms are developed and analyzed for evaluating CSG trees by bintree conversion. These techniques are shown to enable the addition of the time dimension and motion to the approximate analysis of CSG trees. This facilitates the solution of problems such as static and dynamic interference detection. A technique for projecting across any dimension is also shown. For “well-behaved” CSG trees the execution time of the conversion algorithm is directly related to the spatial complexity of the object represented by the CSG tree (i.e., as the resolution increases, it is asymptotically proportional to the number of bintree nodes and does not depend on the size or form of the CSG tree representation). The set of well-behaved CSG trees include all trees that define multidimensional polyhedra in a manner that does not give rise to tangential intersections at CSG tree nodes. This is an expanded version of a paper titled “Bintrees, CSG Trees, and Time” which appeared inProceedings of the SIGGRAPH '85 Conference, San Francisco (July 1985), pp. 121–130. This work was supported in part by the National Science Foundation under Grants DCR-83-02118 and IRI-88-02457 and in part by the Finnish Academy Deceased on August 5, 1989     

The Hardness of Approximating Spanner Problems

This paper examines a number of variants of the sparse k-spanner problem and presents hardness results concerning their approximability. Previously, it was known that most k-spanner problems are weakly inapproximable (namely, they are NP-hard to approximate with ratio O(log n), for every k ≥ 2) and that the unit-length k-spanner problem for constant stretch requirement k ≥ 5 is strongly inapproximable (namely, it is NP-hard to approximate with ratio ). The results of this paper significantly expand the ranges of hardness for k-spanner problems. In general, strong hardness is shown for a number of k-spanner problems, for certain ranges of the stretch requirement k depending on the particular variant at hand. The problems studied differ by the types of edge weights and lengths used, and they include directed, augmentation and client-server variants. The paper also considers k-spanner problems in which the stretch requirement k is relaxed (e.g., . For these cases, no inapproximability results were known (even for a constant approximation ratio) for any spanner problem. Moreover, some versions of the k-spanner problem are known to enjoy the ratio-degradation property; namely, their complexity decreases exponentially with the inverse of the stretch requirement. So far, no hardness result existed precluding any k-spanner problem from enjoying this property. This paper establishes strong inapproximability results for the case of relaxed stretch requirement (up to , for any ), for a large variety of k-spanner problems. It is also shown that these problems do not enjoy the ratio-degradation property.     

On the Hardness of Approximating Spanners

A k -spanner of a connected graph G=(V,E) is a subgraph G' consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in G' is larger than the distance in G by no more than a factor of k . This paper concerns the hardness of finding spanners with a number of edges close to the optimum. It is proved that for every fixed k , approximating the spanner problem is at least as hard as approximating the set-cover problem. We also consider a weighted version of the spanner problem, and prove an essential difference between the approximability of the case k=2 and the case k\geq 5 . Received October 30, 1998; revised March 4, 1999, and April 17, 2000.     

A simple implementation of a 3D thermo-viscoelastic model in a finite element program

A simple method for integrating a 3D thermo-viscoelastic model into an available FE code is presented. The temperature field is assumed to be uncoupled from the displacement field. A linear viscoelastic thermorheologically simple model is developed. However, due to the modularity of the approach, the linearization assumptions of this model may easily be relaxed to include material as well as geometric non-linearities.     

Approximating minimum spanning tree of depth 2

We prove that the problem of finding, in an undirected graph with non-negative costs on edges, a minimum cost rooted spanning tree of depth 2 is NP-hard. We then prove that, in a graph of order n , this problem cannot be approximated within better than O )ln n ), unless problems in NP can be solved by slightly superpolynomial algorithms. We also prove that the metric version of the problem is MAX-SNP-hard and, consequently, cannot be approximated by polynomial time approximation schemes, unless P=NP. We devise approximation algorithms for several restricted cases and, finally, a polynomial time algorithm approximating the general problem within ratio ln n .     

Approximating surfaces of revolution by nonrational B-splines

We present a method to approximate surfaces of revolution with nonrational B-splines requiring a modest number of control points in the range of engineering tolerances.     

Reliable detection and separation of components for solid objects defined with scalar fields

The detection of the number of disjoint components is a well-known procedure for surface objects. However, this problem has not been solved for solid models defined with scalar fields in the so-called implicit form. In this paper, we present a technique which allows for detection of the number of disjoint components with a predefined tolerance for an object defined with a single scalar function. The core of the technique is a reliable continuation of the spatial enumeration based on the interval methods. We also present several methods for separation of components using set-theoretic operations for further handling these components individually in a solid modelling system dealing with objects defined with scalar fields.     

The Space Complexity of Approximating the Frequency Moments

The frequency moments of a sequence containingm_ielements of typei, 1⩽i⩽n, are the numbersF_k=∑ⁿ_i=1 m^k_i. We consider the space complexity of randomized algorithms that approximate the numbersF_k, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbersF₀,F₁, andF₂can be approximated in logarithmic space, whereas the approximation ofF_kfork⩾6 requiresn^Ω(1)space. Applications to data bases are mentioned as well.     

Approximating partition functions of the two-state spin system

Two-state spin system is a classical topic in statistical physics. We consider the problem of computing the partition function of the system on a bounded degree graph. Based on the self-avoiding tree, we prove the system exhibits strong correlation decay under the condition that the absolute value of inverse temperature is small. Due to strong correlation decay property, an FPTAS for the partition function is presented and uniqueness of Gibbs measure of the two-state spin system on a bounded degree infinite graph is proved, under the same condition. This condition is sharp for Ising model.     

Approximating algebraic functions by means of rational ones

In this paper, we use ECO method and the concept of succession rule to enumerate restricted classes of combinatorial objects. Let Ω be the succession rule describing a construction of a combinatorial objects class, then the construction of the restricted class is described by means of an approximating succession rule Ω^k obtained from Ω in a natural way. We give sufficient conditions for the rule Ω^k to be finite; finally we determine finite approximating rules for various classes of paths, and the approximation of the corresponding algebraic language with a regular one.     

GA-BP神经网络的非线性函数拟合

由于BP神经网络具有良好的非线性映射能力,但在极值寻优时易陷入局部极值。本文利用具有全局搜索寻优的遗传算法优化BP神经网络(GA-BP),用于非线性函数拟合,弥补了BP网络寻优时的缺点。通过实例比较分析,GA-BP神经网络明显地提高了拟合精度,也使模型具有较强的应用性与推广性。     

Approximating the safely reusable set of learned facts

Despite many advances, today’s software model checkers and extended static checkers still do not scale well to large code bases when verifying properties that depend on complex interprocedural flow of data. An obvious approach to improve performance is to exploit software structure. Although a tremendous amount of work has been done on exploiting structure at various levels of granularity, the fine-grained shared structure among multiple verification conditions has been largely ignored. In this paper, we formalize the notion of shared structure among verification conditions and propose a novel and efficient approach to exploit this sharing by safely reusing facts learned while checking one verification condition to help solve the others. Experimental results show that this approach can improve the performance of verification, even on path- and context-sensitive and dataflow-intensive properties.     

Approximating the number of frequent sets in dense data

We investigate the problem of counting the number of frequent (item)sets—a problem known to be intractable in terms of an exact polynomial time computation. In this paper, we show that it is in general also hard to approximate. Subsequently, a randomized counting algorithm is developed using the Markov chain Monte Carlo method. While for general inputs an exponential running time is needed in order to guarantee a certain approximation bound, we show that the algorithm still has the desired accuracy on several real-world datasets when its running time is capped polynomially.     

Approximating the Minimum Length of Synchronizing Words Is Hard

We prove that, unless P=NP, no polynomial-time algorithm can approximate the minimum length of reset words for a given synchronizing automaton within a constant factor.