Search

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 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]

Pisot numbers are real algebraic integers bigger than 1, whose other conjugates all have modulus smaller than 1. In this paper we deal with the algorithmic problem of finding the smallest Pisot unit generating a given number field. We first solve this problem in all real fields, then we consider the analogous problem involving the so called complex Pisot numbers and we solve it in all number fields that admit such a generator, in particular this includes all fields without CM. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we compute and manipulate the support of monomial resolutions based on iterated mapping cones. We derive in this way algorithms to obtain homological and numerical invariants of monomial ideals without actually computing their resolution. Our computations include Betti diagrams, Hilbert series and irreducible decompositions. The algorithms derived by the method presented in the paper are efficient in practice as shown by experiments. [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: Irreducible decomposition of monomial ideals has an increasing number of applications from biology to pure math. This paper presents the Slice Algorithm for computing irreducible decompositions, Alexander duals and socles of monomial ideals. The paper includes experiments showing good performance in practice. [Copyright &y& Elsevier]

Abstract: This paper deals with the problem of finding, for a given parametrization of an algebraic variety of arbitrary dimension, another parametrization with coefficients over a smaller field. We proceed adapting, to the parametric case, a construction introduced by A. Weil for implicitly given varieties. We find that this process leads to the consideration of new varieties of a particular kind (ultraquadrics, in the terminology of this paper) in order to check, algorithmically, several interesting properties of the given variety , such as the property of being reparametrizable over the smaller field. [Copyright &y& Elsevier]

Abstract: In this paper we address the decision problem for a fragment of unquantified formulae of real analysis, which, besides the operators of Tarski’s theory of reals, includes also strict and non-strict predicates expressing comparison, monotonicity, concavity, and convexity of continuous real functions over possibly unbounded intervals. The decision result is obtained by proving that a formula of our fragment is satisfiable if and only if it admits a parametric “canonical” model, whose existence can be tested by solving a suitable unquantified formula, expressed in the decidable language of Tarski’s theory of reals and involving the numerical variables of the initial formula plus various other parameters. This paper generalizes a previous decidability result concerning a more restrictive fragment in which predicates relative to infinite intervals or stating strict concavity and convexity were not expressible. [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]

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]

Assume that we wish to expand the product h = fg of two formal power series f and g. Classically, there are two types of algorithms to do this: zealous algorithms first expand f and g up to order n, multiply the results and truncate at order n. Lazy algorithms on the contrary compute the coefficients of f, g and h gradually and they perform no more computations than strictly necessary at each stage. In particular, at the moment we compute the coefficient hiof ziin h, only f0,⋯ , fiand g0,⋯ , giare known.Lazy algorithms have the advantage that the coefficients of f and g may actually depend on “previous" coefficients of h, as long as they are computed before they are needed in the multiplication, i.e. the coefficients fiand gimay depend on h0,⋯ , hi − 1. For this reason, lazy algorithms are extremely useful when solving functional equations in rings of formal power series. However, lazy algorithms have the disadvantage that the classical asymptotically fast multiplication algorithms on polynomials—such as the divide and conquer algorithm and fast Fourier multiplication—cannot be used.In a previous paper, we therefore introduced relaxed algorithms, which share the property concerning the resolution of functional equations with lazy algorithms, but perform slightly more computations than lazy algorithms during the computation of a given coefficient of h. These extra computations anticipate the computations of the next coefficients of h and dramatically improve the asymptotic time complexities of such algorithms.In this paper, we survey several classical and new zealous algorithms for manipulating formal power series, including algorithms for multiplication, division, resolution of differential equations, composition and reversion. Next, we give various relaxed algorithms for these operations. All algorithms are specified in great detail and we prove theoretical time and space complexity bounds. Most algorithms have been experimentally implemented in C++ and we provide benchmarks. We conclude by some suggestions for future developments and a discussion of the fitness of the lazy and relaxed approaches for specific applications.This paper is intended both for those who are interested in the most recent algorithms for the manipulation of formal power series and for those who want to actually implement a power series library into a computer algebra system. [Copyright &y& Elsevier]

