Full papers

Details on the ISSAC 2015 Paper Review Process were published published here. Following this process the program committee has accepted the papers below. Click on the plus symbol to view a paper's abstract.
The full papers are in the ACM Digital Library, available to SIGSAM members at this link. Conference participants will receive USB proceedings at registration.

List of Accepted Papers

  1. [+] Jesus A. De Loera, Susan Margulies, Michael Pernpeintner, Eric Riedl, David Rolnick, Gwen Spencer, Despina Stasi and Jon Swenson. Graph-coloring ideals: Nullstellensatz certificates, Groebner bases for chordal graphs, and hardness of Groebner bases.
    Slides

    Abstract: We consider a well-known family of polynomial ideals encoding the problem of graph-k-colorability. Our paper describes how the inherent combinatorial structure of the ideals implies several interesting algebraic properties. Specifically, we provide lower bounds on the difficulty of computing Gröbner bases and Nullstellensatz certificates for the coloring ideals of general graphs. We revisit the fact that computing a Gröbner basis is NP-hard and prove a robust notion of hardness derived from the inapproximability of coloring problems. For chordal graphs, however, we explicitly describe a Gröbner basis for the coloring ideal and provide a polynomial-time algorithm to construct it.

  2. [+] Ferdinando Mora. De Nugis Groebnerialium 4:Zacharias, Spears, Möller
    Slides

    Abstract: It is well-known that each effective associative ring with identity is endowed with a Buchberger Theory, id est a notion of Gröbner bases and related algorithms. This note is a sort of Do-It-Yourself manual for setting a Gröbner bases approach to such a ring.
    The extension of Buchberger Theory and Algorithm from the classical case of polynomial rings over a field to the case of (non necessarily commutative) monoid rings over a (non necessarily free) monoid and a principal ideal ring was immediately performed by a series of milestone papers: Zacharias' approach to canonical forms, Spear's theorem which extends Buchberger Theory to each effectively given rings, Möller's reformulation of Buchberger Algorithm in terms of lifting.
    Since the universal property of the free monoid ring Q := Z\ Z over Z and the monoid Z of all words over the alphabet Z grants that each ring with identity A can be presented as a quotient A=Q I of a free monoid ring Q modulo a bilateral ideal I E Q, in order to impose a Buchberger Theory over any effective associative ring it is sufficient to reformulate it in filtration-valuation terms and apply the results quoted above; in particular Zacharias canonical forms allow to effectively present A and its elements, Spear's theorem describes how Q imposes its Z-filtration on A and a direct application of Möller's lifting theorem to such filtration allows to characterize the required S-polynomials.

  3. [+] Katsusuke Nabeshima and Shinichi Tajima. Computing Logarithmic Vector Fields associated with Parametric semi-quasihomogeneous Hypersurface isolated Singularities.

    Abstract: Logarithmic vector fields associated with parametric semi-quasihomogeneous hypersurface isolated singularities are considered in the context of symbolic computation. A new algorithm for computing the logarithmic vector fields is introduced. The keys of this approach are the concept of a polar variety and parametric local cohomology systems. The resulting algorithm also provides a decomposition of the parameter space depending on the structure of the logarithmic vector fields.

  4. [+] Alexander Hulpke. Constructing All Composition Series of a Finite Group.

    Abstract: This paper describes an effective method for enumerating all composition series of a finite group, possibly up to action of a group of automorphisms. By building the series in an ascending way it only requires a very easy case of complement computation and can avoid the need to fuse subspace chains in vector spaces.
    As a by-product it also enumerates all subnormal subgroups.

  5. [+] Christoph Lüders. Implementation of the DKSS Algorithm for Multiplication of Large Numbers.
    Slides

    Abstract: The Schönhage-Strassen algorithm (SSA) is the de-facto standard for multiplication of large integers. For N-bit numbers it has a time bound of O(N log N log log N). De, Kurur, Saha and Saptharishi (DKSS) presented an asymptotically faster algorithm with a better time bound of N log N 2^O(log* N). For this paper, a simplified DKSS multiplication was implemented. Assuming a sensible upper limit on the input size, some required constants could be precomputed. This allowed to simplify the algorithm to save some complexity and run-time. Still, run-time is about 30 times larger than SSA, while memory requirements are about 2.3 times higher than SSA. A possible crossover point is estimated to be out of reach even if we utilized the whole universe for computer memory.

  6. [+] Volker Diekert, Alexei Miasnikov and Armin Weiss. Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem.

    Abstract: In various occasions the conjugacy problem in finitely generated amalgamated products and HNN extensions can be decided efficiently for elements which cannot be conjugated into the base groups. This observation asks for a bound on how many such elements there are. Such bounds can be derived using the theory of amenable graphs:
    In this work we examine Schreier graphs of amalgamated products and HNN extensions. For an amalgamated product G=H*AK with [H:A] >= [K:A] >= 2, the Schreier graph with respect to H or K turns out to be non-amenable if and only if [H:A]>= 3. Moreover, for an HNN extension of the form G = , we show that the Schreier graph of G with respect to the subgroup H is non-amenable if and only if A <> H <> phi(A).
    As application of these characterizations we show that under certain conditions the conjugacy problem in fundamental groups of finite graphs of groups with free abelian vertex groups can be solved in polynomial time on a strongly generic set. Furthermore, the conjugacy problem in groups with more than one end can be solved with a strongly generic algorithm which has essentially the same time complexity as the word problem. These are rather striking results as the word problem might be easy, but the conjugacy problem might be even undecidable. Finally, our results yield another proof that the set where the conjugacy problem of the Baumslag group G1,2 is decidable in polynomial time is also strongly generic.

  7. [+] Jonathan D. Hauestein, Bernard Mourrain and Agnes Szanto. Certifying isolated singular points and their multiplicity structure.
    Slides

    Abstract: This paper presents two new constructions related to singular solutions of polynomial systems. The first is a new deflation method for an isolated singular root. This construction uses a single linear differential form defined from the Jacobian matrix of the input, and defines the deflated system by applying this differential form to the original system. The advantages of this new deflation is that it does not introduce new variables and the increase in the number of equations is linear instead of the quadratic increase of previous methods. The second construction gives the coefficients of the so-called inverse system or dual basis, which defines the multiplicity structure at the singular root. We present a system of equations in the original variables plus a relatively small number of new variables. We show that the roots of this new system include the original singular root but now with multiplicity one, and the new variables uniquely determine the multiplicity structure. Both constructions are 'exact' in that they permit one to treat all conjugate roots simultaneously and can be used in certification procedures for singular roots and their multiplicity structure with respect to an exact rational polynomial system.

  8. [+] Ryoya Fukasaku, Hidenao Iwane and Yosuke Sato. Real Quantifier Elimination by Computation of Comprehensive Gröbner Systems.
    Slides

    Abstract: A real quantifier elimination method based on the theory of real root counting and the computation of comprehensive Gröbner systems introduced by V. Weispfenning is studied in more detail. We introduce a simpler and more intuitive algorithm which is shown to be an improvement of the original algorithm. Our algorithm is implemented on the computer algebra system Maple using a recent algorithm to compute comprehensive Gröbner systems together with several simplification techniques. According to our computation experiments, our program is superior to other existing implementations for many examples which contain many equalities.

  9. [+] Bruno Grenet, Joris van der Hoeven and Grégoire Lecerf. Randomized Root Finding over Finite FFT-fields using Tangent Graeffe Transforms.

    Abstract: Consider a finite field Fq whose multiplicative group has smooth cardinality. We study the problem of computing all roots of a polynomial that splits over Fq, which was one of the bottlenecks for fast sparse interpolation in practice. We revisit and slightly improve existing algorithms and then present new randomized ones based on the Graeffe transform. We report on our implementation in the MATHEMAGIX computer algebra system, confirming that our ideas gain by a factor ten at least in practice, for sufficiently large inputs.

  10. [+] Shaoshi Chen, Hui Huang, Manuel Kauers and Ziming Li. A Modified Abramov-Petkovsek Reduction and Creative Telescoping for Hypergeometric Terms.

    Abstract: The Abramov-Petkovsek reduction computes an additive decomposition of a hypergeometric term,which extends the functionality of the Gosper algorithm for indefinite hypergeometric summation. We modify the Abramov-Petkovsek reduction so as to decompose a hypergeometric term as the sum of a summable term and a non-summable one. The outputs of the Abramov-Petkovsek reduction and our modified version share the same required properties. The modified reduction does not solve any auxiliary linear difference equation explicitly. It is also more efficient than the original reduction according to computational experiments. Based on this reduction, we design a new algorithm to compute minimal telescopers for bivariate hypergeometric terms. The new algorithm can avoid the costly computation of certificates.

  11. [+] Jose Rodriguez and Xiaoxian Tang. Data-Discriminants of Likelihood Equations.
    Slides

    Abstract: Maximum likelihood estimation (MLE) is a fundamental computational problem in statistics. The problem is to maximize the likelihood function with respect to given data on a statistical model. An algebraic approach to this problem is to solve a very structured parameterized polynomial system called likelihood equations. For general choices of data, the number of complex solutions to the likelihood equations is finite and called the ML-degree of the model. The only solutions to the likelihood equations that are statistically meaningful are the real/positive solutions. However, the number of real/positive solutions is not characterized by the ML-degree. We use discriminants to classify data according to the number of real/positive solutions of the likelihood equations. We call these discriminants data-discriminants (DD). We develop a probabilistic algorithm for computing DDs. Experimental results show that, for the benchmarks we have tried, the probabilistic algorithm is more efficient than the standard elimination algorithm. Based on the computational results, we discuss the real root classification problem for the 3 by 3 symmetric matrix~model.

  12. [+] Adrien Poteaux and Marc Rybowicz. Improving Complexity Bounds for the Computation of Puiseux Series over Finite Fields.

    Abstract: Let K be a field of characteristic p with q elements and FE in L[X,Y] be a polynomial with p > deg[Y(F)] and total degree d. In [40], we showed that rational Puiseux series of F above X=0 could be computed with an expected number of O~(d5+d3log q) arithmetic operations in L. In this paper, we reduce this bound to O~(d4+d2log q) using Hensel lifting and changes of variables in the Newton-Puiseux algorithm that give a better control of the number of steps. The only asymptotically fast algorithm required is polynomial multiplication over finite fields. This approach also allows to test the irreducibility of F in L[[X]][Y] with O(d3) operations in K. Finally, we describe a method based on structured bivariate multiplication [34] that may speed up computations for some input.

  13. [+] Erdal Imamoglu and Mark Van Hoeij. Computing Hypergeometric Solutions of Second Order Linear Differential Equations using Quotients of Formal Solutions.
    Slides

    Abstract: Let L be a second order differential equation with coefficients in C(x). The goal of this paper is to find solutions of L in the form exp(int r dx) [2]F[1](a1,a2,b1;f) where r; f E Q(x), and a1; a2; b1 E Q.

  14. [+] Andrew Arnold and Erich Kaltofen. Error-Correcting Sparse Interpolation in the Chebyshev Basis.
    Slides

    Abstract: We present an error-correcting interpolation algorithm for a univariate black-box polynomial that has a sparse representation using Chebyshev polynomials as a term basis. Our algorithm assumes that an upper bound on the number of erroneous evaluations is given as input, and is a generalization of the algorithm by Lakshman and Saunder [SIAM J. Comput., vol. 24 (1995)] for interpolating sparse Chebyshev polynomials and the techniques in error-correcting sparse interpolation in the usual basis of consecutive powers of the variable due to Comer, Kaltofen, and Pernet [Proc. ISSAC 2012 and 2014]. We prove the correctness of our list-decoder-based algorithm with a Descartes-rule-of-signs-like property for sparse polynomials in Chebyshev basis. We also give a new algorithm that reduces the sparse interpolation in Chebyshev basis to that in power basis, thus making the many techniques for the sparse interpolation in power basis, for instance, supersparse (lacunary) interpolation over large finite fields, available to interpolation in Chebyshev basis. Furthermore, we can customize the randomized early termination algorithms from Kaltofen and Lee [J. Symb. Comput., vol. 36 (2003)] to our new approach.

  15. [+] Andrew Arnold and Daniel Roche. Output-sensitive algorithms for sumset and sparse polynomial multiplication.
    Slides

    Abstract: We present randomized algorithms to compute the sumset (Minkowski sum) of two integer sets, and to multiply two univariate integer polynomials given by sparse representations. Our algorithm for sumset has cost softly linear in the combined size of the inputs and output. This is used as part of our sparse multiplication algorithm, whose cost is softly linear in the combined size of the inputs, output, and the sumset of the supports of the inputs. As a subroutine, we present a new method for computing the coefficients of a sparse polynomial, given a set containing its support. Our multiplication algorithm extends to multivariate Laurent polynomials over finite fields and rational numbers. Our techniques are based on sparse interpolation algorithms and results from analytic number theory.

  16. [+] Christopher Brown. Open Non-uniform Cylindrical Algebraic Decompositions.
    Slides

    Abstract: This paper introduces the notion of an Open Non-uniform Cylindrical Algebraic Decomposition (NuCAD), and presents an efficient model-based algorithm for constructing an Open NuCAD from an input formula. Using a limited experimental implementation of the algorithm, we demonstrate the effectiveness of the approach. NuCAD generalizes Cylindrical Algebraic Decomposition (CAD) as defined by Collins in his seminal work from the early 1970s, and extended in concepts like Hong's partial CAD. A NuCAD, like a CAD, is a decomposition of Rn into cylindrical cells. But unlike a CAD, the cells in a NuCAD need not be arranged cylindrically. It is in this sense that NuCADs are not uniformly cylindrical. However, NuCADs, like CADs, carry a tree-like structure that relates different cells. It is a very different tree but, as with the CAD tree structure, it allows some operations to be performed efficiently, for example locating the containing cell for an arbitrary input point.

  17. [+] Xavier Caruso, David Roe and Tristan Vaccon. p-adic stability in linear algebra.

    Abstract: Using the differential precision methods developed previously by the same authors, we study the p-adic stability of standard operations on matrices and vector spaces. We demonstrate that lattice-based methods surpass naive methods in many applications, such as matrix multiplication and sums and intersections of subspaces. We also analyze determinants, characteristic polynomials and LU factorization using these differential methods. We supplement our observations with numerical experiments.

  18. [+] Vikram Sharma and Prashant Batra. Near Optimal Subdivision Algorithms for Real Root Isolation.
    Slides

    Abstract: Isolating real roots of a square-free polynomial in a given interval is a fundamental problem. Subdivision based algorithms are a standard approach to solve this problem. E.g., Sturm's method,or various algorithms based on the Descartes's rule of signs. For isolating all the real roots of a degree n polynomial with root separation sigma, the subdivision tree size of most of these algorithms is bounded by O(log 1/sigma) (assume sigma < 1). Recently Sagraloff (2012) and Sagraloff-Mehlhorn (2013) have developed algorithms that combine subdivision with Newton iteration to reduce the size of the subdivision tree to O(n (log (nlog 1/sigma))). Their algorithms and analysis crucially depend on the terminating predicates. We describe a subroutine that improves the running time of any subdivision algorithm for real root isolation. The subdivision tree size of our algorithm using predicates based on the Descartes's rule of signs is bounded by O(nlog n). Our analysis differs in two key aspects from earlier approaches. First, we use the general technique of continuous amortization from Burr-Krahmer-Yap (2009), and hence the analysis extends to other predicates; and second, we use the geometry of clusters of roots instead of root bounds.

  19. [+] Van Chiên Bui, Gerard H.E. Duchamp and Vincel Hoang Ngoc Minh. Structure of polyzetas and explicit representation on transcendence bases of shuffle and stuffle algebras.

    Abstract: By an effective construction of pairs of bases in duality in shuffle and quasi-shuffle algebras, we identify the local coordinates of noncommutative generating series of polyzetas which are group-like. Algorithms lead to the ideal of homogeneous polynomial relations, in weight, among polyzetas and their explicit representation on irreducible elements.

  20. [+] Manuel Kauers and Christoph Koutschan. Integral D-finite Functions.
    Slides

    Abstract: We propose a differential analog of the notion of integral closure of algebraic function fields. We present an algorithm for computing the integral closure of the algebra defined by a linear differential operator. Our algorithm is a direct analog of van Hoeij's algorithm for computing integral bases of algebraic function fields.

  21. [+] Didier Clamond, Denys Dutykh and Andre Galligo. Computer algebra applied to a solitary waves study.
    Slides

    Abstract: We apply Computer algebra techniques, such as algebraic computations of resultants and discriminants, certified drawing (with a guaranteed topology) of plane curves, to a problem in Fluid dynamics: We investigate ``capillary-gravity'' solitary waves in shallow water, relying on the framework of the Serre-Green-Naghdi equations. So, we deal with 2 dimensional surface waves, propagating in a shallow water of constant depth. By a differential elimination process, the study reduces to describing the solutions of an ordinary non linear first order differential equation, depending on two parameters. The paper is illustrated with examples and pictures computed with the computer algebra system Maple.

  22. [+] Sébastien Maulat and Bruno Salvy. Formulas for Continued Fractions: An Automated Guess and Prove Approach.
    Slides Demo (Maple WS) Demo (PDF1) Demo (PDF2)

    Abstract: We describe a simple method that produces automatically closed forms for the coefficients of continued fractions expansions of a large number of special functions. The function is specified by a non-linear differential equation and initial conditions. This is used to generate the first few coefficients and from there a conjectured formula. This formula is then proved automatically thanks to a linear recurrence satisfied by some remainder terms. Extensive experiments show that this simple approach and its straightforward generalization to difference and q-difference equations capture a large part of the formulas in the literature on continued fractions.

  23. [+] Ioannis Z. Emiris, Christos Konaxis and Zafeirakis Zafeirakopoulos. Minkowski decomposition and geometric predicates in sparse implicitization.
    Slides

    Abstract: Based on the computation of a polytope Q, called the predicted polytope, containing the Newton polytope P of the implicit equation, implicitization of a parametric hypersurface is reduced to computing the nullspace of a numeric matrix. Polytope Q may contain P as a Minkowski summand, thus jeopardizing the efficiency of sparse implicitization. Our contribution is twofold. On one hand we tackle the aforementioned issue in the case of 2D curves and 3D surfaces by Minkowski decomposing Q, thus detecting the Minkowski summand relevant to implicitization: we design and implement in Sage a new, public domain, practical, potentially generalizable and worst-case optimal algorithm for Minkowski decomposition in 3D based on integer linear programming. On the other hand, we formulate basic geometric predicates, namely membership and sidedness for given query points, as rank computations on the interpolation matrix, thus avoiding to expand the implicit polynomial. This approach is implemented in Maple.

  24. [+] Alin Bostan, Louis Dumont and Bruno Salvy. Algebraic Diagonals and Walks.
    Slides

    Abstract: The diagonal of a multivariate power series $F$ is the univariate power series DiagF generated by the diagonal terms of F. Diagonals form an important class of power series; they occur frequently in number theory, theoretical physics and enumerative combinatorics. We study algorithmic questions related to diagonals in the case where F is the Taylor expansion of a bivariate rational function. It is classical that in this case DiagF is an algebraic function. We propose an algorithm that computes an annihilating polynomial for DiagF. Generically, it is its minimal polynomial and is obtained in time quasi-linear in its size. We show that this minimal polynomial has an exponential size with respect to the degree of the input rational function. We then address the related problem of enumerating directed lattice walks. The insight given by our study leads to a new method for expanding the generating power series of bridges, excursions and meanders. We show that their first N terms can be computed in quasi-linear complexity in N, without first computing a very large polynomial equation.

  25. [+] Pierre-Vincent Koseleff, Fabrice Rouillier and Cuong Tran. On the sign of a trigonometric expression.

    Abstract: We propose a set of simple and fast algorithms for evaluating and using trigonometric expressions in the form F=Sigma[k^d]=0 fk E Zd< n, for a fixed nin>0:EZ > 0: computing the sign of such an expression, evaluating it numerically and computing its minimal polynomial in Q[x]. As critical byproducts, we propose simple and efficient algorithms for performing arithmetic operations (multiplication, division, gcd) on polynomials expressed in a Chebyshev basis (with the same bit-complexity as in the monomial basis) and for computing the minimal polynomial of 2 cos Pi over n in Õ(n02) bit operations with n0 <= n is the odd squarefree part of n. Within such a framework, we can decide if F=0 in Õ(d(tau+d)) bit operations, compute the sign of F in Õ(d2 tau) bit operations and compute the minimal polynomial of F in Õ(n3tau) bit operations, where tau denotes the maximum bitsize of the f k's.

  26. [+] Tristan Vaccon. Matrix-F5 algorithms and tropical Gröbner base computation.

    Abstract: Let K be a field equipped with a valuation. Tropical varieties over K can be defined with a theory of Gröbner bases taking into account the valuation of K. Because of the use of the valuation, this theory is promising for stable computations over polynomial rings over a p-adic fields.
    We design a strategy to compute such tropical Gröbner bases by adapting the Matrix-F5 algorithm. Two variants of the Matrix-F5 algorithm, depending on how the Macaulay matrices are built, are available to tropical computation with respective modifications. The former is more numerically stable while the latter is faster.
    Our study is performed both over any exact field with valuation and some inexact fields like Qp or Fq [[t]]. In the latter case, we track the loss in precision, and show that the numerical stability can compare very favorably to the case of classical Gröbner bases when the valuation is non-trivial. Numerical examples are provided.

  27. [+] Feng Guo, Mohab Safey El Din, Chu Wang and Lihong Zhi. Optimizing a parameteric linear function over a non-compact real algebraic variety.
    Slides

    Abstract: We consider the problem of optimizing a parametric linear function over a non-compact real trace of an algebraic set. Our goal is to compute a representing polynomial which defines a hypersurface containing the graph of the optimal value function. Rostalski and Sturmfels showed that when the algebraic set is irreducible and smooth with a compact real trace, then the least degree representing polynomial is given by the defining polynomial of the irreducible hypersurface dual to the projective closure of the algebraic set.
    First, we generalize this approach to non-compact situations. We prove that the graph of the opposite of the optimal value function is still contained in the affine cone over a dual variety similar to the one considered in compact case. In consequence, we present an algorithm for solving the considered parametric optimization problem for generic parameters' values. For some special parameters' values, the representing polynomials of the dual variety can be identically zero, which give no information on the optimal value. We design a dedicated algorithm that identifies those regions of the parameters' space and computes for each of these regions a new polynomial defining the optimal value over the considered region.

  28. [+] Didier Henrion, Simone Naldi and Mohab Safey El Din. Real root finding for rank defects in linear Hankel matrices. Slides

    Abstract: Let H0, ..., H n be m x m matrices with entries in Q and Hankel structure, i.e. constant skew diagonals. We consider the linear Hankel matrix H(x) = H0+x1H1+...+xnHn and the problem of computing sample points in each connected component of the real algebraic set defined by the rank constraint rank}(H(x))<= r, for a given integer r <= m-1. Computing sample points in real algebraic sets defined by rank defects in linear matrices is a general problem that finds applications in many areas such as control theory, computational geometry, optimization, etc. Moreover, Hankel matrices appear in many areas of engineering sciences. Also, since Hankel matrices are symmetric, any algorithmic development for this problem can be seen as a first step towards a dedicated exact algorithm for solving semi-definite programming problems, i.e. linear matrix inequalities. Under some genericity assumptions on the input (such as smoothness of an incidence variety), we design a probabilistic algorithm for tackling this problem. It is an adaptation of the so-called critical point method that takes advantage of the special structure of the problem. Its complexity reflects this: it is essentially quadratic in specific degree bounds on an incidence variety. We report on practical experiments and analyze how the algorithm takes advantage of this special structure. A first implementation outperforms existing implementations for computing sample points in general real algebraic sets: it tackles examples that are out of reach of the state-of-the-art.

  29. [+] Moulay Barkatou and Suzy Maddah. Removing Apparent Singularities of Systems of Linear Differential Equations with Rational Function Coefficients.
    Slides

    Abstract: In this paper we present a new algorithm which, given a system of first order linear differential equations with rational function coefficients, constructs an equivalent system with rational function coefficients, whose finite singularities are exactly the non-apparent singularities of the original system. This algorithm is implemented in the computer algebra system Maple and is illustrated by examples.

  30. [+] Moulay Barkatou, Thomas Cluzeau and Achref Jalouli. Formal Solutions of Linear Differential Systems with Essential Singularities in their Coefficients.
    Slides

    Abstract: The local analysis of formal meromorphic linear differential systems with coefficients in C((z)) has been widely studied in the literature and there exist various computer algebra algorithms for computing formal solutions of such systems. In the present paper we extend the algorithm presented in [3] to allow more general systems. More precisely, we give an algorithm for computing a formal fundamental matrix of solutions around z=0 of systems with coefficients in C((z))[[X]], where X is transcendental and hyperexponential over C((z)).

  31. [+] Ivan Bannwarth and Mohab Safey El Din. Probabilistic algorithm for computing the dimension of real algebraic sets.

    Abstract: Let f E Q[X1, ..., Xn] be a polynomial of degree D. We consider the problem of computing the real dimension of the real algebraic set defined by f=0. Such a problem can be reduced to quantifier elimination. Hence it can be tackled with Cylindrical Algebraic Decomposition within a complexity that is doubly exponential in the number of variables. More recently, denoting by d the dimension of the real algebraic set under study, deterministic algorithms running in time DO(d(n-d)) have been proposed. However, no implementation reflecting this complexity gain has been obtained and the constant in the exponent remains unspecified. We design a probabilistic algorithm which runs in time which is essentially cubic in Dd(n-d). Our algorithm takes advantage of genericity properties of polar varieties to avoid computationally difficult steps of quantifier elimination. We also report on a first implementation. It tackles examples that are out of reach of the state-of-the-art and its practical behavior reflects the complexity gain.

  32. [+] Jose Gomez-Torrecillas, F.J. Lobillo and Gabriel Navarro. Separable automorphisms on matrix algebras over finite field extensions. Applications to ideal codes.
    Slides

    Abstract: Let (F E= K) an extension of finite fields and (A = Mn K) be the ring of square matrices of order n over (K) viewed as an algebra over (F). Given an (F)--automorphism (sigma) on (A) the Ore extension (A[z;sigma]) may be used to built certain convolutional codes, namely, the ideal codes. We provide an algorithm to decide if the automorphism (sigma) on (A) is a separable returning the corresponding separability element (p). In this case (p) is also a separability element for the extension (F[z] E= A[z;sigma]), and as a consequence ideal codes are generated by idempotents in (A[z;sigma]), which can be computed applying previous algorithms of the authors.

  33. [+] Arne Storjohann and Shiyun Yang. A relaxed algorithm for online matrix inversion.

    Abstract: We consider a variation of the well known problem of computing the unique solution to a nonsingular system Ax=b of n linear equations over a field K. The variation assumes that A has generic rank profile and requires as output not only the single solution vector A^(-1)b E Kn x 1, but rather the solution to all leading principle subsystems. Most importantly, the rows of the augmented system [A||b] are given one at a time from first to last, and as soon as the next row is given the solution to the next leading principal subsystem should be produced. We call this problem ONLINESYSTEM. The obvious iterative algorithm for ONLINESYSTEM has a cost in terms of field operations that is cubic in the dimension of A. In this paper we introduce a relaxed representation for the inverse and show how to obtain an algorithm for ONLINESYSTEM that allows us to incorporate matrix multiplication. As an application we show how to introduce fast matrix multiplication into the inherently iterative algorithm for row rank profile computation presented previously by the authors.

  34. [+] Jérémy Berthomieu, Brice Boyer and Jean-Charles Faugére. Linear Algebra for Computing Gröbner Bases of Linear Recursive Multidimensional Sequences.

    Abstract: Sakata generalized the Berlekamp--Massey algorithm to n dimensions in~1988. The Berlekamp--Massey--Sakata (BMS) algorithm can be used for finding a Grbner basis of a 0-dimensional ideal of relations verified by a table. We investigate this problem using ö linear algebra techniques, with motivations such as accelerating change of basis algorithms (FGLM) or improving their complexity. We first define and characterize multidimensional linear recursive sequences for 0-dimensional ideals. Under genericity assumptions, we propose a randomized preprocessing of the table that corresponds to performing a linear change of coordinates on the polynomials associated with the linear recurrences. This technique then essentially reduces our problem to using the efficient 1-dimensional Berlekamp--Massey (BM) algorithm. However, the number of probes to the table in this scheme may be elevated. We thus consider the table in the black-box model: we assume probing the table is expensive and we minimize the number of probes to the table in our complexity model. We produce an FGLM-like algorithm for finding the relations in the table, which lets us use linear algebra techniques. Under some additional assumptions, we make this algorithm adaptive and reduce further the number of table probes. This number can be estimated by counting the number of distinct elements in a multi-Hankel matrix (a multivariate generalization of Hankel matrices); we can relate this quantity with the geometry of the final staircase. Hence, in favorable cases such as convex ones, the complexity is essentially linear in the size of the output. Finally, when using the LEX ordering, we can make use of fast structured linear algebra similarly to the Hankel interpretation of Berlekamp--Massey.

  35. [+] Alin Bostan, Xavier Caruso and Éric Schost. A fast algorithm for computing the p-curvature.
    Slides

    Abstract: We design an algorithm for computing the p-curvature of a differential system in positive characteristic p. For a system of dimension r with coefficients of degree at most d, its complexity is O~ (p d r^w) operations in the ground field (where w denotes the exponent of matrix multiplication), whereas the size of the output is about p d r^2. Our algorithm is then quasi-optimal assuming that matrix multiplication is (i.e. w = 2). The main theoretical input we are using is the existence of a well-suited ring of series with divided powers for which an analogue of the Cauchy--Lipschitz Theorem holds.

  36. [+] Hsing-Hau Chen and Ming-Deh Huang. On p-adic Expansions of Algebraic Integers.

    Abstract: It is well known that every rational integer has a finite or periodic p-adic expansion. In this paper a more general notion of p-adic expansion is introduced for algebraic integers, where given a number field K and a principal prime ideal p in K, a different choice of generator for p is allowed in each stage of the expansion. With the notion of p-adic expansion, we prove that there is always a finite or periodic p-adic expansion for every algebraic integer. Moreover, we prove a bound on the periodicity of the p-adic expansion that depends only on the number field K and the prime ideal p. The proof yields an algorithm for constructing such a p-adic expansion for elements in the ring O of algebraic integers of K, through finding an approximation to the closest vector on the lattice spanned by the unit group of O. As a special case we prove that, similar to rational integers, Gaussian integers are finite or periodic not only in p-adic expansion but also in Pi-adic expansion, where a fixed generator Pi for p is used in each stage of the expansion. Moreover, the time complexity of finding a Pi-adic expansion for a Gaussian integer is polynomial in the length of input, the period, and p, where p is the rational prime contained in p. We implement the algorithm for some quadratic number fields and provide examples which illustrate that the p-adic expansion of the elements in O is either finite or periodic.

  37. [+] Deepak Kapur and Yiming Yang. An Algorithm to Check Whether a Basis of a Parametric Polynomial System is a Comprehensive Gröbner Basis and the Associated Completion Algorithm.

    Abstract: Given a basis of a parametric polynomial ideal, an algorithm is proposed to test whether it is a comprehensive Gröbner basis or not. A basis of a parametric polynomial ideal is a comprehensive Gröbner basis if and only if for every specialization of parameters in a given field, the specialization of the basis is a Gröbner basis of the associated specialized polynomial ideal. In case a basis does not check to be a comprehensive Gröbner basis, a completion algorithm for generating a comprehensive Gröbner basis from it that is patterned after Buchberger's algorithm is proposed. Its termination is proved and its correctness is established. In contrast to other algorithms for computing a comprehensive Gröbner basis which first compute a comprehensive Gröbner system and then extract a comprehensive Gröbner basis from it, the proposed algorithm computes a comprehensive Gröbner basis directly. Further, the proposed completion algorithm always computes a minimal faithful comprehensive Gröbner basis in the sense that every polynomial in the result is from the ideal as well as essential with respect to the comprehensive Gröbner basis. A prototype implementation of the algorithm has been successfully tried on many examples from the literature. An interesting and somewhat surprising outcome of using the proposed algorithm is that there are example parametric ideals for which a minimal comprehensive Gröbner basis computed by it is different from minimal comprehensive Gröbner bases computed by other algorithms in the literature.

  38. [+] Thomas Sturm. Subtropical Real Root Finding.

    Abstract: We describe a new incomplete but terminating heuristic method for real root finding for large multivariate polynomials. We take an abstract view of the polynomial as the set of exponent vectors associated with sign information on the coefficients. Then we employ linear programming to heuristically find roots. There is a specialized variant for roots with exclusively positive coordinates, which is of considerable interest for applications in chemistry and systems biology. An implementation of our method combining the computer algebra system Reduce with the linear programming solver Gurobi has been successfully applied to input data originating from established mathematical models used in these areas. We have solved several hundred problems with up to more than 800,000 monomials in up to 10 variables with degrees up to 12. Our method has failed due to its incompleteness in only 10 percent of the cases.

  39. [+] Matthew England, Russell Bradford and James H. Davenport. Improving the use of equational constraints in cylindrical algebraic decomposition.
    Slides

    Abstract: When building a cylindrical algebraic decomposition (CAD) savings can be made in the presence of an equational constraint (EC): an equation logically implied by a formula.
    The present paper is concerned with how to use multiple ECs, propagating those in the input throughout the projection set. We improve on the approach of McCallum in ISSAC 2001 by using the reduced projection theory to make savings in the lifting phase (both to the polynomials we lift with and the cells lifted over). We demonstrate the benefits with worked examples and a complexity analysis.

  40. [+] B. David Saunders. Matrices with two nonzero entries per row.

    Abstract: Matrices with two nonzero entries per row (or per column) occur in many contexts. For example, edge-vertex incidence matrices of graphs have this form. Also, the boundary matrix for the highest dimensional simplices in a simplicial complex sometimes has this form as well. In particular, the homology of a triangulation of a 2 dimensional non-self-intersecting surface is obtained from the Smith forms of 2 two-per-row matrices (the edge-vertex and triangle-edge boundary matrices). For an n by n matrix having just two nonzero entries per row, we show that rank, determinant, LU decomposition, and linear system solution can all be done in O(n) arithmetic operations (algebraic complexity). In the LU decomposition, U is bidiagonal and L, generally dense, is represented as a blackbox occupying O(n) space and such that matrix vector product with L and with its inverse can both be performed in O(n) arithmetic operations.
    If the nonzero entries are restricted to one and minus one then rank, LU decomposition, and Smith normal form can be computed in essentially O(n) bit operations (ignoring log factors). In this limited situation, Smith form is meaningfully defined over any ring. Determinant and linear system solution can each be performed with O(n) additions and negations in the entry ring.
    For integer two-per-row matrices with the nonzeros not limited to one and minus one, the methods here can be combined with standard techniques for algorithms of bit complexity greater than O(n) but less than the complexity for general matrices.

  41. [+] Christoph Fürst and Guenter Landsmann. Computation of Dimension in Filtered Free Modules by Gröbner Reduction.

    Abstract: We present an axiomatic approach to Gröbner basis techniques in free multi-filtered modules over a not necessarily commutative multi-filtered ring. It is shown that classical Gröbner basis concepts can be viewed as models of our axioms. Within this theory it is possible to prove a general theorem about the dimension of filter spaces in multi-filtered modules. We use these ideas for computing the Hilbert function of finitely generated multi-filtered modules over difference-differential rings. Thus the presented method allows to compute a multivariate generalization of the univariate and the bivariate dimension polynomial considered in the papers of Winkler and Zhou.

  42. [+] Markus Rosenkranz and Nitin Serwa. Green's Functions for Stieltjes Boundary Problems.
    Slides

    Abstract: In in the classical case of well-posed two-point boundary value problems, it is known how to transform the Green's operator into the so-called Green's function, the representation usually preferred by physicists and engineers. In this paper we extend this transformation to the whole class of Stieltjes boundary problems. It turns out that the extension (1) leads to more case distinction, (2) implies ill-posed problems and hence distributional terms, (3) has apparently no effect on the structure of the Green's function.

  43. [+] Jean-Guillaume Dumas, Clément Pernet and Ziad Sultan. Computing the Rank Profile Matrix.

    Abstract: The row (resp. column) rank profile of a matrix describes the stair case shape of its row (resp. column) echelon form. In an ISSAC'13 paper, we proposed a recursive Gaussian elimination that can compute simultaneously the row and column rank profiles of a matrix, as well as those of all of its leading sub-matrices, in the same time as state of the art Gaussian elimination algorithms. Here we first study the conditions making a Gaussian elimination algorithm reveal this information. We propose the definition of a new matrix invariant, the rank profile matrix, summarizing all information on the row and column rank profiles of all the leading sub-matrices. We also explore the conditions for a Gaussian elimination algorithm to compute all or part of this invariant, through the corresponding PLUQ decomposition. As a consequence, we show that the classical iterative CUP decomposition algorithm can actually be adapted to compute the rank profile matrix. Used, in a Crout variant, as a base-case to our ISSAC'13 implementation, it delivers a significant improvement in efficiency. Second, the row (resp. column) echelon form of a matrix are usually computed via different dedicated triangular decompositions. We show here that, from some PLUQ decompositions, it is possible to recover the row and column echelon forms of a matrix and of any of its leading sub-matrices thanks to an elementary post-processing algorithm.