Search

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]

Multiplicative relations between the roots of a polynomial in Q [ x ] have drawn much attention in the field of arithmetic and algebra, while the problem of computing these relations is interesting to researchers in many other fields. In this paper, a sufficient condition is given for a polynomial f ∈ Q [ x ] to have only trivial multiplicative relations between its roots, which is a generalization of those sufficient conditions proposed in Smyth (1986) , Baron et al. (1995) and Dixon (1997). Based on the new condition, a subset E ⊂ Q [ x ] is defined and proved to be generic (i.e. , the set Q [ x ] \ E is very small). We develop an algorithm deciding whether a given polynomial f ∈ Q [ x ] is in E and returning a basis of the lattice consisting of the multiplicative relations between the roots of f whenever f ∈ E. The numerical experiments show that the new algorithm is very efficient for the polynomials in E. A large number of polynomials with much higher degrees, which were intractable before, can be handled successfully with the algorithm. [ABSTRACT FROM AUTHOR]

In this paper we describe the method which we applied to successfully compute the primary decomposition of a certain ideal coming from applications in combinatorial algebra and algebraic statistics regarding conditional independence statements with hidden variables. While our method is based on the algorithm for primary decomposition by Gianni, Trager and Zacharias, we were not able to decompose the ideal using the standard form of that algorithm, nor by any other method known to us. [ABSTRACT FROM AUTHOR]

The goal of this paper is to study primitive groups that are contained in the union of maximal (in the symmetric group) imprimitive groups. The study of types of permutations that appear inside primitive groups goes back to the origins of the theory of permutation groups. However, this is another instance of a situation common in mathematics in which a very natural problem turns out to be extremely difficult. Fortunately, the enormous progresses of the last few decades seem to allow a new momentum on the attack to this problem. In this paper we prove that there are infinite families of primitive groups contained in the union of imprimitive groups and propose a new hierarchy for primitive groups based on that fact. In addition we introduce some algorithms to handle permutations, provide the corresponding GAP implementation, solve some open problems, and propose a large list of open problems. [ABSTRACT FROM AUTHOR]

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 Triangular decomposition is one of the standard ways to represent the radical of a polynomial ideal. A general algorithm for computing such a decomposition was proposed by A. Szántó. In this paper, we give the first complete bounds for the degrees of the polynomials and the number of components in the output of the algorithm, providing explicit formulas for these bounds. [ABSTRACT FROM AUTHOR]

This paper presents an algorithm which, given a point and a set of polynomials, constructs a single cylindrical cell containing the point, such that the given polynomials are sign-invariant in the computed cell. To represent a single cylindrical cell, a novel data structure is introduced. The algorithm works with this representation and proceeds incrementally, i.e., first constructing a cell representing the whole real space, and then iterating over the input polynomials, refining the cell at each step to ensure the sign-invariance of the current input polynomial. A merge procedure realizing this refinement is described, and its correctness is proven. The merge procedure is based on McCallum's projection operator, but uses geometric information relative to the input point to reduce the number of projection polynomials computed. The use of McCallum's operator implies the incompleteness of the algorithm in general. However, the algorithm is complete for well-oriented sets of polynomials. Moreover, the incremental approach described in this paper can be easily adapted to a different projection operator. The cell construction algorithm presented in this paper is an alternative to the “model-based” method described by Jovanović and de Moura in a 2012 paper. It generalizes the algorithm described by the first author in a 2013 paper, which could only produce full-dimensional cells, to allow for the construction of cells of arbitrary dimension. While a thorough comparison, whether analytical or empirical, of the new algorithm and the “model-based” approach will be the subject of future work, this paper provides preliminary justification for asserting the superiority of the new method. [ABSTRACT FROM AUTHOR]