We describe a subdivision algorithm for isolating the complex roots of a polynomial F ∈ C [ x ] . Given an oracle that provides approximations of each of the coefficients of F to any absolute error bound and given an arbitrary square B in the complex plane containing only simple roots of F , our algorithm returns disjoint isolating disks for the roots of F in B . Our complexity analysis bounds the absolute error to which the coefficients of F have to be provided, the total number of iterations, and the overall bit complexity. It further shows that the complexity of our algorithm is controlled by the geometry of the roots in a near neighborhood of the input square B , namely, the number of roots, their absolute values and pairwise distances. The number of subdivision steps is near-optimal. For the benchmark problem , namely, to isolate all the roots of a polynomial of degree n with integer coefficients of bit size less than τ , our algorithm needs O ˜ ( n 3 + n 2 τ ) bit operations, which is comparable to the record bound of Pan (2002) . It is the first time that such a bound has been achieved using subdivision methods, and independent of divide-and-conquer techniques such as Schönhage's splitting circle technique. Our algorithm uses the quadtree construction of Weyl (1924) with two key ingredients: using Pellet's Theorem (1881) combined with Graeffe iteration, we derive a “soft-test” to count the number of roots in a disk. Using Schröder's modified Newton operator combined with bisection, in a form inspired by the quadratic interval method from Abbot (2006), we achieve quadratic convergence towards root clusters. Relative to the divide-conquer algorithms, our algorithm is quite simple with the potential of being practical. This paper is self-contained: we provide pseudo-code for all subroutines used by our algorithm. [ABSTRACT FROM AUTHOR]

The computation of Kronecker coefficients is a challenging problem with a variety of applications. In this paper we present an approach based on methods from symplectic geometry and residue calculus. We outline a general algorithm for the problem and then illustrate its effectiveness in several interesting examples. Significantly, our algorithm does not only compute individual Kronecker coefficients, but also symbolic formulas that are valid on an entire polyhedral chamber. As a byproduct, we are able to compute several Hilbert series. [ABSTRACT FROM AUTHOR]

Suppose M is a finite cell decomposition of a space X and that for 0 = t 0 < t 1 < ⋯ < t r = 1 we have a discrete Morse function F t i : M → R . In this paper, we study the births and deaths of critical cells for the functions F t i and present an algorithm for pairing the cells that occur in adjacent slices. We first study the case where the cell decomposition of X is the same for each t i , and then generalize to the case where they may differ. This has potential applications in topological data analysis, where one has function values at a sample of points in some region in space at several different times or at different levels in an object. [ABSTRACT FROM AUTHOR]

The Morse–Smale complex is an important tool for global topological analysis in various problems of computational geometry and topology. Algorithms for Morse–Smale complexes have been presented in case of piecewise linear manifolds ( Edelsbrunner et al., 2003a ). However, previous research in this field is incomplete in the case of smooth functions. In the current paper we address the following question: Given an arbitrarily complex Morse–Smale system on a planar domain, is it possible to compute its certified (topologically correct) Morse–Smale complex? Towards this, we develop an algorithm using interval arithmetic to compute certified critical points and separatrices forming the Morse–Smale complexes of smooth functions on bounded planar domain. Our algorithm can also compute geometrically close Morse–Smale complexes. [ABSTRACT FROM AUTHOR]

Forman's discrete Morse theory appeared to be useful for providing filtration-preserving reductions of complexes in the study of persistent homology. So far, the algorithms computing discrete Morse matchings have only been used for one-dimensional filtrations. This paper is perhaps the first attempt in the direction of extending such algorithms to multidimensional filtrations. An initial framework related to Morse matchings for the multidimensional setting is proposed, and a matching algorithm given by King, Knudson, and Mramor is extended in this direction. The correctness of the algorithm is proved, and its complexity analyzed. The algorithm is used for establishing a reduction of a simplicial complex to a smaller but not necessarily optimal cellular complex. First experiments with filtrations of triangular meshes are presented. [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]

