Search

This paper deals with the problem of finding the generators of the solution space for a system of inequalities A ⊗ x ≥ x in max-plus algebra. It provides an improved algorithm which can be used to find a smaller set of generators for the solution space by skipping a large number of invalid generators. [ABSTRACT FROM AUTHOR]

An algorithm for finding the largest singular value of a nonnegative rectangular tensor was recently proposed by Chang, Qi, and Zhou [J. Math. Anal. Appl., 2010, 370: 284-294]. In this paper, we establish a linear convergence rate of the Chang-Qi-Zhou algorithm under a reasonable assumption. [ABSTRACT FROM AUTHOR]

In this paper, we introduce an additional constraint to the one-dimensional variable sized bin packing problem. Practically, some of items have to be packed separately in different bins due to their specific requirement. Therefore, these items are labelled as different types. The bins can be used to pack either any type of items if they are empty originally or the same type of items as what they already have. We model the problem as a type-constrained and variable sized bin packing problem (TVSBPP), and solve it via a branch and bound method. An efficient backtracking procedure is proposed to improve the efficiency of the algorithm. [ABSTRACT FROM AUTHOR]

In this paper, the maximal abelian dimension is computationally obtained for an arbitrary finite-dimensional Lie algebra, defined by its nonzero brackets. More concretely, we describe and implement an algorithm which computes such a dimension by running it in the symbolic computation package MAPLE. Finally, we also show a computational study related to this implementation, regarding both the computing time and the memory used. [ABSTRACT FROM AUTHOR]

Persistent homology with coefficients in a field $$\mathbb {F}$$ coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substantially the amount of matrix operations. In addition, we propose a heuristic to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology. [ABSTRACT FROM AUTHOR]

Let A , B ∈ K [ X , Y ] be two bivariate polynomials over an effective field K , and let G be the reduced Gröbner basis of the ideal I : = ⟨ A , B ⟩ generated by A and B with respect to the usual degree lexicographic order. Assuming A and B sufficiently generic, we design a quasi-optimal algorithm for the reduction of P ∈ K [ X , Y ] modulo G, where "quasi-optimal" is meant in terms of the size of the input A, B, P. Immediate applications are an ideal membership test and a multiplication algorithm for the quotient algebra A : = K [ X , Y ] / ⟨ A , B ⟩ , both in quasi-linear time. Moreover, we show that G itself can be computed in quasi-linear time with respect to the output size. [ABSTRACT FROM AUTHOR]

We describe a parallel polynomial time algorithm for computing the topological Betti numbers of a smooth complex projective variety X. It is the first single exponential time algorithm for computing the Betti numbers of a significant class of complex varieties of arbitrary dimension. Our main theoretical result is that the Castelnuovo-Mumford regularity of the sheaf of differential p-forms on X is bounded by p( em+1) D, where e, m, and D are the maximal codimension, dimension, and degree, respectively, of all irreducible components of X. It follows that, for a union V of generic hyperplane sections in X, the algebraic de Rham cohomology of X∖ V is described by differential forms with poles along V of single exponential order. By covering X with sets of this type and using a Čech process, we obtain a similar description of the de Rham cohomology of X, which allows its efficient computation. Furthermore, we give a parallel polynomial time algorithm for testing whether a projective variety is smooth. [ABSTRACT FROM AUTHOR]

We introduce some modifications and extensions of the concept of index pair in the Conley index theory. We then show how these concepts may be used to overcome some difficulties in obtaining efficient algorithms computing the Conley index. We also present examples of applications to computer assisted proofs in dynamics. [ABSTRACT FROM AUTHOR]

We present a polynomial-time algorithm for computing the zeta function of a smooth projective hypersurface of degree d over a finite field of characteristic p, under the assumption that p is a suitably small odd prime and does not divide d. This improves significantly upon an earlier algorithm of the author and Wan which is only polynomial-time when the dimension is fixed. [ABSTRACT FROM AUTHOR]