In this paper, we study the desingularization problem in the first q -Weyl algebra. We give an order bound for desingularized operators, and thus derive an algorithm for computing desingularized operators in the first q -Weyl algebra. Moreover, an algorithm is presented for computing a generating set of the first q -Weyl closure of a given q -difference operator. As an application, we certify that several instances of the colored Jones polynomial are Laurent polynomial sequences by computing the corresponding desingularized operator. [ABSTRACT FROM AUTHOR]

Let A be a basic and connected finite dimensional algebra and D b ( A ) be the bounded derived category of finitely generated left A -modules. In this paper we consider lengths of tilting objects and indecomposable compact exceptional objects in D b ( A ) , and prove a sufficient condition such that these lengths are bounded by the number of isomorphism classes of simple A -modules. Moreover, we show that algebras satisfying this criterion are bounded derived simple, and describe an algorithm to construct a family of algebras satisfying this condition. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we consider systems of algebraic and non-linear partial differential equations and inequations. We decompose these systems into so-called simple subsystems and thereby partition the set of solutions. For algebraic systems, simplicity means triangularity, square-freeness and non-vanishing initials. Differential simplicity extends algebraic simplicity with involutivity. We build upon the constructive ideas of J. M. Thomas and develop them into a new algorithm for disjoint decomposition. The present paper is a revised version of and includes the proofs of correctness and termination of our decomposition algorithm. In addition, we illustrate the algorithm with further instructive examples and describe its Maple implementation together with an experimental comparison to some other triangular decomposition algorithms. [Copyright &y& Elsevier]

Abstract: In this paper, we summarize our recent work on establishing, for the first time, an algorithm for the symbolic solution of linear boundary problems. We put our work in the frame of Wen-Tsun Wu’s approach to algorithmic problem solving in analysis, geometry, and logic by mapping the significant aspects of the underlying domains into algebra. We briefly compare this with the lines of thought of Wolfgang Groebner. For building up the necessary tower of domains in a generic and flexible way, we use the machinery of algorithmic functors introduced in our Theorema project. The essence of this concept is explained in the first section of the paper. The main part of the paper then describes our symbolic analysis approach to linear boundary problems, which hinges on three basic principles: (1) Differentiation as well as integration is treated axiomatically, setting up an algebraic data structure that can encode the problem statement (differential equation and boundary conditions) and suitable symbolic expressions for their solution (Green’s operators qua integral operators). (2) Abstract boundary problems are introduced as pairs consisting of an epimorphism on a vector space (abstract differential operator) and a subspace of its dual (abstract boundary conditions). (3) Operator algebras are treated by noncommutative polynomials, modulo Groebner bases for certain relation ideals. [Copyright &y& Elsevier]

Abstract: Bisimulation equivalence is decidable in polynomial time for both sequential and commutative normed context-free processes, known as BPA and BPP, respectively. Despite apparent similarity between the two classes, different algorithmic techniques were used in each case. We provide one polynomial-time algorithm that works in a superclass of both normed BPA and BPP. It is derived in the setting of partially-commutative context-free processes, a new process class introduced in the paper. It subsumes both BPA and BPP and seems to be of independent interest. Expressibility issue of the new class, in comparison with the normed PA class, is also tackled in the paper. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate algorithms for some related graph parameters. Each of these asks for a linear ordering of the vertices of the graph (or can be formulated as such), and constructive linear time algorithms for the fixed parameter versions of the problems have been published for several of these. Examples are cutwidth, pathwidth, and directed or weighted variants of these. However, these algorithms have complicated technical details. This paper attempts to present ideas in these algorithms in a different more easily accessible manner, by showing that the algorithms can be obtained by a stepwise modification of a trivial hypothetical non-deterministic algorithm. The methodology is applied to rederive known results for the cutwidth and the pathwidth problem, and obtain new results for several variants of these problems, like directed and weighted variants of cutwidth and modified cutwidth. [Copyright &y& Elsevier]