In Kaltofen and Yang (2014) we give an algorithm based algebraic error-correcting decoding for multivariate sparse rational function interpolation from evaluations that can be numerically inaccurate and where several evaluations can have severe errors (“outliers”). Our 2014 algorithm can interpolate a sparse multivariate rational function from evaluations where the error rate 1 / q is quite high, say q = 5 . For the algorithm with exact arithmetic and exact values at non-erroneous points, one avoids quadratic oversampling by using random evaluation points. Here we give the full probabilistic analysis for this fact, thus providing the missing proof to Theorem 2.1 in Section 2 of our ISSAC 2014 paper. Our argumentation already applies to our original 2007 sparse rational function interpolation algorithm ( Kaltofen et al., 2007 ), where we have experimentally observed that for T unknown non-zero coefficients in a sparse candidate ansatz one only needs T + O ( 1 ) evaluations rather than O ( T 2 ) (cf. Candès and Tao sparse sensing), the latter of which we have proved in 2007. Here we prove that T + O ( 1 ) evaluations at random points indeed suffice. [ABSTRACT FROM AUTHOR]

In this paper, we present a new method for computing bounded-degree factors of lacunary multivariate polynomials. In particular for polynomials over number fields, we give a new algorithm that takes as input a multivariate polynomial f in lacunary representation and a degree bound d and computes the irreducible factors of degree at most d of f in time polynomial in the lacunary size of f and in d . Our algorithm, which is valid for any field of zero characteristic, is based on a new gap theorem that enables reducing the problem to several instances of (a) the univariate case and (b) low-degree multivariate factorization. The reduction algorithms we propose are elementary in that they only manipulate the exponent vectors of the input polynomial. The proof of correctness and the complexity bounds rely on the Newton polytope of the polynomial, where the underlying valued field consists of Puiseux series in a single variable. [ABSTRACT FROM AUTHOR]

This paper describes the fastest quantum algorithm at this moment for the quantum Fourier transform (QFT) over symmetric groups. We provide a new FFT (classical) algorithm over symmetric groups and then transform it to a quantum algorithm. The complexity of our QFT algorithm is O ( n 3 log ⁡ n ) , faster than the existing O ( n 4 log ⁡ n ) QFT algorithm. In addition, we show that the algorithm can be performed in O ( n 3 ) if the use of threshold gates is allowed. [ABSTRACT FROM AUTHOR]

In this paper, we present a new algorithm and an experimental implementation for factoring elements in the polynomial n th Weyl algebra, the polynomial n th shift algebra, and Z n -graded polynomials in the n th q _ -Weyl algebra. The most unexpected result is that this noncommutative problem of factoring partial differential operators can be approached effectively by reducing it to the problem of solving systems of polynomial equations over a commutative ring. In the case where a given polynomial is Z n -graded, we can reduce the problem completely to factoring an element in a commutative multivariate polynomial ring. The implementation in Singular is effective on a broad range of polynomials and increases the ability of computer algebra systems to address this important problem. We compare the performance and output of our algorithm with other implementations in major computer algebra systems on nontrivial examples. [ABSTRACT FROM AUTHOR]

Let R be a non-commutative PID finitely generated as a module over its center C . In this paper we give a criterion to decide effectively whether two given elements f , g ∈ R are similar, that is, if there exists an isomorphism of left R -modules between R / R f and R / R g . Since these modules are of finite length, we also consider the more general problem of deciding when two given left R -modules of finite length are isomorphic. This criterion allows the design of algorithms when R is an Ore extension of a skew-field whose center is a commutative polynomial ring. We propose two methods which, essentially, check the equality of the rational canonical forms of certain matrices with coefficients in C associated to each of the modules. These algorithms are based on the fact that, if R is finitely generated as a C -module, then the existence of an isomorphism of R -modules can be reduced to checking the existence of an isomorphism of C -modules. Actually, we prove this result in the realm of non-commutative principal ideal domains, generalizing a version given by Jacobson for some Ore extensions of a skew field by an automorphism. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the notion of isoclinism among crossed modules and describe various properties of the notion. We give an algorithm for checking isoclinism among crossed modules and apply the algorithm (implemented in GAP) to classify certain crossed modules. [ABSTRACT FROM AUTHOR]

