Search

There are several classical characterisations of the valuative dimension of a commutative ring. Constructive versions of this dimension have been given and proven to be equivalent to the classical notion within classical mathematics, and they can be used for the usual examples of commutative rings. To the contrary of the classical versions, the constructive versions have a clear computational content. This paper investigates the computational relationship between three possible constructive definitions of the valuative dimension of a commutative ring. In doing so, it proves these constructive versions to be equivalent within constructive mathematics. [ABSTRACT FROM AUTHOR]

Abstract: In 1.9 of the paper [A. Hahn, A Hermitian Morita theorem for algebras with anti-structure, J. Algebra 93 (1985) 215–235], should be replaced by . This leads to minor changes in the rest of the paper where the ring should be replaced by its opposite and vice versa. [Copyright &y& Elsevier]

Abstract The growth of tropical geometry has generated significant interest in the tropical semiring in the past decade. However, there are other semirings in tropical algebra that provide more information, such as the symmetrized (max ⁡ , +) , Izhakian's extended and Izhakian–Rowen's supertropical semirings. In this paper we identify in which of these upper-bound semirings we can express symmetric polynomials in terms of elementary ones. We show that in the case of idempotent semirings we can do this precisely when the Frobenius property is satisfied, that in the case of supertropical semirings this is always possible, and that in non-trivial symmetrized semirings this is never possible. Our results allow us to determine the tropical algebra semirings where an analogue of the Fundamental Theorem of Symmetric Polynomials holds and to what extent. [ABSTRACT FROM AUTHOR]

Abstract With the increasing use of composite material and external energy dissipation device in civil structures, the classical Rayleigh damping becomes an inappropriate assumption in structural damage identification. In this paper, a parametric sensitivity-based approach is developed to identify the structural damage and damping defect of non-classically damped shear-type building simultaneously. As the preliminary step, the complex eigenvalues and eigenvectors of damaged structure are obtained by a novel identification technique, which decouples the first-order modal analysis equation under physical coordinate so that the complex modal parameters of each mode can be identified independently. Thereafter, by analysing the sensitivities of complex eigenparameter, non-linear least square method is applied to identify the locations and magnitudes of damage with respect to stiffness reduction and damping defect. The proposed identification approach is illustrated by identifying the damage in a numerical five-storey shear building. The identification results show that the proposed approach can locate and quantify the stiffness reductions satisfactorily even when measurement noise is taken into account. However, in order to quantify the damping defects consistently, their locations need to be known as a priori. Highlights • A novel complex eigenparameter identification approach under state-space coordinate. • Damage identification on non-proportionally damped shear-type building. • Identify the stiffness reduction and damping defect simultaneously. • Identify the design parameters which locate and quantify the damages. • Numerical validation on a five-storey shear building by considering measurement noise. [ABSTRACT FROM AUTHOR]

In this paper we prove a new recurrence relation on the van der Waerden numbers, w ( r , k ) . In particular, if p is a prime and p ≤ k then w ( r , k ) > p ⋅ w r − r p , k − 1 . This recurrence gives the lower bound w ( r , p + 1 ) > p r − 1 2 p when r ≤ p , which generalizes Berlekamp’s theorem on 2-colorings, and gives the best known bound for a large interval of r . The recurrence can also be used to construct explicit valid colorings, and it improves known lower bounds on small van der Waerden numbers. [ABSTRACT FROM AUTHOR]

One of the most famous algorithmic meta-theorems states that every graph property which can be defined in counting monadic second order logic (CMSOL) can be checked in linear time on graphs of bounded treewidth, which is known as Courcelle’s Theorem (Courcelle, 1990). These algorithms are constructed as finite state tree automata and hence every CMSOL-definable graph property is recognizable. Courcelle also conjectured that the converse holds, i.e. every recognizable graph property is definable in CMSOL for graphs of bounded treewidth. In this paper we prove two special cases of this conjecture, first for the class of k -outerplanar graphs, which are known to have treewidth at most 3 k − 1 (Bodlaender, 1998) and for graphs of bounded treewidth without chordless cycles of length at least some constant ℓ . We furthermore show that for a proof of Courcelle’s Conjecture it is sufficient to show that all members of a graph class admit constant width tree decompositions whose bags and edges can be identified with MSOL-predicates. For graph classes that admit MSOL-definable constant width tree decompositions that have bounded degree or allow for a linear ordering of all nodes with the same parent we even give a stronger result: In that case, the counting predicates of CMSOL are not needed. [ABSTRACT FROM AUTHOR]

