Search

Abstract: The present paper describes an efficient algorithm to integrate the equations of motion implicitly in the frequency domain. The standard FEM displacement model (Galerkin formulation) is employed to perform space discretization, and the time-marching process is carried out through an algorithm based on the Green’s function of the mechanical system in nodal coordinates. In the present formulation, mechanical system Green’s functions are implicitly calculated in the frequency domain. Once the Green’s functions related matrices are computed, a time integration procedure, which demands low computational effort when applied to non-linear mechanical systems, becomes available. At the end of the paper numerical examples are presented in order to illustrate the accuracy of the present approach. [Copyright &y& Elsevier]

Abstract: In this paper, a subspace limited memory BFGS algorithm for solving large-scale bound constrained optimization problems is developed. It is modifications of the subspace limited memory quasi-Newton method proposed by Ni and Yuan [Q. Ni, Y.X. Yuan, A subspace limited memory quasi-Newton algorithm for large-scale nonlinear bound constrained optimization, Math. Comput. 66 (1997) 1509–1520]. An important property of our proposed method is that more limited memory BFGS update is used. Under appropriate conditions, the global convergence of the method is established. The implementations of the method on CUTE test problems are presented, which indicate the modifications are beneficial to the performance of the algorithm. [Copyright &y& Elsevier]

Abstract: Tarski’s fixed point theorem guarantees the existence of a fixed point of an order-preserving function defined on a nonempty complete lattice [B. Knaster, Un théorème sur les fonctions d’ensembles, Annales de la Société Polonaise de Mathématique 6 (1928) 133–134; A. Tarski, A lattice theoretical fixpoint theorem and its applications, Pacific Journal of Mathematics 5 (1955) 285–309]. In this paper, we investigate several algorithmic and complexity-theoretic topics regarding Tarski’s fixed point theorem. In particular, we design an algorithm that finds a fixed point of when it is given as input and as an oracle. Our algorithm makes queries to when is a total order on . We also prove that when both and are given as oracles, any deterministic or randomized algorithm for finding a fixed point of makes an expected queries for some and . [Copyright &y& Elsevier]

Abstract: In this paper we develop a new mathematical approach to the pattern formation problem in biology. This problem was first posed mathematically by A.M. Turing, however some principal questions were left open (for example, whether there exists a “universal” mathematical model that allows one to obtain any spatio-temporal patterns). Here we consider the pattern formation ability of some class of genetic circuits. First, we show that the genetic circuits are capable of generating arbitrary spatio-temporal patterns. Second, we give upper and lower bounds on the number of genes in a circuit generating a given pattern. A connection between the complexity of gene interaction and the pattern complexity is found. We investigate the stochastic stability of patterning algorithms. Results are consistent with experimental data. [Copyright &y& Elsevier]

Abstract: In many applications of temporal reasoning we are interested in processing temporal information incrementally. In particular, given a set of temporal constraints (a temporal CSP) and a new constraint, we want to maintain certain properties of the extended temporal CSP (e.g., a solution), rather than recomputing them from scratch. The Point Algebra (PA) and the Interval Algebra (IA) are two well-known frameworks for qualitative temporal reasoning. The reasoning algorithms for PA and the tractable fragments of IA, such as Nebel and Bürckert''s maximal tractable class of relations (ORD-Horn), have originally been designed for “static” reasoning. In this paper, we study the incremental version of the fundamental reasoning problems in the context of these tractable classes. We propose a collection of new polynomial algorithms that can amortize their complexity when processing a sequence of input constraints to incrementally decide satisfiability, to maintain a solution, or to update the minimal representation of the CSP. Our incremental algorithms improve the total time complexity of using existing static techniques by a factor of or , where n is the number of the variables involved by the temporal CSP. An experimental analysis focused on constraints over PA confirms the computational advantage of our incremental approach. [Copyright &y& Elsevier]

Covering arrays are combinatorial structures which extend the notion of orthogonal arrays and have applications in the realm of software testing. In this paper we raise several new problems motivated by these applications and discuss algorithms for their solution. [Copyright &y& Elsevier]

Abstract: In [l] and [2], two algorithms have been proposed to calculate the output probability of Boolean functions represented by OBDDs, assuming that the input variables are equiprobable and each variable is statistically independent from others. In this paper, we point out that under these assumptions, the output probability calculation is equivalent to counting the number of minterms of the corresponding Boolean functions. An algorithm is proposed to compute the output probability using simple integer arithmetic as opposed to floating point arithmetic involved in [1,2]. To compute output probability of Boolean functions represented by shared OBDI)s and OBDDs with edge negation, we further propose a generalized algorithm. [Copyright &y& Elsevier]

In this paper the classical stable roommates problem is generalized to situations when the two partners in a pair perform different roles. We propose an efficient algorithm to decide the existence of a stable matching in this problem. [Copyright &y& Elsevier]

In the paper, we show a law of the iterated logarithm for rescaled R/S statistics without second moment. [Copyright &y& Elsevier]

Most collision detection algorithms are ones of a discrete type which utilize convexity and local coherence to verify the closest points. However, the incremental algorithms have such critical drawbacks like failure to detect high-speed collisions and dependence on the time complexity on the time step size of animation. In this paper, in order to find a new method which can resolve the drawbacks, we are concerned with a more restricted but nontrivial version of the problem: given a fixed infinite plane H and a moving convex polyhedron P, compute their collision time. Our algorithm utilizes the spherical extreme vertex diagram that is the embedding of the dual graph P onto the Gauss sphere. Exploiting the diagram, we are able to efficiently compute the sequence of the extreme vertices vis, i = 1, …, m and find the time interval [ti, ti+1] during which vi is the extreme vertex of P. With the sequences of the consecutive time intervals and extreme vertices, we construct a distance function between P and H. Hence, we can compute their collision time within a given tolerance by applying the interval Newton method to the distance function. Moreover, the total time complexity is independent of the time step size of animation. [Copyright &y& Elsevier]

This paper presents some new techniques in designing finite-difference domain decomposition algorithm for the heat equation. The basic procedure is to define the finite-difference schemes at the interface grid points with smaller time step Δt = SHAPE="SOL" ALIGN="C" STYLE="S">Δtm (m is a positive integer) by Saul''yev asymmetric schemes. The algorithm can increase the stability bounds of the classical explicit method by 2m times, and the prior error estimates for the numerical solutions are obtained for some algorithms when m = 2 or m = 3. Numerical experiments on stability and accuracy are also presented. [Copyright &y& Elsevier]