The main goal of the paper is to present an algorithm to realize the theoretical method by Berlyand and Mityushev (2001, 2005) for computations of the effective conductivity of fibrous composites expressed in therms of the linear combinations of the basic e -sums. Algorithms are presented in Mathematical Pseudo-language with examples in Mathematica ® . A method for simplifying the basic e -sums by reducing mirror terms is presented. Developed algorithms are applied to the optimal packing problem of disks in the plane. [ABSTRACT FROM AUTHOR]

Computing the roots of a univariate polynomial is a fundamental and long-studied problem of computational algebra with applications in mathematics, engineering, computer science, and the natural sciences. For isolating as well as for approximating all complex roots, the best algorithm known is based on an almost optimal method for approximate polynomial factorization, introduced by Pan in 2002. Pan's factorization algorithm goes back to the splitting circle method from Schönhage in 1982. The main drawbacks of Pan's method are that it is quite involved 2 2 In Victor Pan's own words: “Our algorithms are quite involved, and their implementation would require a non-trivial work, incorporating numerous known implementation techniques and tricks”. In fact, we are not aware of any implementation of Pan's method. and that all roots have to be computed at the same time. For the important special case, where only the real roots have to be computed, much simpler methods are used in practice; however, they considerably lag behind Pan's method with respect to complexity. In this paper, we resolve this discrepancy by introducing a hybrid of the Descartes method and Newton iteration, denoted A New Dsc , which is simpler than Pan's method, but achieves a run-time comparable to it. Our algorithm computes isolating intervals for the real roots of any real square-free polynomial, given by an oracle that provides arbitrary good approximations of the polynomial's coefficients. A New Dsc can also be used to only isolate the roots in a given interval and to refine the isolating intervals to an arbitrary small size; it achieves near optimal complexity for the latter task. [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]

Recently, Lombardi, Quitté and Yengui have given a Gröbner-free algorithm which computes the V -saturation of any finitely generated submodule of V [ X ] n , where V is a valuation domain. The goal of this paper is to clarify this algorithm, to give precise complexity bounds, and a complete submodule membership test for the saturation. As application, we give precise degree bounds on syzygies over V [ X ] . [ABSTRACT FROM AUTHOR]

Let R be a discrete valuation ring (DVR) and K be its fraction field. If M is a matrix over R admitting an LU decomposition, it could happen that the entries of the factors L and U do not lie in R , but just in K . Having a good control on the valuations of these entries is very important for algorithmic applications. In the paper, we prove that on average these valuations are not too large and explain how one can apply this result to provide an efficient algorithm computing a basis of a coherent sheaf over A K 1 from the knowledge of its stalks. [ABSTRACT FROM AUTHOR]

The notion of strict equivalence for order one differential equations of the form f ( y ′ , y , z ) = 0 with coefficients in a finite extension K of C ( z ) is introduced. The equation gives rise to a curve X over K and a derivation D on its function field K ( X ) . Procedures are described for testing strict equivalence, strict equivalence to an autonomous equation, computing algebraic solutions and verifying the Painlevé property. These procedures use known algorithms for isomorphisms of curves over an algebraically closed field of characteristic zero, the Risch algorithm and computation of algebraic solutions. The most involved cases concern curves X of genus 0 or 1. This paper complements work of M. Matsuda and of G. Muntingh & M. van der Put. [ABSTRACT FROM AUTHOR]