The generalised colouring numbers col r ( G ) and wcol r ( G ) were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have since then found important theoretical and algorithmic applications. In this paper, we dramatically improve upon the known upper bounds for generalised colouring numbers for graphs excluding a fixed minor, from the exponential bounds of Grohe et al. to a linear bound for the r -colouring number col r and a polynomial bound for the weak r -colouring number wcol r . In particular, we show that if G excludes K t as a minor, for some fixed t ≥ 4 , then col r ( G ) ≤ t − 1 2 ( 2 r + 1 ) and wcol r ( G ) ≤ r + t − 2 t − 2 ( t − 3 ) ( 2 r + 1 ) ∈ O ( r t − 1 ) . In the case of graphs G of bounded genus g , we improve the bounds to col r ( G ) ≤ ( 2 g + 3 ) ( 2 r + 1 ) (and even col r ( G ) ≤ 5 r + 1 if g = 0 , i.e. if G is planar) and wcol r ( G ) ≤ ( 2 g + r + 2 2 ) ( 2 r + 1 ) . [ABSTRACT FROM AUTHOR]

Many methods for multinational License Plate Detection (LPD) have been proposed in recent times but most of them are not sophisticated enough to handle complex backgrounds. Moreover, their ability to handle various environmental and illumination conditions has been limited and still needs improvement. In this paper, we propose a novel technique to detect license plates of vehicles regardless of their color, size, and content. As the rear vehicle lights are an essential part of any vehicle, we reduce the image processing area to eliminate the complex background by detecting the rear-lights as the license plates are in a certain range of these lights. Heuristic Energy Map (HEM) of the vertical edge information in the Region of Interest (ROI) is calculated and area with the dense edges is selected using a unique histogram approach which is considered to be the license plate. The proposed algorithm is tested on 855 images from various countries including China, Pakistan, Serbia, Italy and various states of America. Experimental results show that the proposed method is able to detect license plates 90.4% of times despite of complex backgrounds in 0.25 s on average that can achieve real time performance. [ABSTRACT FROM AUTHOR]

This paper presents a new algorithm for implicitizing tensor product surfaces of bi-degree ( m , n ) with no base points, assuming that there are no moving planes of bi-degree ( m − 1 , n − 1 ) following the surface. The algorithm is based on some structural results: (1) There are exactly 2 n linearly independent moving planes of bi-degree ( m , n − 1 ) following the surface; (2) mn linearly independent moving quadrics of bi-degree ( m − 1 , n − 1 ) following the surface can be constructed from the 2 n linearly independent moving planes; (3) The mn linearly independent moving quadrics form a compact determinant of order mn which exactly gives the implicit equation of the rational surface. Complexity analysis and experimental results show that the new algorithm is significantly more efficient than the previous methods. [ABSTRACT FROM AUTHOR]

Abstract: Quasimodules for vertex algebras are generalizations of modules for vertex algebras. These new objects arise from a generalization of locality for fields. Quasimodules tie together module theory and twisted module theory, and both twisted and untwisted modules feature Poincaré–Birkhoff–Witt-like spanning sets. This paper generalizes these spanning set results to quasimodules for certain Möbius vertex algebras. In particular this paper presents two spanning sets, one featuring a difference-zero ordering restriction on modes and another featuring a difference-one ordering restriction. [Copyright &y& Elsevier]

Abstract: The algebraic theory of variable-length codes was initiated by Schützenberger in the 1950s. Almost all the subsequently stated results in this theory are constructive and therefore lead to algorithms. However, there are some basic problems that are still open. For instance, we still do not know how to decide whether a finite code can be embedded in a finite maximal one. We answer this question under additional hypotheses. Precisely, let A be a finite alphabet with , let . Let , let be the number of factors in the prime factorization of n. We give an algorithm to decide whether there exists n, with , and a finite maximal code C which is also factorizing such that . We recall that a factorizing code is a finite maximal code which satisfies the factorization conjecture, proposed by Schützenberger. The above-mentioned statement is a consequence of another result proved in this paper. Namely, given a factorizing code C, it is known that the words in satisfy a property defined by using factorizations of cyclic groups. In this paper we give an algorithm to decide whether a set can be embedded in a set satisfying . Furthermore, we prove that, conversely, for each set satisfying , under additional hypotheses, there exists a factorizing code C such that and, as a consequence, is a code. In this case, C can be constructed starting with prefix/suffix codes and by using two types of operations on codes (composition and substitution). The additional required hypotheses concern the structure of the factorizations involved and are always satisfied when, for each , we have , with . In addition, we prove that there exist sets which satisfy and which are not codes. [Copyright &y& Elsevier]

