Size bounds for superconcentrators

We prove that any N-superconcentrator of indegree two has at least 4N - o(N) nodes. From this lower bounds of 4N - o(N) follow on the number of additions required to compute the Discrete Fourier Transform of prime order and cyclic convolution. Using small examples we illustrate how small superconcentrators can suggest fast algorithms for instances of these problems.For superconcentrators with no degree restrictions we prove a lower bound of 5N - o(N) edges. Also, we give a recursive construction with 3Nlog₂N edges that improves on the best bounds previously known for values of N up to several thousand.     

A partition of unity enriched dual boundary element method for accurate computations in fracture mechanics

We introduce a novel enriched Boundary Element Method (BEM) and Dual Boundary Element Method (DBEM) approach for accurate evaluation of Stress Intensity Factors (SIFs) in crack problems. The formulation makes use of the Partition of Unity Method (PUM) such that functions obtained from a priori knowledge of the solution space can be incorporated in the element formulation. An enrichment strategy is described, in which boundary integral equations formed at additional collocation points are used to provide auxiliary equations in order to accommodate the extra introduced unknowns. In addition, an efficient numerical quadrature method is outlined for the evaluation of strongly singular and hypersingular enriched boundary integrals. Finally, results are shown for mixed mode crack problems; these illustrate that the introduction of PUM enrichment provides for an improvement in accuracy of approximately one order of magnitude in comparison to the conventional unenriched DBEM.     

Analysis for scattering of conductive objects covered with anisotropic magnetized plasma by trapezoidal recursive convolution finite‐difference time‐domain method

The finite‐difference time‐domain method (FDTD) is extended to three‐dimensional (3D) anisotropic magnetized plasma based on the trapezoidal recursive convolution (TRC) technology. The TRC technique requires single convolution integral in the formulation as in the recursive convolution (RC) method, while maintaining the accuracy comparable to the piecewise linear recursive convolution (PLRC) method with two convolution integrals. In this article, the numerical results indicate that the TRC‐FDTD method not only improves accuracy over the RC‐FDTD with the same computational efficiency but also spends less computational time than the PLRC‐FDTD based on the same accuracy. The 3D TRC‐FDTD formula is provided and the bistatic radar scattering sections of conductive targets covered with anisotropic magnetized plasma are calculated. The results show that magnetized plasma cover layer can greatly reduce echo energy of radar targets, and the anisotropic magnetized plasma cover has better absorption effect than nonmagnetized. © 2010 Wiley Periodicals, Inc. Int J RF and Microwave CAE, 2010.     

Automatic LEFM crack propagation method based on local Lepp–Delaunay mesh refinement

A numerical method for 2D LEFM crack propagation simulation is presented. This uses a Lepp–Delaunay based mesh refinement algorithm for triangular meshes which allows both the generation of the initial mesh and the local modification of the current mesh as the crack propagates. For any triangle t, Lepp(t) (Longest Edge Propagation Path of t) is a finite, ordered list of increasing longest edge neighbor triangles, that allows to find a pair of triangles over which mesh refinement operations are easily and locally performed. This is particularly useful for fracture mechanics analysis, where high gradients of element size are needed. The crack propagation is simulated by using a finite element model for each crack propagation step, then the mesh near the crack tip is modified to take into account the crack advance. Stress intensify factors are calculated using the displacement extrapolation technique while the crack propagation angle is calculated using the maximum circumferential stress method. Empirical testing shows that the behavior of the method is in complete agreement with experimental results reported in the literature. Good results are obtained in terms of accuracy and mesh element size across the geometry during the process.     

The application of moving finite elements for the study of crack propagation in linear elastic solids

Mode I crack propagation in linear elastic solids is studied by a convecting finite element mesh. The finite element formulation is briefly described. Two different approaches for the determination of the stress intensity factor K₁ have been investigated, one using the COD relation to K₁ and one using the dynamic G-integral. Different test problems, including stationary cracks, steady-state crack propagation and transient crack propagation, have been thoroughly examined.     

An effective method for numerical evaluation of general 2D and 3D high order singular boundary integrals

In this paper, a robust method is presented for numerical evaluation of weakly, strongly, hyper- and super-singular boundary integrals, which exist in the Cauchy principal value sense in two- and three-dimensional problems. In this method, the singularities involved in integration kernels are analytically removed by expressing the non-singular parts of the integration kernels as power series in the local distance ρ of the intrinsic coordinate system. For three-dimensional boundary integrals, the radial integration method [1] is applied to transform the surface integral into a line integral over the contour of the surface and to remove various orders of singularities within the radial integrals. Some examples are provided to verify the correctness and robustness of the presented method.     

Minimal parallelism for associative computations under time constraints