We consider the problem of counting (stable) equilibriums of an important family of algebraic differential equations modeling multistable biological regulatory systems. The problem can be solved, in principle, using real quantifier elimination algorithms, in particular real root classification algorithms. However, it is well known that they can handle only very small cases due to the enormous computing time requirements. In this paper, we present a special algorithm which is much more efficient than the general methods. Its efficiency comes from the exploitation of certain interesting structures of the family of differential equations. [ABSTRACT FROM AUTHOR]

Mumford showed that Schottky subgroups of PGL ( 2 , K ) give rise to certain curves, now called Mumford curves, over a non-archimedean field K . Such curves are foundational to subjects dealing with non-archimedean varieties, including Berkovich theory and tropical geometry. We develop and implement numerical algorithms for Mumford curves over the field of p -adic numbers. A crucial and difficult step is finding a good set of generators for a Schottky group, a problem solved in this paper. This result allows us to design and implement algorithms for tasks such as: approximating the period matrices of the Jacobians of Mumford curves; computing the Berkovich skeleta of their analytifications; and approximating points in canonical embeddings. We also discuss specific methods and future work for hyperelliptic Mumford curves. [ABSTRACT FROM AUTHOR]

In this paper, the concept of sparse difference resultant for a Laurent transformally essential system of difference polynomials is introduced and a simple criterion for the existence of sparse difference resultant is given. The concept of transformally homogenous polynomial is introduced and the sparse difference resultant is proved to be transformally homogenous. It is shown that the vanishing of the sparse difference resultant gives a necessary condition for the corresponding difference polynomial system to have non-zero solutions. Order and degree bounds for the sparse difference resultant are given. Based on these bounds, an algorithm to compute the sparse difference resultant is proposed, which is single exponential in terms of the number of variables, the Jacobi number, and the size of the Laurent transformally essential system. Furthermore, the precise order and degree, a determinant representation, and a Poisson-type product formula for the difference resultant are given. [ABSTRACT FROM AUTHOR]

Let M be a given positive integer and r = ( r δ ) δ | M a sequence indexed by the positive divisors δ of M . In this paper we present an algorithm that takes as input a generating function of the form ∑ n = 0 ∞ a r ( n ) q n : = ∏ δ | M ∏ n = 1 ∞ ( 1 − q δ n ) r δ and positive integers m , N and t ∈ { 0 , … , m − 1 } . Given this data we compute a set P m , r ( t ) which contains t and is uniquely defined by m , r and t . Next we decide if there exists a sequence ( s δ ) δ | N indexed by the positive divisors δ of N , and modular functions b 1 , … , b k on Γ 0 ( N ) (where each b j equals the product of finitely many terms from { q δ / 24 ∏ n = 1 ∞ ( 1 − q δ n ) : δ | N } ), such that: q α ∏ δ | N ∏ n = 1 ∞ ( 1 − q δ n ) s δ × ∏ t ′ ∈ P m , r ( t ) ∑ n = 0 ∞ a ( m n + t ′ ) q n = c 1 b 1 + ⋯ + c k b k for some c 1 , ⋯ , c k ∈ Q and α : = ∑ δ | N δ s δ 24 + ∑ t ′ ∈ P m , r ( t ) 24 t ′ + ∑ δ | M δ r δ 24 m . Our algorithm builds on work by Rademacher (1942) , Newman (1959) , and Kolberg (1957) . [ABSTRACT FROM AUTHOR]

In this paper, we use the theory of theta functions to generalise to all abelian varieties the usual Miller's algorithm to compute a function associated with a principal divisor. We also explain how to use the Frobenius morphism on abelian varieties defined over a finite field in order to shorten the loop of the Weil and Tate pairings algorithms. This extends preceding results about ate and twisted ate pairings to all abelian varieties. Then building upon the two preceding ingredients, we obtain a variant of optimal pairings on abelian varieties. Finally, by introducing new addition formulas, we explain how to compute optimal pairings on Kummer varieties. We compare in term of performance the resulting algorithms to the algorithms already known in the genus one and two case. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we consider Artinian modules over power series rings endowed with a Frobenius map. We describe a method for finding the set of all prime annihilators of submodules which are preserved by the given Frobenius map and on which the Frobenius map is not nilpotent. This extends the algorithm by Karl Schwede and the first author, which solved this problem for submodules of the injective hull of the residue field. The Matlis dual of this problem asks for the radical annihilators of quotients of free modules by submodules preserved by a given Frobenius near-splitting, and the same method solves this dual problem in the F-finite case. [Copyright &y& Elsevier]