Abstract: Recent work of Gowers [T. Gowers, A new proof of Szemerédi''s theorem, Geom. Funct. Anal. 11 (2001) 465–588] and Nagle, Rödl, Schacht, and Skokan [B. Nagle, V. Rödl, M. Schacht, The counting lemma for regular k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Regularity lemma for k-uniform hypergraphs, Random Structures Algorithms, in press; V. Rödl, J. Skokan, Applications of the regularity lemma for uniform hypergraphs, preprint] has established a hypergraph removal lemma, which in turn implies some results of Szemerédi [E. Szemerédi, On sets of integers containing no k elements in arithmetic progression, Acta Arith. 27 (1975) 299–345], and Furstenberg and Katznelson [H. Furstenberg, Y. Katznelson, An ergodic Szemerédi theorem for commuting transformations, J. Anal. Math. 34 (1978) 275–291] concerning one-dimensional and multidimensional arithmetic progressions, respectively. In this paper we shall give a self-contained proof of this hypergraph removal lemma. In fact we prove a slight strengthening of the result, which we will use in a subsequent paper [T. Tao, The Gaussian primes contain arbitrarily shaped constellations, preprint] to establish (among other things) infinitely many constellations of a prescribed shape in the Gaussian primes. [Copyright &y& Elsevier]

Abstract: In this paper we describe software for an efficient factorization of polynomials over global fields . The algorithm for function fields was recently incorporated into our system KANT. The method is based on a generic algorithm developed by the second author in an earlier paper in this journal. Besides algorithmic aspects not contained in that paper we give details about the current implementation and about some complexity issues as well as a few illustrative examples. Also, a generalization of the application of LLL reduction for factoring polynomials over arbitrary global fields is developed. [Copyright &y& Elsevier]

Abstract: In previous papers (J. Combin Theory Ser. A 103 (2003) 387) and (J. Combin. Theory Ser. A 105 (2004) 359) Saharon Shelah and I formulated a conditional chromatic number theorem, which described a setting in which the chromatic number of the plane takes on two different values depending upon the axioms for set theory. We also constructed examples of a distance graph on the real line R and difference graphs on the real plane R whose chromatic numbers depend upon the system of axioms we choose for set theory. Ideas developed there are extended in the present paper to construct difference graphs on the real space R , whose chromatic number is a positive integer in the Zermelo–Fraenkel-choice system of axioms, and is not countable (if it exists) in a consistent system of axioms with limited choice, studied by Solovay (Ann. Math. Ser. 2 (1970) 1). These examples illuminate how heavily combinatorial results can depend upon the underlying set theory, help appreciate the potential complexity of the chromatic number of n-space problem, and suggest that the chromatic number of n-space may depend upon the system of axioms chosen for set theory. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a generic method of automatic parallelization for sparse matrix computation. This method is based on both a refinement of the data-dependence test proposed by Bernstein and an inspector–executor scheme which is specialized to each input program of the compiler. This analysis mixes compilation process and run-time process. The sparsity of underlying data-structure determines a specific parallelism which increases the degree of parallelism of an algorithm. Such a source of parallelism had already been applied to many numerical algorithms such as the usual Cholesky factorization or LU-decomposition algorithms considered as the gold standards of parallelization based on sparsity. The standard automatic parallelization method cannot tackle such source of parallelism because it is based on the value of cells arrays and not merely on the memory addressing function. Addressing the automatization of this parallelism requires to develop a mixed compile-time and runtime approach integrated in a inspector–executor process. The compilation step provides a dedicated inspector devoted to the analyzed program. The inspector computes the dependence graph at runtime which allows a dynamic parallelization of the execution. As expressed just before, the generic scheme developed in this paper follows the design principles which have been applied, but at each time in an ad hoc way, to many sparse parallelization of numerical algorithms such as Cholesky algorithm. As far as we know, no general formal framework has been proposed to automate such a method of sparse parallelization. In this paper, we propose a generic framework of sparse parallelization (i.e. numerical program independent) which can be applied to any numerical programs satisfying the usual syntactic constraints of parallelization. [Copyright &y& Elsevier]

The aim of this paper is to exploit the algorithms of paper Experimental Math. 8 (1999) in order to produce a new algebraic method for computing efficiently absolute Lagrange resolvent, a fundamental tool in constructive algebraic Galois theory. This article is composed of two parts.The main idea of the first part is to break up the calculation of absolute resolvent into smaller computations. Since a multi-resolvent is a factor of a resolvent, the whole resolvent may be computed by means of several multi-resolvents.The idea of the second part is that an irreducible polynomial over Z might be reducible over Z /pZ for certain integer p. So the first part can be applied and then, the Chinese remainder theorem allows to lift up the resolvent over Z. [Copyright &y& Elsevier]

