List of accepted papers
Papers are ordered according to paper IDs used during the review process. Abstracts can be expanded.
- [+] Daniel Cabarcas and Jintai Ding. Linear Algebra to Compute Syzygies and Gröbner Bases.
- [+] Hongbo Li, Ruiyong Sun, Shoubin Yao and Ge Li. Approximate Rational Solutions for Rational ODEs Defined on Discrete Differentiable Curves.
- [+] Prabhanjan Ananth and Ambedkar Dukkipati. Border basis detection is NP-complete.
- [+] Jonathan Borwein and Armin Straub. Special values of generalized log-sine integrals.
- [+] Ernst W. Mayr and Stephan Ritscher. Space-efficient Gröbner Basis Computation without Degree Bounds.
- [+] Dustin Moody. Division Polynomials for Jacobi Quartic Curves.
- [+] Wei Li, Xiao-Shan Gao and Chun-Ming Yuan. Sparse Differential Resultant.
- [+] Kosaku Nagasaka. Computing a Structured Gröbner Basis Approximately.
- [+] Yue Li and Gabriel Dos Reis. An Automatic Parallelization Framework for Algebraic Computation Systems.
- [+] Zhikun She, Bai Xue and Zhiming Zheng. Algebraic Analysis on Asymptotic Stability of Continuous Dynamical Systems.
- [+] Shaoshi Chen, Ruyong Feng, Guofeng Fu and Ziming Li. On the Structure of Compatible Rational Functions.
- [+] Leilei Guo and Feng Liu. An Algorithm for Computing Set-Theoretic Generators of an Algebraic Variety.
- [+] Yue Ma and Lihong Zhi. The Minimum-Rank Gram Matrix Completion via Fixed Point Continuation Method.
- [+] Yao Sun and Dingkang Wang. A Generalized Criterion for Signature Related Gröbner Basis Algorithms.
- [+] Deepak Kapur, Yao Sun and Dingkang Wang. Computing Comprehensive Gröbner Systems and Comprehensive Gröbner Bases Simultaneously.
- [+] André Galligo and Daniel Bembe. Virtual Roots of a Real Polynomial and Fractional Derivatives.
- [+] Alessandra Bernardi, Pierre Comon, Bernard Mourrain and Jérôme Brachat. Tensor decomposition and moment matrices.
- [+] Angelos Mantzaflaris and Bernard Mourrain. Deflation and Certified Isolation of Singular Zeros of Polynomial Systems.
- [+] Chee Yap and Michael Sagraloff. A Simple But Exact and Efficient Algorithm for Complex Root Isolation.
- [+] Jean-Charles Faugère and Chenqi Mou. Fast Algorithm for Change of Ordering of Zero-dimensional Gröbner Bases with Sparse Multiplication Matrices.
- [+] Somit Gupta and Arne Storjohann. Computing Hermite forms of polynomial matrices.
- [+] Mark Giesbrecht and Daniel Roche. Diversification improves interpolation.
- [+] Erich Kaltofen, Michael Nehring and B. David Saunders. Quadratic-time certificates in linear algebra.
- [+] John Perry and Christian Eder. Signature-based algorithms to compute Gröbner bases.
- [+] Curtis Bright and Arne Storjohann. Vector Rational Number Reconstruction.
- [+] Erich Kaltofen and Michael Nehring. Supersparse black box rational function interpolation.
- [+] Soumojit Sarkar and Arne Storjohann. Normalization of row reduced polynomial matrices.
- [+] Tingting Fang and Mark van Hoeij. 2-descent for Second Order Linear Differential Equations.
- [+] Michael Kerber and Michael Sagraloff. Efficient Real Root Approximation.
- [+] Manuel Kauers and Carsten Schneider. A Refined Denominator Bounding Algorithm for Multivariate Linear Difference Equations.
- [+] Alexey Pospelov. Fast Fourier Transforms over Poor Fields.
- [+] B. David Saunders, David H. Wood and Bryan Youse. Symbolic-numeric exact rational linear system solution.
- [+] Thomas Sturm and Ashish Tiwari. Verification and Synthesis Using Real Quantifier Elimination.
- [+] Adam Strzebonski and Elias Tsigaridas. Univariate real root isolation in an extension field.
- [+] Jacques-Arthur Weil, Ainhoa Aparicio-Monforte, Moulay Barkatou and Sergi Simon. Formal first integrals along solutions of differential systems I.
- [+] Victor Y. Pan, Guoliang Qian and Ai-Long Zheng. GCDs and AGCDS of Univariate Polynomials by Matrix Methods.
- [+] Aurélien Greuet and Mohab Safey El Din. On the reachability the infimum of an unconstrained global optimization problem and real equation solving.
- [+] Andrew Novocin, Mark Van Hoeij and Jürgen Klüners. Generating Subfields.
- [+] Andrew Novocin, William Hart and Mark Van Hoeij. Practical Polynomial Factorization in Polynomial Time.
- [+] Changbo Chen and Marc Moreno Maza. Algorithms for Computing Triangular Decompositions of Polynomial Systems.
- [+] Changbo Chen, James H. Davenport, Marc Moreno Maza, Bican Xia and Rong Xiao. Computing with Semi-Algebraic Sets Represented by Triangular Decomposition.
- [+] Li Guo, William Sit and Ronghua Zhang. On Rota’s Problem for Linear Operators in Associative Algebras.
- [+] Benjamin A. Burton. Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations.
- [+] Jeremy-Yrmeyahu Kaminski and Yann Sepulcre. Using Discriminant Curves to Recover a Surface of P^4 From Two Generic Linear Projections.
Abstract: In this paper, a new concept is proposed for discrete differential geometry: discrete n-differentiable curve, which is a tangent n-jet on a sequence of space points. A complete method is proposed to solve ODEs of the form n^{(m)} = F(r, rʹ, . . . , r^{(n)}, w, wʹ, . . . , w^{(m - 1)}, u) / G(r, rʹ, . . . , r^{(n)}, w, wʹ, . . . s, w^{(m - 1)}, u), where F, G are respectively vector-valued and scalar-valued polynomials, where r is a discrete curve obtained by sampling along an unknown smooth curve parametrized by u, and where w is the vector field to be computed along the curve. Our Maple program outputs an approximate rational solution with the highest order of approximation for given data and neighborhood size.
The method is used to compute rotation minimizing frames of space curves in CAGD. For one-step backward-forward chasing, a 6th-order approximate rational solution is found, and theorems in this paper guarantee that 6 is the highest order of approximation by rational functions. The theoretical order of approximation is also supported by numerical experiments. Prabhanjan Ananth and Ambedkar Dukkipati. Border basis detection is NP-completeAbstract: The computation of a Gröbner basis of a polynomial ideal is known to be exponential space complete. We revisit the algorithm by Kühnle and Mayr using recent improvements of various degree bounds. The result is an algorithm which is exponential in the ideal dimension (rather than the number of indeterminates).
Furthermore, we provide an incremental version of the algorithm which is independent of the knowledge of degree bounds. Employing a space-efficient implementation of Buchberger’s S-criterion, the algorithm can be implemented such that the space requirement depends on the representation and Gröbner basis degrees of the problem instance (instead of the worst case) and thus is much lower in average.DISCOVERER
. The experimental results and comparisons demonstrate the feasibility and promise of our approach.
Abstract: We present a new exact subdivision algorithm CEVAL for isolating the complex roots of a square-free polynomial in any given box. It is a generalization of a previous real root isolation algorithm called EVAL. Under suitable conditions, our approach is applicable for general analytic functions. CEVAL is based on the simple Bolzano Principle and is easy to implement exactly. Preliminary experiments have shown its competitiveness.
We further show that, for the benchmark problem of isolating all roots of a square-free polynomial with integer coefficients, the asymptotic complexity of both algorithms EVAL and CEVAL matches (up a logarithmic term) that of more sophisticated real root isolation methods which are based on Descartes’ Rule of Signs, Continued Fraction or Sturm sequences. In particular, we show that the tree size of EVAL matches that of other algorithms.
Our analysis is based on a novel technique called δ-clusters from which we expect to see further applications.Abstract: Let I be a 0-dimensional ideal of degree D in K[x1,…,xn], where K is a field. It is well-known that obtaining efficient algorithms for change of ordering of Gröbner bases of I is crucial in polynomial system solving. Through the algorithm FGLM, this task is classically tackled by linear algebra operations in K[x1,…,xn]/I. With recent progress on Gröbner bases computations, this step turns out to be the bottleneck of the whole solving process.
Our contribution is an algorithm that takes advantage of the sparsity structure of multiplication matrices appearing during the change of ordering. This sparsity structure arises even when the input polynomial system defining I is dense. As a by-product, we obtain an implementation which is able to manipulate 0-dimensional ideals over a prime field of degree greater than 30000. It outperforms the Magma/Singular/FGb implementations of FGLM.
First, we investigate the particular but important shape position case. The obtained algorithm performs the change of ordering within a complexity O(D(N1+n log(D))), where N1 is the number of nonzero entries of a multiplication matrix. This almost matches the complexity of computing the minimal polynomial of one multiplication matrix. Then, we address the general case and give corresponding complexity results. Our algorithm is dynamic in the sense that it selects automatically which strategy to use depending on the input. Its key ingredients are the Wiedemann algorithm to handle 1-dimensional linear recurrence (for the shape position case), and the Sakata algorithm from Coding Theory (which is a generalization of Berlekamp–Massey algorithm) to handle multi-dimensional linearly recurring sequences in the general case.Abstract: We present certificates for the positive semidefiniteness of an n by n matrix A, whose entries are integers of binary length log ||A||, that can be verified in O(n^(2+epsilon) (log ||A||)^(1+epsilon)) binary operations for any epsilon > 0. The question arises in Hilbert/Artin-based rational sum-of-squares certificates (proofs) for polynomial inequalities with rational coefficients. We allow certificates that are validated by Monte Carlo randomized algorithms, as in Rusins Freivalds’s famous 1979 quadratic time certification for the matrix product. Our certificates occupy O(n^(3+epsilon) (log ||A|| )^(1+epsilon)) bits, from which the verification algorithm randomly samples a quadratic amount.
In addition, we give certificates of the same space and randomized validation time complexity for the Frobenius form, which includes the characteristic and minimal polynomial. For determinant and rank we have certificates of essentially-quadratic binary space and time complexity via Storjohann’s algorithms.Abstract: We present a method for interpolating a supersparse blackbox rational function with rational coefficients, for example, a ratio of binomials or trinomials with very high degree. We input a blackbox rational function, as well as an upper bound on the number of non-zero terms and an upper bound on the degree. The result is found by interpolating the rational function modulo a small prime p, and then applying an effective version of Dirichlet’s Theorem on primes in an arithmetic progression progressively lift the result to larger primes. Eventually we reach a prime number that is larger than the inputted degree bound and we can recover the original function exactly. In a variant, the initial prime p is large, but the exponents of the terms are known modulo larger and larger factors of p–1.
The algorithm, as presented, is conjectured to be polylogarithmic in the degree, but exponential in the number of terms. Therefore, it is very effective for rational functions with a small number of non-zero terms, such as the ratio of binomials, but it quickly becomes ineffective for a high number of terms.
The algorithm is oblivious to whether the numerator and denominator have a common factor. The algorithm will recover the sparse form of the rational function, rather than the reduced form, which could be dense. We have experimentally tested the algorithm in the case of under 10 terms in numerator and denominator combined and observed its conjectured high efficiency.Abstract: Let L be a second order linear ordinary differential equation with coefficients in C(x). The goal in this paper is to reduce L to an equation that is easier to solve. The starting point is an irreducible L, of order two, and the goal is to decide if L is projectively equivalent to another equation L~ that is defined over a subfield C(f) of C(x).
This paper treats the case of 2-descent, which means reduction to a subfield with index [C(x):C(f)]=2. Although the mathematics has already been treated in other papers, a complete implementation could not be given because it involved a step for which we do not have a complete implementation. The contribution of this paper is to give an alternative approach that is fully implementable. Examples illustrate that this algorithm is very useful for finding closed form solutions (2-descent, if it exists, reduces the number of true singularities from n to at most n/2 + 2).
Abstract: We present a new algebraic algorithm for computing the Discrete Fourier Transforms over arbitrary fields. It computes DFTs of infinitely many orders n in O(nlogn) algebraic operations, while the complexity of the known FFT algorithms is Ω (n^{1. 5}) for such n. Our algorithm is a novel combination of the classical FFT algorithms, and is never slower than any of the latter.
As an application we come up with an efficient way of computing DFTs of high orders in finite field extensions which can further boost fast polynomial multiplication. We relate the complexities of the DFTs of special orders with the complexity of polynomial multiplication.Abstract: An iterative refinement approach is taken to rational linear system solution. Such methods produce, for each entry of the solution vector, a dyadic rational approximation from which the correct rational entry can be reconstructed. A dyadic rational is a rational number with denominator a power of 2. Our method is numeric-symbolic in that it uses an approximate numeric solver at each iteration together with a symbolic (exact arithmetic) residual computation and symbolic rational reconstruction. There is some possibility of failure of convergence. The rational solution may be checked symbolically. Alternatively, the algorithm may be used without the rational reconstruction to obtain an extended precision floating point approximation of any specified accuracy. In this case we cannot guarantee the result, but we give evidence (not proof) that the probability of error is extremely small.
The chief contributions of our method are (1) consistent continuation, (2) improved rational reconstruction. and (3) performance. By consistent continuation is meant that the primary evidence of convergence at each iterative step is not the size of the residual but rather the consistency of the low order portion of the previous approximant with the high order bits of the current correction term. Our improved rational reconstruction uses a new rationale. For good enough dyadic approximants it is able to be output sensitive (i.e. have early termination) with provably correct result. We also have a heuristic for even earlier, but speculative, termination. Regarding performance, experiments show that our implementation competes favorably with Dixon’s method (pure symbolic with padic iteration) as implemented in LinBox, and with previous numeric-symbolic iterative implementations. In many cases we achieve equivalent or better time than similar methods or succeed when they fail to converge.
Abstract: We present algorithmic, complexity and implementation results for the problem of isolating the real roots of a univariate polynomial in B_{α} ∈ L[y], where $L=\QQ(\alpha)$ is a simple algebraic extension of the rational numbers.
We consider two approaches for tackling the problem. In the first approach using resultant computations we perform a reduction to a polynomial with integer coefficients. We compute separation bounds for the roots, and using them we deduce that we can isolate the real roots of B_{α} in $\sOB(N^{10})$, where N is an upper bound on all the quantities of the input (degree and bitsize) polynomials.
In the second approach we isolate the real roots working directly on the polynomial of the input. We compute separation bounds for real roots and we prove that they are optimal, under mild assumptions. For isolating the roots we consider a modified Sturm’s algorithm, and a modified version of Descartes’ algorithm introduced by Sagraloff. For the former we prove a complexity bound of $\sOB(N^8)$ and for the latter a bound of $\sOB(N^{7})$.
We implemented the algorithms in C as part of the core library of Mathematica and we illustrate their efficiency over various data sets.
Finally, we present complexity results for the general case of the first approach, in the case where the coefficients belong to multiple extensions.Abstract: Let $$f\in \Q[X_1,\ldots,X_n]$$ of degree D. Algorithms for solving the unconstrained global optimization problem $$f^\star=\inf_{\x\in \R^n} f(\x)$$ are of first importance since this problem appears frequently in numerous applications in engineering sciences. This can be tackled by either designing appropriate quantifier elimination algorithms or by certifying lower bounds on $f^\star$ by means of sums of squares decompositions but there is no efficient algorithm for deciding if $f^\star$ is a minimum.
This paper is dedicated to this important problem. We design an algorithm that decides if $f^\star$ is reached over $$\R^n$$ and computes a point $$\x^\star\in \R^n$$ such that $$f(\x^\star)=f^\star$$ if such a point exists. If $L$ is the length of a straight-line program evaluating $f$, a probabilistic version of the algorithm runs in time $Õ(n^{2}(L + n^{2})(D(D - 1)^{n - 1})^{2})$. Experiments show its practical efficiency.Abstract: Methods for computing triangular decompositions of polynomial systems can be classified into two groups. First, those computing a series of regular chains C_{1}…, C_{e} such that for each irreducible component V of the variety of the input system, one of the C_{i}’s encodes a generic zero of V. Secondly are those methods computing a series of characteristic sets (in the sense of Wu Wen Tsün) C_{1}…, C_{f} such that the variety of the input system is the union of the quasi-components of the C_{i}’s.
A large number of methods fall in the second family. Some methods belong to both families, this is the case for those proceeding in an incremental manner, that is, solving one equation after another. These latter methods rely on an operation for computing the intersection of an hypersurface and the quasi-component of a regular chain. This is an attractive operation since its input can be regarded as well-behaved geometrical objects. However, known algorithms (the one of Daniel Lazard in 1991 and the one of the second author in 2000) are quite involved and difficult to analyze.
We revisit this intersection operation. We exhibit a simpler algorithm, which also appears to be practically much more efficient. To this end, we have weakened the standard notion of a polynomial CDG modulo a regular chain, while preserving the same specifications for our intersection operation. Another central idea is to prevent from repeating intermediate expensive computations. This feature is achieved by the algebraic properties of our algorithm and not as a result of any caching techniques in the implementation.
In our experimental results, realized with the RegularChains library in Maple, our new intersection outperforms the one of the second author by several orders of magnitude on sufficiently difficult problems.Abstract: In a previous work, we introduced the notion of a triangular decomposition of a semi-algebraic system. We also proposed two algorithms for computing such decompositions, by adapting to the semi-algebraic case techniques that are standard in the algebraic one. Under genericity assumptions one of our algorithms runs in singly exponential in the number of variables.
Increasing the practical efficiency of these two algorithms and the utility of their output are the motivations of this new article. To this end, we propose theoretical results, new algorithms and an implementation report.
First, we establish properties of border polynomials and fingerprint polynomial sets under splitting. These results are used in our algorithms in order to recycle intermediate data when computations split in several branches.
Second, observing that triangular decomposition algorithms are essentially recursive, we propose a technique, that we call relaxation, for reducing the complexity of the arguments in those recursive calls. Experimental results confirm the effectiveness of this technique.
Third, we present practical procedures for basic set-theoretical operations on semi-algebraic sets represented by triangular decompositions, in particular for performing inclusion tests. This allows us to ensure that semi-algebraic sets can be represented by irredundant triangular decompositions.Abstract: A long standing problem of G. Rota for associative algebras is the classification of all linear operators that can be defined on them. In the 1970s, there were only a few known classes of such operators, for example, the derivative operator, the difference operator, the average operator and the Rota-Baxter operator. A few more similar operators have appeared after Rota posed his problem. However, little progress has been made to solve this problem in general. In part, this is because the precise meaning of the problem is not so well understood. In this paper, we propose a formulation of the problem using the context of operated algebras and viewing an associative algebra with a linear operator as one that satisfies a certain operated polynomial identity. This approach is analogous to the study of rings with polynomial identities. To narrow our focus more on the operators that Rota was interested in, we further consider two particular classes of operators, namely, those that generalize differential or Rota-Baxter operators. With the aid of computer algebra, we are able to come up to a list of these two classes of operators, and provide some evidence that these lists may be complete. Our search have revealed quite a few new operators of these types whose properties are expected to be similar to the differential operator and Rota-Baxter operator respectively.
In recent years, a more uniformed approach has emerged in related areas, such as difference algebra and differential algebra, and Rota-Baxter algebra and Nijenhuis algebra. The similarities in related theories can be more efficiently explored by advances on Rota’s problem.Abstract: Enumerating all 3-manifold triangulations of a given size is a difficult but increasingly important problem in computational topology. A key difficulty for enumeration algorithms is that most combinatorial triangulations must be discarded because they do not represent topological 3-manifolds. In this paper we show how to preempt bad triangulations by detecting genus in partially-constructed vertex links, allowing us to prune the enumeration tree substantially.
The key idea is to manipulate the boundary edges surrounding partial vertex links using expected logarithmic time operations. Practical testing shows the resulting enumeration algorithm to be significantly faster, with up to 249x speed-ups even for small problems where comparisons are feasible. We also discuss parallelisation, and describe new data sets that have been obtained using high-performance computing facilities.Abstract: We study how an irreducible smooth and closed algebraic surface X embedded in $$\C\P^4$$, can be recovered using its projections from two points onto embedded projective hyperplanes. The different embeddings are unknown. The only input is the defining equation of each projected surface. We show how both the embeddings and the surface in $$\C\P^4$$ can be recovered modulo some action of the group of projective transformations of $$\C\P^4$$.
We show how in a generic situation, a characteristic matrix of the pair of embeddings can be recovered. Then we use this matrix to recover the class of the couple of maps and as a consequence to recover the surface.
For a generic situation, two projections define a surface with two irreducible components. One component has degree d(d - 1) and the other has degree d, being the original surface.