Faugèreʼs F5 algorithm (Faugère, 2002) is the fastest known algorithm to compute Gröbner bases. It has a signature-based and an incremental structure that allow to apply the F5 criterion for deletion of unnecessary reductions. In this paper, we present an involutive completion algorithm which outputs a minimal involutive basis. Our completion algorithm has a non-incremental structure and in addition to the involutive form of Buchbergerʼs criteria it applies the F5 criterion whenever this criterion is applicable in the course of completion to involution. In doing so, we use the G2V form of the F5 criterion developed by Gao, Guan and Volny IV (Gao et al., 2010a). To compare the proposed algorithm, via a set of benchmarks, with the Gerdt–Blinkov involutive algorithm (Gerdt and Blinkov, 1998) (which does not apply the F5 criterion) we use implementations of both algorithms done on the same platform in Maple. [ABSTRACT FROM AUTHOR]

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]

Abstract: The existence of rational rotation-minimizing frames on polynomial space curves is characterized by the satisfaction of a certain identity among rational functions. Part 2 of Remark 5.1 in the original paper states an inequality among the degrees of the denominators of these rational functions, but the proof given therein was incomplete. A formal proof of this inequality, which is essential to the complete categorization of rational rotation-minimizing frames on polynomial space curves, appears to be a rather formidable task. Since all known examples and special cases suggest that the inequality is correct, it is restated here as a conjecture rather than a definitive result, and some preliminary steps towards the proof are presented. [Copyright &y& Elsevier]

Abstract: In this paper, an algorithm is given for determining the topology of an algebraic space curve and to compute a certified rational parametric approximation of the algebraic space curve. The algorithm works by extending to dimension one the local generic position method for solving zero-dimensional polynomial equation systems. Here, certified means that the approximation curve and the original curve have the same topology and their Hausdorff distance is smaller than a given precision. The main advantage of the algorithm, inherited from the local generic position method, is that the topology computation and approximation for a space curve are directly reduced to the same tasks for two plane curves. In particular, an error bound of the approximation space curve is deduced explicitly from the error bounds of the approximation plane curves. The complexity of the algorithm is also analyzed. Its effectivity is shown on some non-trivial examples. [Copyright &y& Elsevier]

Abstract: The computation of approximate Gröbner bases is reported to be highly unstable in the literature. Selecting a suitable length of floats is helpful for stabilizing this computation. In this paper, we present a method to compute such a suitable length of floats. We concentrate on a family of polynomial systems sharing the same support and study the relation between the lengths of floats and the coefficients of relevant polynomials. Then we give a reference length of floats for all the polynomial systems in the family. One feature of our method is that it need not utilize numerical algorithms of Gröbner bases. Hence, our method can avoid the influence of the instabilities of the existing numerical algorithms and thus will be helpful for designing stable ones (e.g., stable Shirayanagiʼs algorithm). Experiments show that our method can work out reliable and reasonably large lengths of floats for most of the tested benchmarks. [Copyright &y& Elsevier]

Abstract: We discuss parametric polynomial systems, with algorithms for real root classification and triangular decomposition of semi-algebraic systems as our main applications. We exhibit new results in the theory of border polynomials of parametric semi-algebraic systems: in particular a geometric characterization of its “true boundary” (Definition 1). In order to optimize the corresponding decomposition algorithms, we also propose a technique, that we call relaxation, which can simplify the decomposition process and reduce the number of components in the output. This paper extends our earlier works (Chen et al., 2010, 2011). [Copyright &y& Elsevier]