A number of recent papers on approximation algorithms have used the square roots of unity, −1 and 1, to represent binary decision variables for problems in combinatorial optimization, and have relaxed these to unit vectors in real space using semidefinite programming in order to obtain near optimum solutions to these problems. In this paper, we consider using the cube roots of unity, 1, ei2π/3, and ei4π/3, to represent ternary decision variables for problems in combinatorial optimization. Here the natural relaxation is that of unit vectors in complex space. We use an extension of semidefinite programming to complex space to solve the natural relaxation, and use a natural extension of the random hyperplane technique introduced by the authors in Goemans and Williamson (J. ACM 42 (1995) 1115–1145) to obtain near-optimum solutions to the problems. In particular, we consider the problem of maximizing the total weight of satisfied equations xu−xv≡c (mod 3) and inequations xu−xv≢c (mod 3), where xu∈{0,1,2} for all u. This problem can be used to model the Max-3-Cut problem and a directed variant we call Max-3-Dicut. For the general problem, we obtain a 0.793733-approximation algorithm. If the instance contains only inequations (as it does for Max-3-Cut), we obtain a performance guarantee of 7/12+3/4π2arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3+3/4π2arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3 arccos2(−1/4)−ϵ>0.836008. This compares with proven performance guarantees of 0.800217 for Max-3-Cut (by Frieze and Jerrum (Algorithmica 18 (1997) 67–81) and 1/3+10−8 for the general problem (by Andersson et al. (J. Algorithms 39 (2001) 162–204)). It matches the guarantee of 0.836008 for Max-3-Cut found independently by de Klerk et al. (On approximate graph colouring and Max-k-Cut algorithms based on the ϑ-function, Manuscript, October 2000). We show that all these algorithms are in fact equivalent in the case of Max-3-Cut, and that our algorithm is the same as that of Andersson et al. in the more general case. [Copyright &y& Elsevier]

In this paper we propose a new iterative penalty-projection algorithm for a monolithic fluid-structure interaction solver. Projection methods, that split the computation of the velocity from the pressure, are very popular in fluid dynamics since the boundary errors generated by the projection method are localized mainly near the boundary layers where the incorrect pressure boundary conditions are imposed. However, when solid regions are taken into account, the pressure projected field cannot satisfy fully coupled boundary constraints imposed on external solid surfaces such as stress-free conditions, and, due to the rigidity of the medium, the boundary errors propagate deeply in the interior. In order to reduce the projection errors we propose a one-step penalty-projection method in the fluid domain and an iterative penalty-projection method in the solid region. This technique decouples the pressure-velocity degrees of freedom and, as a consequence, the computational cost. In order to verify the accuracy and robustness of the proposed method we compare the results between this splitting velocity-pressure algorithm and the coupled one. These numerical results show stability and robustness of the proposed algorithm with a strong reduction of the computational effort. [ABSTRACT FROM AUTHOR]

In 1994 Lazard proposed an improved projection operation for cylindrical algebraic decomposition (CAD). For the proof he introduced a certain notion of valuation of a multivariate Puiseux series at a point. However a gap in one of the key supporting results for the improved projection was subsequently noticed. In this paper we show that Lazard's projection is valid for CAD construction for so-called well-oriented polynomial sets. Our proof does not make use of Lazard's notion of valuation, however. [ABSTRACT FROM AUTHOR]

This paper introduces stochastic weighted particle algorithms for the solution of multi-compartment population balance equations. In particular, it presents a class of fragmentation weight transfer functions which are constructed such that the number of computational particles stays constant during fragmentation events. The weight transfer functions are constructed based on systems of weighted computational particles and each of it leads to a stochastic particle algorithm for the numerical treatment of population balance equations. Besides fragmentation, the algorithms also consider physical processes such as coagulation and the exchange of mass with the surroundings. The numerical properties of the algorithms are compared to the direct simulation algorithm and an existing method for the fragmentation of weighted particles. It is found that the new algorithms show better numerical performance over the two existing methods especially for systems with significant amount of large particles and high fragmentation rates. [ABSTRACT FROM AUTHOR]

Abstract: It has recently been proved that the popular nonlocal means (NLM) denoising algorithm does not optimally denoise images with sharp edges. Its weakness lies in the isotropic nature of the neighborhoods it uses to set its smoothing weights. In response, in this paper we introduce several theoretical and practical anisotropic nonlocal means (ANLM) algorithms and prove that they are near minimax optimal for edge-dominated images from the Horizon class. On real-world test images, an ANLM algorithm that adapts to the underlying image gradients outperforms NLM by a significant margin. [Copyright &y& Elsevier]

Abstract: This paper describes an algorithm which produces all ideals compatible with a given surjective Frobenius near-splitting. [Copyright &y& Elsevier]

Abstract: In this paper we give an explicit algorithm to construct the ordinary quiver of a finite EI category for which the endomorphism groups of all objects have orders invertible in the field k. We classify all finite EI categories with hereditary category algebras, characterizing them as free EI categories (in a sense which we define) for which all endomorphism groups of objects have invertible orders. Some applications on the representation types of finite EI categories are derived. [Copyright &y& Elsevier]

Abstract: This paper concerns systems with small coherence parameter. Simple greedy-type algorithms perform well on these systems, which are also useful in the construction of compressed sensing matrices. We discuss the following problems for both and . How large can a dictionary be, if we prescribe the coherence parameter? How small could the resulting coherence parameter be, if we impose a size on the dictionary? How could we construct such a system? Several fundamental results from different areas of mathematics shed light on these important problems with far-reaching implications in approximation theory. [Copyright &y& Elsevier]

Abstract: The algorithms used in Arabic and medieval European mathematics for extracting cube roots are studied with respect to algebraic structure and use of external memory (dust board, table, paper). They can be separated into two distinct groups. One contains methods used in the eastern regions from the 11th century, closely connected to Chinese techniques, and very uniform in structure. The other group, showing much wider variation, contains early Indian methods and techniques developed in central and western parts of the Arabic areas and in Europe. This study supports hypotheses previously formulated by Luckey and Chemla on an early scientific connection between China and Persia. [Copyright &y& Elsevier]

Abstract: In Schweiger (2003) , Fritz Schweiger introduced the algorithm of the generalized continued fraction (GCF), and in Zhong (2008) , T. Zhong studied some basic metric properties of the GCF. In this paper, under the restriction of , the “0–1” law and the central limit theorem of quotients in the GCF expansions are studied. [Copyright &y& Elsevier]

Abstract: In this paper we present a new primal-dual path-following interior-point algorithm for semidefinite optimization. The algorithm is based on a new technique for finding the search direction and the strategy of the central path. At each iteration, we use only full Nesterov–Todd step. Moreover, we obtain the currently best known iteration bound for the algorithm with small-update method, namely, , which is as good as the linear analogue. [Copyright &y& Elsevier]

Abstract: This paper explores the certification of properties of an efficient functional program in the area of symbolic computation: the calculation of Gröbner basis of a set of multivariate polynomials. Our experience in the development of industrial systems and the certification of some of its relevant properties has led us to use a methodology consisting of functional programs to write the code and the formal verification of fundamental properties. The functional language objective caml has been chosen to implement the program. To verify the properties two approaches are explored: manual proofs that reason directly over the source code of the algorithms, applying techniques like equational reasoning, and theorem provers that are used as a tool to help us certify a model of the real system. The chosen proof assistant is coq. Not only will the certification of the software be taken into consideration but also its efficiency. In addition, we present a graphical interface which eases the use of the program. [Copyright &y& Elsevier]

Abstract: In this paper, we show that minimization problems involving sublinear regularizing terms are ill-posed, in general, although numerical experiments in image processing give very good results. The energies studied here are inspired by image restoration and image decomposition. Rewriting the nonconvex sublinear regularizing terms as weighted total variations, we give a new approach to perform minimization via the well-known Chambolle''s algorithm. The approach developed here provides an alternative to the well-known half-quadratic minimization one. [Copyright &y& Elsevier]

Abstract: In this paper we analyze O''Hara''s partition bijection. We present three type of results. First, we show that O''Hara''s bijection can be viewed geometrically as a certain scissor congruence type result. Second, we obtain a number of new complexity bounds, proving that O''Hara''s bijection is efficient in several special cases and mildly exponential in general. Finally, we prove that for identities with finite support, the map of the O''Hara''s bijection can be computed in polynomial time, i.e. much more efficiently than by O''Hara''s construction. [Copyright &y& Elsevier]

Abstract: Factorial designs are arguably the most widely used designs in scientific investigations. Generalized minimum aberration (GMA) and uniformity are two important criteria for evaluating both regular and non-regular designs. The generation of GMA designs is a non-trivial problem due to the sequential optimization nature of the criterion. Based on an analytical expression between the generalized wordlength pattern and a uniformity measure, this paper converts the generation of GMA designs to a constrained optimization problem, and provides effective algorithms for solving this particular problem. Moreover, many new designs with GMA or near-GMA are reported, which are also (nearly) optimal under the uniformity measure. [Copyright &y& Elsevier]

Abstract: BackPropagation (BP) is the most famous learning algorithm for Artificial Neural Networks (ANN). BP has received intensive research efforts to exploit its parallelism in order to reduce the training time for complex problems. A modified version of BP based on matrix–matrix multiplication was proposed for parallel processing. In this paper, we present the implementation of Matrix BackPropagation (MBP) using scalar, vector, and matrix Instruction Set Architectures (ISAs). Besides this, we show that the performance of the MBP is improved by switching from scalar ISA to vector ISA. It is further improved by switching from vector ISA to matrix ISA. On a practical application, speech recognition, the speedup of training a neural network using unrolling scalar ISA over scalar ISA is 1.83. On eight parallel lanes, the speedups of using vector, unrolling vector, and matrix ISAs are respectively 10.33, 11.88, and 15.36, where the maximum theoretical speedup is 16. The results obtained show that the use of matrix ISA gives a performance close to optimal, because of reusing the loaded data, decreasing the loop overhead, and overlapping the memory operations with arithmetic operations. [Copyright &y& Elsevier]

Abstract: In this paper we consider partial actions of groups on algebras and partial skew group rings. After some general results we prove two versions of Maschke''s theorem and then we study von Neumann regularity, the prime radical and the Jacobson radical of partial skew group rings. In this way we extend many results which are known for skew group rings. [Copyright &y& Elsevier]

Abstract: In a variety of dynamical systems, formations of motion patterns occur. Observing colonies of animals, for instance, for the scientist it is not only of interest which kinds of formations these animals show, but also how they altogether move around. In order to analyse motion patterns for the purpose of making predictions, to describe the behaviour of systems, or to index databases of moving objects, methods are required for dealing with them. This becomes increasingly important since a number of technologies have been devised which allow objects precisely to get traced. However, the indeterminacy of spatial information in real world environments also requires techniques to approximate reasoning, for example, in order to compensate for small and unimportant distinctions which are due to noisy measurements. As a consequence, precise as well as coarse motion patterns have to be dealt with. A set of 16 atomic motion patterns is proposed. On the one hand, a relation algebra is defined on them. On the other hand, these 16 relations form the basis of a visual language using which motion patterns can easily be dealt with in a diagrammatic way. The relations are coarse but crisp and they allow imprecise knowledge about motion patterns to be dealt with, while their diagrammatic realisation also allow precise patterns to get handled. While almost all approaches consider motion patterns along arbitrary time intervals, this paper in particular focuses on short-term motion patterns as we permanently observe them in our everyday life. The bottom line of the current work, however, is yet more general. While it has been widely argued that it makes sense to use both sentential and diagrammatic representations in order to represent different things in the same system adequately (and hence differently), we argue that it makes even sense to represent the same things differently in order to grasp different aspects of one and the same object of interest from different viewpoints. We demonstrate this by providing both a sentential and a diagrammatic representation for the purpose of grasping different aspects of motion patterns. It shows that both representations complement each other. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a generalization for the class of laura algebras, called almost laura. We show that this new class of algebras retains most of the essential features of laura algebras, especially concerning the important role played by the non-semiregular components in their Auslander–Reiten quivers. Also, we study more intensively the left supported almost laura algebras, showing that these are characterized by the presence of a generalized standard, convex and faithful component. Finally, we prove that almost laura algebras behave well with respect to full subcategories, split-by-nilpotent extensions and skew group algebras. [Copyright &y& Elsevier]

Abstract: In [M. Dettweiler, S. Reiter, An algorithm of Katz and its application to the inverse Galois problem, J. Symbolic Comput. 30 (2000) 761–798], a purely algebraic analogon of Katz'' middle convolution functor (see [N.M. Katz, Rigid Local Systems, Ann. of Math. Stud., vol. 139, Princeton University Press, 1997]) is given. In this paper, we find an explicit Riemann–Hilbert correspondence for this functor. This leads to a construction algorithm for differential systems which correspond to rigid local systems on the punctured affine line via the Riemann–Hilbert correspondence. [Copyright &y& Elsevier]

Abstract: In this paper we study construction algorithms for polynomial lattice rules modulo arbitrary polynomials. Polynomial lattice rules are a special class of digital nets which yield well distributed point sets in the unit cube for numerical integration. Niederreiter obtained an existence result for polynomial lattice rules modulo arbitrary polynomials for which the underlying point set has a small star discrepancy and recently Dick, Leobacher and Pillichshammer introduced construction algorithms for polynomial lattice rules modulo an irreducible polynomial for which the underlying point set has a small (weighted) star discrepancy. In this work we provide construction algorithms for polynomial lattice rules modulo arbitrary polynomials, thereby generalizing the previously obtained results. More precisely we use a component-by-component algorithm and a Korobov-type algorithm. We show how the search space of the Korobov-type algorithm can be reduced without sacrificing the convergence rate, hence this algorithm is particularly fast. Our findings are based on a detailed analysis of quantities closely related to the (weighted) star discrepancy. [Copyright &y& Elsevier]

Abstract: A family of algorithms for approximate solution of the bound-constrained minimization problem was introduced in [K.A. Ariyawansa, W.L. Tabor, A class of collinear scaling algorithms for bound-constrained optimization: Derivation and computational results, Technical Report 2003-1, Department of Mathematics, Washington State University, Pullman, WA, 2003, submitted for publication. Available at http://www.math.wsu.edu/math/TRS/2003-1.pdf]. These algorithms employ the standard barrier method, with the inner iteration based on trust region methods. Local models are conic functions rather than the usual quadratic functions, and are required to match first and second derivatives of the barrier function at the current iterate. The various members of the family are distinguished by the choice of a vector-valued parameter, which is the zero vector in the degenerate case that quadratic local models are used. This paper presents a convergence analysis of the family of algorithms presented in [K.A. Ariyawansa, W.L. Tabor, A class of collinear scaling algorithms for bound-constrained optimization: Derivation and computational results, Technical Report 2003-1, Department of Mathematics, Washington State University, Pullman, WA, 2003, submitted for publication. Available at http://www.math.wsu.edu/math/TRS/2003-1.pdf]. Specifically, convergence properties similar to those of barrier methods using quadratic local models are established. [Copyright &y& Elsevier]

Abstract: The gap function of an infinite word over the binary alphabet gives the distances between consecutive 1''s in this word. In this paper we study infinite binary words whose gap function is injective or “almost injective.” A method for computing the subword complexity of such words is given. A necessary and sufficient condition for a function to be the subword complexity function of a binary word whose gap function is increasing is obtained. [Copyright &y& Elsevier]

Abstract: In [B. De Bruyn, P. Vandecasteele, Valuations and hyperplanes of dual polar spaces, J. Combin. Theory Ser. A 112 (2005) 194–211], we introduced the class of the SDPS-valuations of dual polar spaces. We showed that these valuations and all their extensions give rise to hyperplanes of dual polar spaces. We call these hyperplanes SDPS-hyperplanes. In the present paper, we show that a hyperplane of a thick dual polar space is an SDPS-hyperplane if and only if every hex not contained in intersects in either a singular hyperplane or the extension of an ovoid. [Copyright &y& Elsevier]

Abstract: For a canonical threefold X, we know for a sufficiently large n. When , there are few known results about the integer n. This paper introduces an algorithm for computing plurigenera. Furthermore, when is small, especially 1 and 2, plurigenera are computed. This produces for and for when . Also, for and for with 8 possible exceptional cases when . [Copyright &y& Elsevier]

Abstract: The Gröbner walk is an algorithm for conversion between Gröbner bases for different term orders. It is based on the polyhedral geometry of the Gröbner fan and involves tracking a line between cones representing the initial and target term order. An important parameter is the explicit numerical perturbation of this line. This usually involves both time and space, demanding arithmetic of integers much larger than the input numbers. In this paper we show how the explicit line may be replaced by a formal line using Robbiano’s characterization of group orders on . This gives rise to the generic Gröbner walk involving only Gröbner basis conversion over facets and computations with marked polynomials. The infinite precision integer arithmetic is replaced by term order comparisons between (small) integral vectors. This makes it possible to compute with infinitesimal numbers and perturbations in a consistent way without introducing unnecessary long integers. The proposed technique is closely related to the lexicographic (symbolic) perturbation method used in optimization and computational geometry. We report on an implementation of our algorithm specifically tailored to computations with lattice ideals. [Copyright &y& Elsevier]

Abstract: An algorithm is presented that computes explicit generators for the ring of differential operators on an orbifold, the quotient of a complex vector space by a finite group action. The algorithm also describes the relations among these generators. The algorithm presented in this paper is based on Schwarz’s study of a map carrying invariant operators to operators on the orbifold and on an algorithm to compute rings of invariants using Gröbner bases due to Derksen [Derksen, Harm, 1999. Computation of invariants for reductive groups. Adv. Math. 141 (2), 366–384]. It is also possible to avoid using Derksen’s algorithm, instead relying on the Reynolds operator and the Molien series. [Copyright &y& Elsevier]

Abstract: Several message passing-based parallel solvers have been developed for general (non-symmetric) sparse LU factorization with partial pivoting. Existing solvers were mostly deployed and evaluated on parallel computing platforms with high message passing performance (e.g., 1– in message latency and 100–1000Mbytes/s in message throughput) while little attention has been paid on slower platforms. This paper investigates techniques that are specifically beneficial for LU factorization on platforms with slow message passing. In the context of the distributed memory solver, we find that significant reduction in the application message passing overhead can be attained at the cost of extra computation and slightly weakened numerical stability. In particular, we propose batch pivoting to make pivot selections in groups through speculative factorization, and thus substantially decrease the inter-processor synchronization granularity. We experimented on three different message passing platforms with different communication speeds. While the proposed techniques provide no performance benefit and even slightly weaken numerical stability on an IBM Regatta multiprocessor with fast message passing, they improve the performance of our test matrices by 15–460% on an Ethernet-connected 16-node PC cluster. Given the different tradeoffs of communication-reduction techniques on different message passing platforms, we also propose a sampling-based runtime application adaptation approach that automatically determines whether these techniques should be employed for a given platform and input matrix. [Copyright &y& Elsevier]

Abstract: One of the main contributions which Volker Weispfenning made to mathematics is related to Gröbner bases theory. In this paper we present an algorithm for computing all algebraic intermediate subfields in a separably generated unirational field extension (which in particular includes the zero characteristic case). One of the main tools is Gröbner bases theory. Our algorithm also requires computing primitive elements and factoring over algebraic extensions. Moreover, the method can be extended to finitely generated -algebras. [Copyright &y& Elsevier]

Abstract: In this paper we prove rigorous results on persistence of invariant tori and their whiskers. The proofs are based on the parameterization method of [X. Cabré, E. Fontich, R. de la Llave, The parameterization method for invariant manifolds. I. Manifolds associated to non-resonant subspaces, Indiana Univ. Math. J. 52 (2) (2003) 283–328; X. Cabré, E. Fontich, R. de la Llave, The parameterization method for invariant manifolds. II. Regularity with respect to parameters, Indiana Univ. Math. J. 52 (2) (2003) 329–360]. The invariant manifolds results proved here include as particular cases of the usual (strong) stable and (strong) unstable manifolds, but also include other non-resonant manifolds. The method lends itself to numerical implementations whose analysis and implementation is studied in [A. Haro, R. de la Llave, A parameterization method for the computation of invariant tori and their whiskers in quasi-periodic maps: Numerical algorithms, preprint, 2005; A. Haro, R. de la Llave, A parameterization method for the computation of invariant tori and their whiskers in quasi-periodic maps: Numerical implementation and examples, preprint, 2005]. The results are stated as a posteriori results. Namely, that if one has an approximate solution which is not degenerate, then, one has a true solution not too far from the approximate one. This can be used to validate the results of numerical computations. [Copyright &y& Elsevier]

Abstract: Consider the class of exp–log constants, which is constructed from the integers using the field operations, exponentiation and logarithm. Let be such an exp–log constant and let be its size as an expression. Witness conjectures attempt to give bounds for the number of decimal digits which need to be evaluated in order to test whether equals zero. For this purpose, it is convenient to assume that exponentials are only applied to arguments with absolute values bounded by 1. In that context, several witness conjectures have appeared in the literature and the strongest one states that it is possible to choose . In this paper we give a counterexample to this conjecture. We also extend it so as to cover similar, polynomial witness conjectures. [Copyright &y& Elsevier]

Abstract: Given an edge-weighted transportation network G and a list of transportation requests L, the Stacker Crane Problem is to find a minimum-cost tour for a server along the edges of G that serves all requests. The server has capacity one, and starts and stops at the same vertex. In this paper, we consider the case that the transportation network G is a tree, and that the requests are chosen randomly according to a certain class of probability distributions. We show that a polynomial time algorithm by Frederickson and Guan [J. Algorithms 15 (1993) 29–60], which guarantees a 4/3-approximation in the worst case, on almost all inputs finds a minimum-cost tour, along with a certificate of the optimality of its output. [Copyright &y& Elsevier]

Abstract: In this paper we consider the unsplittable flow problem (UFP): given a directed or undirected network with edge capacities and a set of terminal pairs (or requests) with associated demands, find a subset of the pairs of maximum total demand for which a single flow path can be chosen for each pair so that for every edge, the sum of the demands of the paths crossing the edge does not exceed its capacity. We present a collection of new results for the UFP both in the offline (all requests are given from the beginning) and the online (requests arrive at the system one after the other) setting. A fundamental ingredient of our analysis is the introduction of a new graph parameter, the flow number, that aims to capture global communication properties of the network. With the help of the flow number we develop a general method for transforming arbitrary multicommodity flow solutions into solutions that use short paths only. This generalizes a well-known theorem of Leighton and Rao [J. ACM 46 (6) (1999) 787–832] that applies to uniform flows only. Both the parameter and the method may therefore be of independent interest. [Copyright &y& Elsevier]

Abstract: In this article, we generalize a localization theorem of Lovász and Simonovits [Random walks in a convex body and an improved volume algorithm, Random Struct. Algorithms 4–4 (1993) 359–412] which is an important tool to prove dimension-free functional inequalities for log-concave measures. In a previous paper [Fradelizi and Guédon, The extreme points of subsets of -concave probabilities and a geometric localization theorem, Discrete Comput. Geom. 31 (2004) 327–335], we proved that the localization may be deduced from a suitable application of Krein–Milman''s theorem to a subset of log-concave probabilities satisfying one linear constraint and from the determination of the extreme points of its convex hull. Here, we generalize this result to more constraints, give some necessary conditions satisfied by such extreme points and explain how it may be understood as a generalized localization theorem. Finally, using this new localization theorem, we solve an open question on the comparison of the volume of sections of non-symmetric convex bodies in by hyperplanes. A surprising feature of the result is that the extremal case in this geometric inequality is reached by an unusual convex set that we manage to identify. [Copyright &y& Elsevier]