The parallel evaluation ofA _N =a ₁ °a ₂ °...°a _N , where ° is binary associative, is studied. Under an idealized model of parallel computation, the minimal number of parallel processors required to computeA _N in at mostt steps is determined for ?log₂ N?≤t≤N?1. This indicates that it is not always desirable to reduce the running time to an absolute minimum, and provides a lower bound on the processing power required for time-constrained evaluation of general arithmetic expressions. Results for two-input processors, are generalized tob-input processors, and then to non-homogeneous collections of processors. The latter does not have a closed-form solution, so approximations are analyzed.     

The boundary element-free method for 2D interior and exterior Helmholtz problems

The boundary element-free method (BEFM) is developed in this paper for numerical solutions of 2D interior and exterior Helmholtz problems with mixed boundary conditions of Dirichlet and Neumann types. A unified boundary integral equation is established for both interior and exterior problems. By using the improved interpolating moving least squares method to form meshless shape functions, mixed boundary conditions in the BEFM can be satisfied directly and easily. Detailed computational formulas are derived to compute weakly and strongly singular integrals over linear and higher order integration cells. Three numerical integration procedures are developed for the computation of strongly singular integrals. Numerical examples involving acoustic scattering and radiation problems are presented to show the accuracy and efficiency of the meshless method.     

The typed λ-calculus is not elementary recursive

We prove that the problem of deciding for closed terms t₁, t₂ of the typed λ-calculus whether t₁ β-converts to t₂ is not elementary recursive.     

An adaptive Huber method for weakly singular second kind Volterra integral equations with non-linear dependencies between unknowns and their integrals

Numerical methods for weakly singular Volterra integral equations with non-linear dependencies between unknowns and their integrals, are almost non-existent in the literature. In the present work an adaptive Huber method for such equations is proposed, by extending the method previously formulated for the first kind Abel equations. The method is tested on example integral equations involving integrals with kernels K(t, τ) = (t ? τ)^?1/2, K(t, τ) = exp[?λ(t ? τ)](t ? τ)^?1/2 (where λ > 0), and K(t, τ) = 1. By controlling estimated local discretisation errors, the integral equation can be solved adaptively on a discrete grid of nodes in the independent variable domain, in a step-by-step fashion. The practical accuracy order is close to 2. The accuracy can be varied by varying the prescribed local error tolerance parameter tol, although the actual errors tend to be larger than tol. Approximations to off-nodal solution values can also be computed, with a comparable accuracy. The method appears numerically stable when partial derivatives, of the non-linear function representing the equation, with respect to the unknown and its integral(s), are of the same sign. The stability of the method in the opposite case may be debated.     

The simulation of 3D elastic scattering produced by thin rigid inclusions using the traction boundary element method

A mixed formulation that uses both the traction boundary element method (TBEM) and the boundary element method (BEM) is proposed to compute the three-dimensional (3D) propagation of elastic waves scattered by two-dimensional (2D) thin rigid inclusions. Although the conventional direct BEM has limitations when dealing with thin-body problems, this model overcomes that difficulty. It is formulated in the frequency domain and, taking into account the 2-1/2D configuration of the problem, can be expressed in terms of waves with varying wavenumbers in the zdirection, k_z. The elastic medium is homogeneous and unbounded and it should be noted that no restrictions are imposed on the geometry and orientation of the internal crack.     

The formula of the solution for some classes of initial boundary value problems for the hyperbolic equation with two independent variables

A new representation is proved of the solutions of initial boundary value problems for the equation of the form u _xx (x, t) + r(x)u _x (x, t) ? q(x)u(x, t) = u _tt (x, t) + μ(x)u _t (x, t) in the section (under boundary conditions of the 1st, 2nd, or 3rd type in any combination). This representation has the form of the Riemann integral dependent on the x and t over the given section.     

基于Vague等价关系的粗糙集分解

首先,提出了基于Vague等价关系的（α_t,α_f）-等价类,并在（α_t,α_f）-等价类基础上定义了（α_t,α_f）-粗糙集,得到（α_t,α_f）-粗糙集是λ-粗糙集的推广,研究了（α_t,α_f）-等价类和（α_t,α_f）-粗糙集的性质。其次,给出（α_t,α_f）-等价类分解、（α_t,α_f）-粗糙集分解以及（α_t,α_f）-粗糙集的边界的概念。最后,分别得到等价类、粗糙集以及粗糙集的边界基于Vague等价关系的分解结构。     

<Emphasis Type="Italic">α</Emphasis>-Systems of differential inclusions and their unification

This paper introduces α-systems of differential inclusions on a bounded time interval [t₀, ?] and defines α-weakly invariant sets in [t₀, ?] × ?_n, where ?_n is a phase space of the differential inclusions. We study the problems connected with bringing the motions (trajectories) of the differential inclusions from an α-system to a given compact set M ? ?_n at the moment ? (the approach problems). The issues of extracting the solvability set W ? [t₀, ?] × ?ⁿ in the problem of bringing the motions of an α-system to M and the issues of calculating the maximal α-weakly invariant set W^c ? [t₀, ?] × ?ⁿ are also discussed. The notion of the quasi-Hamiltonian of an α-system (α-Hamiltonian) is proposed, which seems important for the problems of bringing the motions of the α-system to M.     

