Arrangements and Ranking Patterns

In the unidimensional unfolding model, given m objects in general position on the real line, there arise 1 + m(m − 1)/2 rankings. The set of rankings is called the ranking pattern of the m given objects. Change of the position of these m objects results in change of the ranking pattern. In this paper we use arrangement theory to determine the number of ranking patterns theoretically for all m and numerically for m ≤ 8. We also consider the probability of the occurrence of each ranking pattern when the objects are randomly chosen. Received March 5, 2005     

Fundamental frequency of a circular membrane with a strip of small length

A circular membrane with an arbitrarily placed internal strip of small length is concerned in this article. A two-term asymptotic expansion for the fundamental frequency of the membrane, as the length of the strip approaching to zero, is specified. Comparing it with the one [8] derived for the membrane with an internal circular core, it is found that the position of the internal constraint has more effect than the shape of the internal constraint on the fundamental frequency. The asymptotic approximation is also compared with the numerical data computed by the dual boundary element method [2] for a circular membrane of radius 1 with a radially placed internal strip of length 2c. These two sets of data are in good agreement. The relative error is less than 3 % as c is less than or equal to 0.1, for all positions of the strip. Moreover, the relative error is less than 1 % as c is less than or equal to 0.01.     

Fundamental frequency of a circular membrane with a strip of small length

A circular membrane with an arbitrarily placed internal strip of small length is concerned in this article. A two-term asymptotic expansion for the fundamental frequency of the membrane, as the length of the strip approaching to zero, is specified. Comparing it with the one [8] derived for the membrane with an internal circular core, it is found that the position of the internal constraint has more effect than the shape of the internal constraint on the fundamental frequency. The asymptotic approximation is also compared with the numerical data computed by the dual boundary element method [2] for a circular membrane of radius 1 with a radially placed internal strip of length 2c. These two sets of data are in good agreement. The relative error is less than 3 % as c is less than or equal to 0.1, for all positions of the strip. Moreover, the relative error is less than 1 % as c is less than or equal to 0.01.     

Configurational-Force-Based Adaptive FE Solver for a Phase Field Model of Fracture

The computational modeling of failure mechanisms in solids due to fracture based on sharp crack discontinuities suffers in situations with complex crack topologies. This can be overcome by diffusive crack modeling, based on the introduction of a crack phase field as outlined in [1, 2]. Following these formulations, we outline a thermodynamically consistent framework for phase field models of crack propagation in elastic solids, develop incremental variational principles and, as an extension to [1, 2], consider their numerical implementations by an efficient h-adaptive finite element method. A key problem of the phase field formulation is the mesh density, which is required for the resolution of the diffusive crack patterns. To this end, we embed the computational framework into an adaptive mesh refinement strategy that resolves the fracture process zones. We construct a configurational-force-based framework for h-adaptive finite element discretizations of the gradient-type diffusive fracture model. We develop a staggered computational scheme for the solution of the coupled balances in physical and material space. The balance in the material space is then used to set up indicators for the quality of the finite element mesh and accounts for a subsequent h-type mesh refinement. The capability of the proposed method is demonstrated by means of a numerical example. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Boundary controllability of a linear semi-discrete 1-D wave equation derived from a mixed finite element method

In this article one discusses the controllability of a semi-discrete system obtained by discretizing in space the linear 1-D wave equation with a boundary control at one extremity. It is known that the semi-discrete models obtained with finite difference or the classical finite element method are not uniformly controllable as the discretization parameter h goes to zero (see [8]). Here we introduce a new semi-discrete model based on a mixed finite element method with two different basis functions for the position and velocity. We show that the controls obtained with these semi-discrete systems can be chosen uniformly bounded in L²(0,T) and in such a way that they converge to the HUM control of the continuous wave equation, i.e. the minimal L²-norm control. We illustrate the mathematical results with several numerical experiments. Supported by Grant BFM 2002-03345 of MCYT (Spain) and the TMR projects of the EU ``Homogenization and Multiple Scales" and ``New materials, adaptive systems and their nonlinearities: modelling, control and numerical simulations". Partially Supported by Grant BFM 2002-03345 of MCYT (Spain), Grant 17 of Egide-Brancusi Program and Grant 80/2005 of CNCSIS (Romania).     