Abstract: In this paper we present a new algorithm for extracting sparse factors from multivariate integral polynomials. The method hinges on a new type of substitution, which reduces multivariate integral polynomials to bivariate polynomials over finite fields and keeps the sparsity of the polynomial. We retrieve the multivariate sparse factors, term by term, using discrete logarithms. We show that our method is really effective when used for factoring multivariate polynomials that have only sparse factors and when used to extract sparse factors of multivariate polynomials that may also have dense factors. [Copyright &y& Elsevier]

Abstract: The tensor decomposition addressed in this paper may be seen as a generalization of Singular Value Decomposition of matrices. We consider general multilinear and multihomogeneous tensors. We show how to reduce the problem to a truncated moment matrix problem and give a new criterion for flat extension of Quasi-Hankel matrices. We connect this criterion to the commutation characterization of border bases. A new algorithm is described. It applies for general multihomogeneous tensors, extending the approach on binary forms by J.J. Sylvester. An example illustrates the algebraic operations involved in this approach and how the decomposition can be recovered from eigenvector computation. [Copyright &y& Elsevier]

Abstract: This paper focuses on the equidimensional decomposition of affine varieties defined by sparse polynomial systems. For generic systems with fixed supports, we give combinatorial conditions for the existence of positive dimensional components which characterize the equidimensional decomposition of the associated affine variety. This result is applied to design an equidimensional decomposition algorithm for generic sparse systems. For arbitrary sparse systems of n polynomials in n variables with fixed supports, we obtain an upper bound for the degree of the affine variety defined and we present an algorithm which computes finite sets of points representing its equidimensional components. [Copyright &y& Elsevier]

Abstract: In this paper, we describe new methods to compute the radical (resp. real radical) of an ideal, assuming its complex (resp. real) variety is finite. The aim is to combine approaches for solving a system of polynomial equations with dual methods which involve moment matrices and semi-definite programming. While the border basis algorithms of Mourrain and Trébuchet (2005) are efficient and numerically stable for computing complex roots, algorithms based on moment matrices (Lasserre et al., 2008) allow the incorporation of additional polynomials, e.g., to restrict the computation to real roots or to eliminate multiple solutions. The proposed algorithm can be used to compute a border basis of the input ideal and, as opposed to other approaches, it can also compute the quotient structure of the (real) radical ideal directly, i.e., without prior algebraic techniques such as Gröbner bases. It thus combines the strength of existing algorithms and provides a unified treatment for the computation of border bases for the ideal, the radical ideal and the real radical ideal. [Copyright &y& Elsevier]

Abstract: Ritt–Wuʼs algorithm of characteristic sets is the most representative for triangularizing sets of multivariate polynomials. Pseudo-division is the main operation used in this algorithm. In this paper we present a new algorithmic scheme for computing generalized characteristic sets by introducing other admissible reductions than pseudo-division. A concrete subalgorithm is designed to triangularize polynomial sets using selected admissible reductions and several effective elimination strategies and to replace the algorithm of basic sets (used in Ritt–Wuʼs algorithm). The proposed algorithm has been implemented and experimental results show that it performs better than Ritt–Wuʼs algorithm in terms of computing time and simplicity of output for a number of non-trivial test examples. [Copyright &y& Elsevier]

Abstract: In this paper we present the algorithms used by the second author in Hernandes (2011) for the implementation in MAPLE of the results of Hefez and Hernandes (2011) that allow to perform the analytic classification of irreducible germs of singular complex plane curves. [Copyright &y& Elsevier]

Abstract: In this paper, we define simultaneously row and column reduced forms of higher-order linear differential systems with power series coefficients and give two algorithms, along with their complexities, for their computation. We show how the simultaneously row and column reduced form can be used to transform a given higher-order input system into a first-order system. Finally, we show that the algorithm can be used to compute Two-Sided Block Popov forms as given in Barkatou et al. (2010). These results extend the previous work in Barkatou et al. (2010), on second-order systems, and Harris et al. (1968), on first-order systems, to systems of arbitrary order. [Copyright &y& Elsevier]