Exact solution of mixed problems for variable coefficient one-dimensional diffusion equation

This paper deals with diffusion problems modeled by the equation a(t)u_xx = u_t, x > 0, t > 0, u(x, 0) = c(x) together with the boundary condition u(0, t) = b(t) or u_x(0, t) = b(t). By using Fourier transforms, existence conditions and exact solutions of the above mixed problems are given.     

Planar crack occupying a finite doubly connected region inside an infinite elastic solid

A method is proposed for the approximate solution of the problem of an embedded pressurized planar crack occupying a finite doubly connected region inside an infinite elastic solid. The formulation of the problem produces a system of two integral equations for determining the unknown normal stresses on the plane of the crack outside the crack region, which can be solved using numerical procedures. The proposed method has been applied to obtain the opening mode stress intensity factors K_I, along the boundary lines of an annular crack subjected to a uniform internal pressure.     

Orientation and anisotropy of multi-component shapes from boundary information

We define a method for computing the orientation of compound shapes based on boundary information. The orientation of a given compound shape S is taken as the direction α that maximises the integral of the squared length of projections, of all the straight line segments whose end points belong to particular boundaries of components of S to a line that has the slope α. Just as the concept of orientation can be extended from single component shapes to multiple components, elongation can also be applied to multiple components, and we will see that it effectively produces a measure of anisotropy since it is maximised when all components are aligned in the same direction. The presented method enables a closed formula for an easy computation of both orientation and anisotropy.     

3D block-based medial axis transform and chessboard distance transform based on dominance

Traditionally, the block-based medial axis transform (BB-MAT) and the chessboard distance transform (CDT) were usually viewed as two completely different image computation problems, especially for three dimensional (3D) space. In fact, there exist some equivalent properties between them. The relationship between both of them is first derived and proved in this paper. One of the significant properties is that CDT for 3D binary image V is equal to BB-MAT for image V' where it denotes the inverse image of V. In a parallel algorithm, a cost is defined as the product of the time complexity and the number of processors used. The main contribution of this work is to reduce the costs of 3D BB-MAT and 3D CDT problems proposed by Wang [65]. Based on the reverse-dominance technique which is redefined from dominance concept, we achieve the computation of the 3D CDT problem by implementing the 3D BB-MAT algorithm first. For a 3D binary image of size N³, our parallel algorithm can be run in O(logN) time using N³ processors on the concurrent read exclusive write (CREW) parallel random access machine (PRAM) model to solve both 3D BB-MAT and 3D CDT problems, respectively. The presented results for the cost are reduced in comparison with those of Wang's. To the best of our knowledge, this work is the lowest costs for the 3D BB-MAT and 3D CDT algorithms known. In parallel algorithms, the running time can be divided into computation time and communication time. The experimental results of the running, communication and computation times for the different problem sizes are implemented in an HP Superdome with SMP/CC-NUMA (symmetric multiprocessor/cache coherent non-uniform memory access) architecture. We conclude that the parallel computer (i.e., SMP/CC-NUMA architecture or cluster system) is more suitable for solving problems with a large amount of input size.     

Adaptive quadratures over volumes

We consider the numerical approximation of volume integrals over bounded domainsD:={D∈R ³:H(x>≤0}, whereH:R ³→R is a suitable decidability function. The integrands may be smooth maps or singular maps such as those arising in the volume potentials for boundary integral methods. An adaptive extrapolation method is described which is based on some simple quadrature rules. It utilizes an automatic simplicial subdivision of the domain. The method offers improvements over recently given approaches. A special version is offered for the important application of the numerical computation of volume potentials in boundary integral methods. Several examples illustrate the performance of the method.     

A new high performance approach: merging optimal multicast sessions for supporting multisource routing

Each single source multicast session (SSMS) transmits packets from a source node s _i to a group of destination nodes t _i , i=1,2,…,n. An SSMS’s path can be established with a routing algorithm, which constructs multicast path between source and destinations. Also, for each SSMS, the routing algorithm must be performed once. When the number of SSMS increases to N≥2, the routing algorithm must be separately performed N≥2 times because the number of source nodes increase to N≥2 (for each SSMS the routing algorithm must be performed once). This causes that time of computation and bandwidth consumption to grow. To remove this problem, in this paper, we will present a new approach for merging different SSMSs to make a new multicast session, which is performed only with one execution of a routing algorithm. The new approach, merging different sessions together, is based on the optimal resource allocation and Constraint Based Routing (CBR). We will show that as compared to other available routing algorithms, it improves time of computation and bandwidth consumption and increases data rate and network efficiency. The new approach uses CBR and merges more than one single source multicast session (SSMS) problem to one multisource multicast session (MSMS) problem. By solving one MSMS problem instead of solving more than one SSMS, we can obtain an optimal solution that is more efficient than optimal solutions of SSMS problems.