Numerical analysis of a modified finite element nonlinear Galerkin method

Summary. A fully discrete modified finite element nonlinear Galerkin method is presented for the two-dimensional equation of Navier-Stokes type. The spatial discretization is based on two finite element spaces X_H and X_h defined on a coarse grid with grid size H and a fine grid with grid size h << H, respectively; the time discretization is based on the Euler explicit scheme with respect to the nonlinear term. We analyze the stability and convergence rate of the method. Comparing with the standard finite element Galerkin method and the nonlinear Galerkin method, this method can admit a larger time step under the same convergence rate of same order. Hence this method can save a large amount of computational time. Finally, we provide some numerical tests on this method, the standard finite element Galerkin method, and the nonlinear Galerkin method, which are in a good agreement with the theoretical analysis.Mathematics Subject Classification (2000): 35Q30, 65M60, 65N30, 76D05     

A two-grid finite element method for the Allen-Cahn equation with the logarithmic potential

In this paper, we present a two-grid finite element method for the Allen-Cahn equation with the logarithmic potential. This method consists of two steps. In the first step, based on a fully implicit finite element method, the Allen-Cahn equation is solved on a coarse grid with mesh size H. In the second step, a linearized system whose nonlinear term is replaced by the value of the first step is solved on a fine grid with mesh size h. We give the energy stabilities of the traditional finite element method and the two-grid finite element method. The optimal convergence order of the two-grid finite element method in H¹ norm is achieved when the mesh sizes satisfy h = O(H²). Numerical examples are given to demonstrate the validity of the proposed scheme. The results show that the two-grid method can save the CPU time while keeping the same convergence rate.     

Finding Range Minima in the Middle: Approximations and Applications

A Range Minimum Query asks for the position of a minimal element between two specified array-indices. We consider a natural extension of this, where our further constraint is that if the minimum in a query interval is not unique, then the query should return an approximation of the median position among all positions that attain this minimum. We present a succinct preprocessing scheme using Dn + o(n) bits in addition to the static input array (small constant D), such that subsequent “range median of minima queries” can be answered in constant time. This data structure can be built in linear time, with little extra space needed at construction time. We introduce several new combinatorial concepts such as Super-Cartesian Trees and Super-Ballot Numbers. We give applications of our preprocessing scheme in text indexes such as (compressed) suffix arrays and trees.     

Approximation by circles

We derive algorithms which permit the inspection of plane hole patterns for their position tolerance. The entire hole pattern is measured by a coordinate measuring machine and then is fitted into the nominal pattern in such a way as to minimize the maximum of the distances between the nominal and the actual positions.

---

Zusammenfassung Wir entwickeln Algorithmen, mit deren Hilfe die Einhaltung der Positionstoleranzen ebener Lochbilder untersucht werden kann. Die Gruppe der Ist-Zentren wird dabei gegenüber der Gruppe der Soll-Zentren so eingepaßt, daß der maximale Abstand zwischen den Soll- und den Ist-Werten minimal ausfällt.

     

When does the inverse have the same sign pattern as the transpose?

By a sign pattern (matrix) we mean an array whose entries are from the set {+, –, 0}. The sign patterns A for which every real matrix with sign pattern A has the property that its inverse has sign pattern A ^T are characterized. Sign patterns A for which some real matrix with sign pattern A has that property are investigated. Some fundamental results as well as constructions concerning such sign pattern matrices are provided. The relation between these sign patterns and the sign patterns of orthogonal matrices is examined.     

Error estimates for a mixed finite volume method for the p-Laplacian problem