Abstract: This is the continuation of Montes’ paper “On the canonical discussion of polynomial systems with parameters”. In this paper, we define the Minimal Canonical Comprehensive Gröbner System of a parametric ideal and fix under which hypothesis it exists and is computable. An algorithm to obtain a canonical description of the segments of the Minimal Canonical CGS is given, thus completing the whole MCCGS algorithm (implemented in Maple and Singular). We show its high utility for applications, such as automatic theorem proving and discovering, and compare it with other existing methods. A way to detect a counterexample to deny its existence is outlined, although the high number of tests done give evidence of the existence of the Minimal Canonical CGS. [Copyright &y& Elsevier]

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: System identification consists in finding a model of an unknown system starting from a finite set of noise-corrupted data. A fundamental problem in this context is to asses the accuracy of the identified model. In this paper, the problem is investigated for the case of nonlinear systems within the Set Membership—Information Based Complexity framework of [M. Milanese, C. Novara, Set membership identification of nonlinear systems, Automatica 40(6) (2004) 957–975]. In that paper, a (locally) optimal algorithm has been derived, giving (locally) optimal models in nonlinear regression form. The corresponding (local) radius of information, providing the worst-case identification error, can be consequently used to measure the quality of the identified model. In the present paper, two algorithms are proposed for the computation of the local radius of information: The first provides the exact value but requires a computational complexity exponential in the dimension of the regressor space. The second is approximate but involves a polynomial (quadratic) complexity. [Copyright &y& Elsevier]