In this work we propose and analyze a mixed finite volume method for the p-Laplacian problem which is based on the lowest order Raviart–Thomas element for the vector variable and the P1 nonconforming element for the scalar variable. It is shown that this method can be reduced to a P1 nonconforming finite element method for the scalar variable only. One can then recover the vector approximation from the computed scalar approximation in a virtually cost-free manner. Optimal a priori error estimates are proved for both approximations by the quasi-norm techniques. We also derive an implicit error estimator of Bank–Weiser type which is based on the local Neumann problems.This work was supported by the Post-doctoral Fellowship Program of Korea Science & Engineering Foundation (KOSEF).     

On using compressibility to detect when slime mould completed computation

Slime mould Physarum polycephalum is a single cell visible by an unaided eye. The slime mould optimizes its network of protoplasmic tubes in gradients of attractants and repellents. This behavior is interpreted as computation. Several prototypes of the slime mould computers were designed to solve problems of computation geometry, graphs, transport networks, and to implement universal computing circuits. Being a living substrate, the slime mould does not halt its behavior when a task is solved but often continues foraging the space thus masking the solution found. We propose to use temporal changes in compressibility of the slime mould patterns as indicators of the halting of the computation. Compressibility of a pattern characterizes the pattern's morphological diversity, that is, a number of different local configurations. At the beginning of computation the slime explores the space, thus generating less compressible patterns. After gradients of attractants and repellents are detected the slime spans data sites with its protoplasmic network and retracts scouting branches, thus generating more compressible patterns. We analyze the feasibility of the approach on results of laboratory experiments and computer modelling. © 2015 Wiley Periodicals, Inc. Complexity 21: 162–175, 2016     

Numerical and theoretical study of weak Galerkin finite element solutions of Turing patterns in reaction–diffusion systems

In this paper, we introduce numerical schemes and their analysis based on weak Galerkin finite element framework for solving 2‐D reaction–diffusion systems. Weak Galerkin finite element method (WGFEM) for partial differential equations relies on the concept of weak functions and weak gradients, in which differential operators are approximated by weak forms through the Green's theorem. This method allows the use of totally discontinuous functions in the approximation space. In the current work, the WGFEM solves reaction–diffusion systems to find unknown concentrations (u, v) in element interiors and boundaries in the weak Galerkin finite element space WG(P₀, P₀, RT₀) . The WGFEM is used to approximate the spatial variables and the time discretization is made by the backward Euler method. For reaction–diffusion systems, stability analysis and error bounds for semi‐discrete and fully discrete schemes are proved. Accuracy and efficiency of the proposed method successfully tested on several numerical examples and obtained results satisfy the well‐known result that for small values of diffusion coefficient, the steady state solution converges to equilibrium point. Acquired numerical results asserted the efficiency of the proposed scheme.     

A note on a lowest order divergence‐free Stokes element on quadrilaterals

This short note reports a lowest order divergence‐free Stokes element on quadrilateral meshes. The velocity space is based on a P₁ spline element over the crisscross partition of a quadrilateral, and the pressure is approximated by piecewise constant. For a given quadrilateral mesh, this element is stable if and only if the well‐known Q₁‐P₀ element is also stable. Although this method is a subspace method of Qin‐Zhang's P₁‐P₀ element, their velocity solutions are precisely equal. Moreover, an explicit basis representation is also provided. These theoretical findings are verified by numerical tests.     

Accurate pressure post-process of a finite element method for elastoacoustics

Summary. This paper deals with a post-process to obtain a more accurate approximation of the fluid pressure from a finite element computation of the vibration modes of a fluid-structure coupled system. The underlying finite element method, based on a displacement formulation for both media, consists of using Raviart-Thomas elements for the fluid combined with standard continuous elements for the solid. An easy to compute post-process of the pressure is derived. The relation between this post-process and an alternative finite element approximation of the problem based on discretizing the fluid pressure by enriched Crouzeix-Raviart elements is studied. Higher order estimates for the L² norm of the post-processed pressure are proved by exploiting this relation. As a by-product, higher order L² estimates for the solid displacements obtained with the original method are also proved.Member of CIC, Provincia de Buenos Aires, ArgentinaMember of CONICET, Argentina. Partially supported by FONDECYT 7.990.075 and FONDAP in Applied Mathematics, ChilePartially supported by FONDECYT 1.990.346 and FONDAP in Applied Mathematics, Chile     

Mixed finite element methods for incompressible flow: Stationary Stokes equations

In this article, we develop and analyze a mixed finite element method for the Stokes equations. Our mixed method is based on the pseudostress‐velocity formulation. The pseudostress is approximated by the Raviart‐Thomas (RT) element of index k ≥ 0 and the velocity by piecewise discontinuous polynomials of degree k. It is shown that this pair of finite elements is stable and yields quasi‐optimal accuracy. The indefinite system of linear equations resulting from the discretization is decoupled by the penalty method. The penalized pseudostress system is solved by the H(div) type of multigrid method and the velocity is then calculated explicitly. Alternative preconditioning approaches that do not involve penalizing the system are also discussed. Finally, numerical experiments are presented. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2010     

Developing an efficient knowledge discovering model for mining fuzzy multi-level sequential patterns in sequence databases

Sequential pattern mining from sequence databases has been recognized as an important data mining problem with various applications. Items in a sequence database can be organized into a concept hierarchy according to taxonomy. Based on the hierarchy, sequential patterns can be found not only at the leaf nodes (individual items) of the hierarchy, but also at higher levels of the hierarchy; this is called multiple-level sequential pattern mining. In previous research, taxonomies based on crisp relationships between any two disjointed levels, however, cannot handle the uncertainties and fuzziness in real life. For example, Tomatoes could be classified into the Fruit category, but could be also regarded as the Vegetable category. To deal with the fuzzy nature of taxonomy, Chen and Huang developed a novel knowledge discovering model to mine fuzzy multi-level sequential patterns, where the relationships from one level to another can be represented by a value between 0 and 1. In their work, a generalized sequential patterns (GSP)-like algorithm was developed to find fuzzy multi-level sequential patterns. This algorithm, however, faces a difficult problem since the mining process may have to generate and examine a huge set of combinatorial subsequences and requires multiple scans of the database. In this paper, we propose a new efficient algorithm to mine this type of pattern based on the divide-and-conquer strategy. In addition, another efficient algorithm is developed to discover fuzzy cross-level sequential patterns. Since the proposed algorithm greatly reduces the candidate subsequence generation efforts, the performance is improved significantly. Experiments show that the proposed algorithm is much more efficient and scalable than the previous one. In mining real-life databases, our works enhance the model's practicability and could promote more applications in business.     

Error estimates for a finite volume element method for parabolic equations in convex polygonal domains

We analyze the spatially semidiscrete piecewise linear finite volume element method for parabolic equations in a convex polygonal domain in the plane. Our approach is based on the properties of the standard finite element Ritz projection and also of the elliptic projection defined by the bilinear form associated with the variational formulation of the finite volume element method. Because the domain is polygonal, special attention has to be paid to the limited regularity of the exact solution. We give sufficient conditions in terms of data that yield optimal order error estimates in L₂ and H 1 . The convergence rate in the L_∞ norm is suboptimal, the same as in the corresponding finite element method, and almost optimal away from the corners. We also briefly consider the lumped mass modification and the backward Euler fully discrete method. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2004     

and Norms Error Estimates in Finite Element Method for Linear Parabolic Interface Problems

We derive new a priori error estimates for linear parabolic equations with discontinuous coefficients. Due to low global regularity of the solutions the error analysis of the standard finite element method for parabolic problems is difficult to adopt for parabolic interface problems. A finite element procedure is, therefore, proposed and analyzed in this paper. We are able to show that the standard energy technique of finite element method for non-interface parabolic problems can be extended to parabolic interface problems if we allow interface triangles to be curved triangles. Optimal pointwise-in-time error estimates in the L ²(Ω) and H ¹(Ω) norms are shown to hold for the semidiscrete scheme. A fully discrete scheme based on backward Euler method is analyzed and pointwise-in-time error estimates are derived. The interfaces are assumed to be arbitrary shape but smooth for our purpose.