Abstract: This paper considers the problem of performing tasks in asynchronous distributed settings. This problem, called Do-All, has been substantially studied in synchronous models, but there is a dearth of efficient algorithms for asynchronous message-passing processors. Do-All can be trivially solved without any communication by an algorithm where each processor performs all tasks. Assuming p processors and t tasks, this requires work Θ(p · t). Thus, it is important to develop subquadratic solutions (when p and t are comparable) by trading computation for communication. Following the observation that it is not possible to obtain subquadratic work when the message delay d is substantial, e.g., d =Θ(t), this work pursues a message-delay-sensitive approach. Here, the upper bounds on work and communication are given as functions of p, t, and d, the upper bound on message delays, however, algorithms have no knowledge of d and they cannot rely on the existence of an upper bound on d. This paper presents two families of asynchronous algorithms achieving, for the first time, subquadratic work as long as d = o (t). The first family uses as its basis a shared-memory algorithm without having to emulate atomic registers assumed by that algorithm. These deterministic algorithms have work O(tp ε + pd⌈t/d⌉ ε ) for any ε >0. The second family uses specific permutations of tasks, with certain combinatorial properties, to sequence the work of the processors. These randomized (deterministic) algorithms have expected (worst-case) work O(t log p + pd log(2+ t/d)). Another important contribution in this work is the first delay-sensitive lower bound for this problem that helps explain the behavior of our algorithms: any randomized (deterministic) algorithm has expected (worst-case) work of Ω(t + pd log d+1 t). [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: Maple’s symbolic evaluator, together with a feature that is usually known as the assume facility, implements a powerful form of conditional rewriting. In a previous paper the authors showed that Maple’s evaluation process can be recast as constraint contextual rewriting (CCR), a form of conditional rewriting that incorporates the services provided by a decision procedure through a well-specified interface. In the present paper, this analysis is extended to a component of the assume facility that deals with problems beyond linear arithmetic and that we call the general solver. This led to the discovery of a fault that causes Maple to return wrong results with some contexts. The reason for this is that the facility wrongly assumes that the general solver is complete in the sense that it uses all the available assumptions in the context. While a simple fix to this problem would reduce the logical strength of the assume facility, we show that a more general approach inspired by techniques available in CCR does not suffer from the problem and naturally leads to stronger forms of simplification. [Copyright &y& Elsevier]

Abstract: This paper advances the design of a unified model for the representation of search in first-order clausal theorem-proving, by extending to tableau-based subgoal-reduction strategies (e.g., model-elimination tableaux), the marked search-graph model, already introduced for ordering-based strategies, those that use (ordered) resolution, paramodulation/superposition, simplification, and subsumption. The resulting analytic marked search-graphs subsume AND–OR graphs, and allow us to represent those dynamic components, such as backtracking and instantiation of rigid variables, that have long been an obstacle to modelling subgoal-reduction strategies properly. The second part of the paper develops for analytic marked search-graphs the bounded search spaces approach to the analysis of infinite search spaces. We analyze how tableau inferences and backtracking affect the bounded search spaces during a derivation. Then, we apply this analysis to measure the effects of regularity and lemmatization by folding-up on search complexity, by comparing the bounded search spaces of strategies with and without these features. We conclude with a discussion comparing the marked search-graphs for tableaux, linear resolution, and ordering-based strategies, showing how this search model applies across these classes of strategies. [Copyright &y& Elsevier]

Information integration systems provide uniform interfaces to varieties of heterogeneous information sources. For query answering in such systems, the current generation of query answering algorithms in local-as-view (source-centric) information integration systems all produce what has been thought of as “the best obtainable” answer, given the circumstances that the source-centric approach introduces incomplete information into the virtual global relations. However, this “best obtainable” answer does not include all information that can be extracted from the sources because it does not allow partial information. Neither does the “best obtainable” answer allow for composition of queries, meaning that querying a result of a previous query will not be equivalentto the composition of the two queries. In this paper, we provide a foundation for information integration, based on the algebraic theory of incomplete information. Our framework allows us to define the semantics of partial facts and introduce the notion of the exact answer—that is the answer that includes partial facts. We show that querying under the exact answer semantics is compositional. We also present two methods for actually computing the exact answer. The first method is tableau-based, and it is a generalization of the “inverse-rules” approach. The second, much more efficient method, is a generalization of the rewriting approach, and it is based on partial containment mappings introduced in the paper. [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]

Abstract: In this paper, we prove that the degree of regularity of square systems, a subfamily of the HFE systems, over a prime finite field of odd characteristic q is exactly q and, therefore, prove that inverting square systems algebraically using Gröbner basis algorithm is exponential, when , where n is the number of variables of the system. [Copyright &y& Elsevier]

Abstract: In this paper we give an insight into the behavior of signature-based Gröbner basis algorithms, like F5, G2V or SB, for inhomogeneous input. On the one hand, it seems that the restriction to sig-safe reductions puts a penalty on the performance. The lost connection between polynomial degree and signature degree can disallow lots of reductions and can lead to an overhead in the computations. On the other hand, the way critical pairs are sorted and corresponding s-polynomials are handled in signature-based algorithms is a very efficient one, strongly connected to sorting w.r.t. the well-known sugar degree of polynomials. [Copyright &y& Elsevier]

Branching Algebra is the natural branching-time generalization of Allen's Interval Algebra. As in the linear case, the consistency problem for Branching Algebra is NP-hard. Branching Algebra has many potential applications in different areas of Artificial Intelligence; therefore, being able to efficiently solve classical problems expressed in Branching Algebra is very important. This can be achieved in two steps: first, by identifying expressive enough, yet tractable fragments of the whole algebra, and, second, by using such fragments to boost the performances of a backtracking algorithm for the whole language. In this paper we study the properties of several such fragments, both from the algebraic and the computational point of view, and we give an almost complete picture of tractable and non-tractable fragments of the Branching Algebra. [ABSTRACT FROM AUTHOR]

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: Goldʼs original paper on inductive inference introduced a notion of an optimal learner. Intuitively, a learner identifies a class of objects optimally iff there is no other learner that: requires as little of each presentation of each object in the class in order to identify that object, and, for some presentation of some object in the class, requires less of that presentation in order to identify that object. Beick considered this notion in the context of function learning, and gave an intuitive characterization of an optimal function learner. Jantke and Beick subsequently characterized the classes of functions that are algorithmically, optimally identifiable. Herein, Goldʼs notion is considered in the context of language learning. It is shown that a characterization of optimal language learners analogous to Beickʼs does not hold. It is also shown that the classes of languages that are algorithmically, optimally identifiable cannot be characterized in a manner analogous to that of Jantke and Beick. Other interesting results concerning optimal language learning include the following. It is shown that strong non-U-shapedness, a property involved in Beickʼs characterization of optimal function learners, does not restrict algorithmic language learning power. It is also shown that, for an arbitrary optimal learner F of a class of languages , F optimally identifies a subclass of iff F is class-preserving with respect to . [Copyright &y& Elsevier]

Abstract: Multiobjective discrete programming is a well-known family of optimization problems with a large spectrum of applications. The linear case has been tackled by many authors during the past few years. However, the polynomial case has not been studied in detail due to its theoretical and computational difficulties. This paper presents an algebraic approach for solving these problems. We propose a methodology based on transforming the polynomial optimization problem to the problem of solving one or more systems of polynomial equations and we use certain Gröbner bases to solve these systems. Different transformations give different methodologies that are theoretically stated and compared by some computational tests via the algorithms that they induce. [Copyright &y& Elsevier]

Abstract: In this paper we describe how an idea centered on the concept of self-saturation allows several improvements in the computation of Gröbner bases via Buchberger’s Algorithm. In a nutshell, the idea is to extend the advantages of computing with homogeneous polynomials or vectors to the general case. When the input data are not homogeneous, we use as a main tool the procedure of a self-saturating Buchberger’s Algorithm. Another strictly related topic is treated later when a mathematical foundation is given to the sugar trick which is nowadays widely used in most of the implementations of Buchberger’s Algorithm. A special emphasis is also given to the case of a single grading, and subsequently some timings and indicators showing the practical merits of our approach. [Copyright &y& Elsevier]

Abstract: In this paper we present an algorithm for the computation of a diagonal form of a matrix over non-commutative Euclidean domain over a field with the help of Gröbner bases. We propose a general framework of Ore localizations of non-commutative -algebras and show its merits and constructiveness. It allows us to handle, among others, common operator algebras with rational coefficients. We introduce the splitting of the computation of a normal form (like the Jacobson form over simple domain) for matrices over Ore localizations into the diagonalization (the computation of a diagonal form of a matrix) and the normalization (the computation of the normal form of a diagonal matrix). These ideas are also used for the computation of the Smith normal form in the commutative case. We give a special algorithm for the normalization of a diagonal matrix over the rational Weyl algebra and present counterexamples to its idea over rational shift and -Weyl algebras. Our implementation of the algorithm in Singular:Plural relies on the fraction-free polynomial strategy, details of which will be described in the forthcoming article. It shows quite an impressive performance, compared with methods which directly use fractions. In particular, we experience quite a moderate swell of coefficients and obtain uncomplicated transformation matrices. We leave questions on the algorithmic complexity of this algorithm open, but we stress the practical applicability of the proposed method to a large class of non-commutative algebras. [Copyright &y& Elsevier]

Abstract: A classical measure of similarity between strings is the length of the longest common subsequence (LCS) between the two given strings. The search for efficient algorithms for finding the LCS has been going on for more than three decades. To date, all known algorithms may take quadratic time (shaved by logarithmic factors) to find large LCS. In this paper, the problem of approximating LCS is studied, while focusing on the hard inputs for this problem, namely, approximating LCS of near-linear size in strings over a relatively large alphabet (of size at least for some constant , where is the length of the string). We show that, any given string over a relatively large alphabet can be embedded into a locally non-repetitive string. This embedding has a negligible additive distortion for strings that are not too dissimilar in terms of the edit distance. We also show that LCS can be efficiently approximated in locally-non-repetitive strings. Our new method (the embedding together with the approximation algorithm) gives a strictly sub-quadratic time algorithm (i.e., of complexity for some constant ) which can find common subsequences of linear (and near linear) size that cannot be detected efficiently by the existing tools. [Copyright &y& Elsevier]

Abstract: In this paper, we present our recent development of a model-domain environment robust adaptation algorithm, which demonstrates high performance in the standard Aurora 2 speech recognition task. The algorithm consists of two main steps. First, the noise and channel parameters are estimated using multi-sources of information including a nonlinear environment-distortion model in the cepstral domain, the posterior probabilities of all the Gaussians in speech recognizer, and truncated vector Taylor series (VTS) approximation. Second, the estimated noise and channel parameters are used to adapt the static and dynamic portions (delta and delta–delta) of the HMM means and variances. This two-step algorithm enables joint compensation of both additive and convolutive distortions (JAC). The hallmark of our new approach is the use of a nonlinear, phase-sensitive model of acoustic distortion that captures phase asynchrony between clean speech and the mixing noise. In the experimental evaluation using the standard Aurora 2 task, the proposed Phase-JAC/VTS algorithm achieves 93.32% word accuracy using the clean-trained complex HMM backend as the baseline system for the unsupervised model adaptation. This represents high recognition performance on this task without discriminative training of the HMM system. The experimental results show that the phase term, which was missing in all previous HMM adaptation work, contributes significantly to the achieved high recognition accuracy. [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: Compressive sampling offers a new paradigm for acquiring signals that are compressible with respect to an orthonormal basis. The major algorithmic challenge in compressive sampling is to approximate a compressible signal from noisy samples. This paper describes a new iterative recovery algorithm called CoSaMP that delivers the same guarantees as the best optimization-based approaches. Moreover, this algorithm offers rigorous bounds on computational cost and storage. It is likely to be extremely efficient for practical problems because it requires only matrix–vector multiplies with the sampling matrix. For compressible signals, the running time is just , where N is the length of the signal. [Copyright &y& Elsevier]

Abstract: In this paper, we consider how to optimize I/O server placement in order to improve parallel I/O performance in switch-based clusters. The significant advances in cluster networks in recent years have made it practical to connect tens of thousands of hosts via networks that have enormous and scalable total capacity, and in which communications between a host and any other host incur the same cost. The same cost property frees users from consideration of network contention and allows them to concentrate on load-balancing issues. We formulate the server placement problem on a cluster that has the same cost property as a weighted bipartite matching with the goal of balancing the workload on the I/O nodes. To find an optimal solution to this problem, we propose an algorithm, called Load Balance Matching (LBM), where is the number of compute nodes and is the number of I/O servers. We also investigate server placement for general clusters in which multiple same-cost subclusters are interconnected to form a large cluster. This class of clusters typically adopt irregular topologies that allow the construction of scalable systems with an incremental expansion capability. Also, due to the limited bandwidth on network links between subclusters, network link contention is a major concern when distributing servers over the entire network. We show that finding an optimal placement strategy for general clusters with the goal of minimizing link contention is computationally intractable. To resolve this problem, we propose a hierarchical strategy that places servers in two steps. First, to minimize link contention, we decide which subcluster each server should be assigned to. We propose a tree-based heuristic algorithm, called Load Balance Traversing (LBT), to solve this problem. In the second step, the LBM algorithm decides the location of each server within a subcluster. Our simulation results demonstrate that LBT achieves a significant improvement in parallel I/O performance over four other algorithms, and is near-optimal in some cases. [Copyright &y& Elsevier]

Abstract: Fault-tolerant scheduling is an imperative step for large-scale computational Grid systems, as often geographically distributed nodes co-operate to execute a task. By and large, primary-backup approach is a common methodology used for fault tolerance wherein each task has a primary and a backup on two different processors. In this paper, we address the problem of how to schedule DAGs in Grids with communication delays so that service failures can be avoided in the presence of processors faults. The challenge is, that as tasks in a DAG have dependence on each other, a task must be scheduled to make sure that it will succeed when any of its predecessors fails due to a processor failure. We first propose a communication model and determine when communications between a backup and backups of its successors are necessary. Then we determine when a backup can start and its eligible processors so as to guarantee that every DAG can complete upon any processor failure. We develop two algorithms to schedule backups, which minimize response time and replication cost, respectively. We also develop a suboptimal algorithm which targets minimizing replication cost while not affecting response time. We conduct extensive simulation experiments to quantify the performance of the proposed algorithms. [Copyright &y& Elsevier]

Abstract: This paper presents two new randomized distributed algorithms for the generation of acyclic orientations upon anonymous distributed systems of arbitrary topology. Both algorithms, called Alg-Neighbors and Alg-Edges, make use of biased and unbiased dice having faces, and are analyzed in terms of correctness, expected time complexity and rate of convergence. First, the Alg-Neighbors algorithm is presented as a generalization of the Calabrese/França algorithm for dice (or coins) with 2 faces. It is proved that a convenient biasing function applied to all dice changes the expected time complexity from sub-exponential, i.e., (for unbiased dice with faces), to , where is the number of the system’s nodes. Next, it is shown that the Alg-Edges algorithm is able to produce acyclic orientations in steps with high probability, where denotes the total number of edges. Finally, a speed of convergence versus quality of acyclic orientation generation (associated number of colors) tradeoff is identified between Alg-Neighbors and Alg-Edges algorithms. Computational experiments were carried out in order to provide a more accurate description of the behavior of both algorithms. [Copyright &y& Elsevier]

Abstract: It is no longer believed that DNA computing will outperform digital computers when it comes to the computation of intractable problems. In this paper, we emphasise the in silico implementation of DNA-inspired algorithms as the only way to compete with other algorithms for solving NP-complete problems. For this, we provide sticker algorithms for some of the most representative NP-complete graph problems. The simple data structures and bit-vertical operations make them suitable for some parallel architectures. The parallel algorithms might solve either moderate-size problems in an exact manner or, when combined with a heuristic, large problems in polynomial time. [Copyright &y& Elsevier]

Abstract: This paper presents a new algorithm for solving a system of polynomials, in a domain of . It can be seen as an improvement of the Interval Projected Polyhedron algorithm proposed by Sherbrooke and Patrikalakis [Sherbrooke, E.C., Patrikalakis, N.M., 1993. Computation of the solutions of nonlinear polynomial systems. Comput. Aided Geom. Design 10 (5), 379–405]. It uses a powerful reduction strategy based on univariate root finder using Bernstein basis representation and Descarte’s rule. We analyse the behavior of the method, from a theoretical point of view, shows that for simple roots, it has a local quadratic convergence speed and gives new bounds for the complexity of approximating real roots in a box of . The improvement of our approach, compared with classical subdivision methods, is illustrated on geometric modeling applications such as computing intersection points of implicit curves, self-intersection points of rational curves, and on the classical parallel robot benchmark problem. [Copyright &y& Elsevier]

Abstract: The aim of the paper is to demonstrate the superiority of Cartan’s method over direct methods based on differential elimination for handling otherwise intractable equivalence problems. In this sense, using our implementation of Cartan’s method, we establish two new equivalence results. We establish when a system of second order ODEs is equivalent to flat system (second derivations are zero), and when a system of holomorphic PDEs with two independent variables and one dependent variable is flat. We consider the problem of finding transformation that brings a given equation to the target one. We shall see that this problem becomes algebraic when the symmetry pseudogroup of the target equation is zerodimensional. We avoid the swelling of the expressions, by using non-commutative derivations adapted to the problem. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to study multidimensional continued fraction algorithm over the field of formal power series. In the case of the Brun algorithm by using its homogenous version, we prove that it converges. [Copyright &y& Elsevier]

Abstract: A vertex ranking of an undirected graph G is a labeling of the vertices of G with integers such that every path connecting two vertices with the same label i contains an intermediate vertex with label . A vertex ranking of G is called optimal if it uses the minimum number of distinct labels among all possible vertex rankings. The problem of finding an optimal vertex ranking for general graphs is NP-hard, and NP-hard even for chordal graphs which form a superclass of block graphs. In this paper, we present the first polynomial algorithm which runs in time for finding an optimal vertex ranking of a block graph G, where n and denote the number of vertices and the maximum degree of G, respectively. [Copyright &y& Elsevier]

Abstract: This paper investigates both the precision and the model checking efficiency of abstract models designed to preserve branching time logics w.r.t. a 3-valued semantics. Current abstract models use ordinary transitions to over approximate the concrete transitions, while they use hyper transitions to under approximate the concrete transitions. In this work, we refer to precision measured w.r.t. the choice of abstract states, independently of the formalism used to describe abstract models. We show that current abstract models do not allow maximal precision. We suggest a new class of models and a construction of an abstract model which is most precise w.r.t. any choice of abstract states. As before, the construction of such models might involve an exponential blowup, which is inherent by the use of hyper transitions. We therefore suggest an efficient algorithm in which the abstract model is constructed during model checking, by need. Our algorithm achieves maximal precision w.r.t. the given property while remaining quadratic in the number of abstract states. To complete the picture, we incorporate it into an abstraction-refinement framework. [Copyright &y& Elsevier]

Abstract: The proceedings of FOCS’98 contain a paper by Zakariae Bouziane, who sketches a new representation of the Petri net reachability problem and claims to provide a new algorithm solving the problem. In this note, the essence of Bouziane’s approach is explained, and a serious flaw of the algorithm is exposed. [Copyright &y& Elsevier]

Abstract: Leonard and Pellikaan developed the qth power algorithm to compute module bases for the integral closure of the polynomial ring in a class of function fields. In this paper, their algorithm is adapted to efficiently obtain an -basis for a class of Riemann–Roch spaces without having to compute the entire integral closure. This reformulation allows one to determine the complexity of the algorithm. Further, we obtain a simple characterization of the integral closure. [Copyright &y& Elsevier]

Abstract: This paper presents an algorithm for fast sorting of large lists using modern GPUs. The method achieves high speed by efficiently utilizing the parallelism of the GPU throughout the whole algorithm. Initially, GPU-based bucketsort or quicksort splits the list into enough sublists then to be sorted in parallel using merge-sort. The algorithm is of complexity , and for lists of 8 M elements and using a single Geforce 8800 GTS-512, it is 2.5 times as fast as the bitonic sort algorithms, with standard complexity of , which for a long time was considered to be the fastest for GPU sorting. It is 6 times faster than single CPU quicksort, and 10% faster than the recent GPU-based radix sort. Finally, the algorithm is further parallelized to utilize two graphics cards, resulting in yet another 1.8 times speedup. [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: The Singular Value Decomposition (SVD) is a vital problem that finds a place in numerous application domains in science and engineering. As an example, SVDs are used in processing voluminous datasets. Many sequential and parallel algorithms have been proposed to compute SVDs. The best known sequential algorithms take cubic time. This amount of time may not be acceptable especially when the data size is large. Thus parallel algorithms are desirable. In this paper, we present a novel technique for the parallel computation of SVDs. This technique yields impressive speedups. We discuss implementation of our technique on parallel models of computing such as the mesh and the PRAM. We also present an experimental evaluation of our technique. [Copyright &y& Elsevier]

Abstract: In this paper, we study the structure of an assosymmetric algebra A by investigating various radicals and show that the Wedderburn principal theorem holds when has no 1-dimensional factor where is the radical of A and also discuss a Pierce decomposition of A. [Copyright &y& Elsevier]