FCRC logo

List of accepted papers


Papers are ordered according to paper IDs used during the review process. Abstracts can be expanded.

  1. [+] Daniel Cabarcas and Jintai Ding. Linear Algebra to Compute Syzygies and Gröbner Bases.
    2. Abstract: In this paper, we introduce a new method to avoid zero reductions in Groebner basis computation. We call this method LASyz, which stands for Lineal Algebra to compute Syzygies. LASyz uses exhaustively the information of both principal syzygies and non-trivial syzygies to avoid zero reductions. All computation is done using linear algebra techniques. LASyz is easy to understand and implement. The method does not require an incremental computation and it imposes no restrictions on the reductions allowed. We provide a complete theoretical foundation for the LASyz method and we describe an algorithm for computing Groebner Bases for zero dimensional ideals based on this foundation. A qualitative comparison with similar algorithms is provided and the performance of the algorithm is illustrated with experimental data.
  2. [+] Hongbo Li, Ruiyong Sun, Shoubin Yao and Ge Li. Approximate Rational Solutions for Rational ODEs Defined on Discrete Differentiable Curves.

    3. 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-complete
  3. [+] Prabhanjan Ananth and Ambedkar Dukkipati. Border basis detection is NP-complete.
  4. [+] Jonathan Borwein and Armin Straub. Special values of generalized log-sine integrals.
    5. Abstract: We study generalized log-sine integrals at special values. At π and multiples thereof explicit evaluations are obtained in terms of multiple polylogarithms at  ± 1. For general arguments we present algorithmic evaluations involving harmonic polylogarithms at related arguments. In particular, we consider log-sine integrals at π / 3 which evaluate in terms of polylogarithms at the sixth root of unity. An implementation of our results for the computer algebra systems Mathematica and SAGE is provided.
  5. [+] Ernst W. Mayr and Stephan Ritscher. Space-efficient Gröbner Basis Computation without Degree Bounds.

    6. Abstract: 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.
  6. [+] Dustin Moody. Division Polynomials for Jacobi Quartic Curves.
    7. Abstract: In this paper we find division polynomials for Jacobi quartics. These curves are an alternate model for elliptic curves to the more common Weierstrass equation. Division polynomials for Weierstrass curves are well known, and the division polynomials we find are analogues for Jacobi quartics. Using the division polynomials, we show recursive formulas for the n-th multiple of a point on the quartic curve. As an application, we prove a type of mean-value theorem for Jacobi quartics. These results can be extended to other models of elliptic curves, namely, Jacobi intersections and Huff curves.
  7. [+] Wei Li, Xiao-Shan Gao and Chun-Ming Yuan. Sparse Differential Resultant.
    8. Abstract: In this paper, the concept of sparse differential resultant for a differentially essential system of differential polynomials is introduced and its properties are proved. In particular, a degree bound for the sparse differential resultant is given. Based on the degree bound, an algorithm to compute the sparse differential resultant is proposed, which is single exponential in terms of the order, the number of variables, and the size of the differentially essential system.
  8. [+] Kosaku Nagasaka. Computing a Structured Gröbner Basis Approximately.
    9. Abstract: There are several preliminary definitions for a Gröbner basis with inexact input since computing such a basis is one of the challenging problems in symbolic-numeric computations for a couple of decades. A structured Gröbner basis is such a basis defined from the data mining point of view: how to extract a meaningful result from the given inexact input when the amount of noise is not small or we do not have enough information about the input. However, the known algorithm needs a suitable (unknown) information on terms required for the Buchberger algorithm. In this paper, we introduce an improved version of the algorithm that does not need any extra information.
  9. [+] Yue Li and Gabriel Dos Reis. An Automatic Parallelization Framework for Algebraic Computation Systems.
    10. Abstract: Concurrency brought by multicore machines has the potential of enabling efficient computations. However, the difficulty of parallel programming makes manual parallelization still a challenging task for non-experts. This paper proposes an automatic parallelization framework for an existing computer algebra system. The framework performs a semantics-based static analysis to extract reductions in library components. Reductions using associative binary operators are automatically transformed to their parallel versions. Our implementation is evaluated using algebraic library functions and a self-implemented application. Experimental results show that up to 5 times speed-up for the application is obtained. It is feasible to adapt the core of this framework to other algebraic computation systems and programming languages. The adaptation requires a type system which is able to provide semantics algebraic information from users.
  10. [+] Zhikun She, Bai Xue and Zhiming Zheng. Algebraic Analysis on Asymptotic Stability of Continuous Dynamical Systems.
    11. Abstract: In this paper we propose a mechanisable technique for asymptotic stability analysis of continuous dynamical systems. We start from linearizing a continuous dynamical system, solving the Lyapunov matrix equation and then check whether the solution is positive definite. For the cases that the Jacobian matrix is not a Hurwitz matrix, we first derive an algebraizable sufficient condition for the existence of a Lyapunov function in quadratic form without linearization, apply a real root classification based method step by step to formulate this derived condition as a semi-algebraic set such that the semi-algebraic set only involves the coefficients of the pre-assumed quadratic form, and then compute a sample point in the resulting semi-algebraic set for the coefficients resulting in a Lyapunov function. In this way, we avoid the use of generic quantifier elimination techniques for efficient computation. We prototypically implemented our algorithm based on DISCOVERER. The experimental results and comparisons demonstrate the feasibility and promise of our approach.
  11. [+] Shaoshi Chen, Ruyong Feng, Guofeng Fu and Ziming Li. On the Structure of Compatible Rational Functions.
    12. Abstract: A finite number of rational functions are compatible if they satisfy the compatibility conditions of a first-order linear functional system involving differential, shift and q-shift operators. We present a theorem that describes the structure of compatible rational functions. The theorem enables us to decompose a solution of such a system as a product of a rational function, several symbolic powers, a hyperexponential function, a hypergeometric term, and a q-hypergeometric term. We outline an algorithm for computing this product, and discuss how to determine the algebraic dependence of hyperexponential-hypergeometric elements.
  12. [+] Leilei Guo and Feng Liu. An Algorithm for Computing Set-Theoretic Generators of an Algebraic Variety.
    13. Abstract: Based on Eisenbud’s idea (see [Eisenbud, D., Evans, G., 1973. Every algebraic set in n-space is the intersection of n hypersurfaces. Invent. Math. 19, 107–112]), we present an algorithm for computing set-theoretic generators for any algebraic variety in the affine n-space, which consists of at most n polynomials. With minor modifications, this algorithm is also valid for projective algebraic variety in projective n-space.
  13. [+] Yue Ma and Lihong Zhi. The Minimum-Rank Gram Matrix Completion via Fixed Point Continuation Method.
    14. Abstract: The problem of computing a representation for a real polynomial as a sum of minimum number of squares of polynomials can be casted as finding a symmetric positive semidefinite real matrix (Gram matrix) of minimum rank subject to linear equality constraints. In this paper, we propose algorithms for solving the minimum-rank Gram matrix completion problem, and show the convergence of these algorithms. Our methods are based on the modified fixed point continuation (FPC) method. We also use the Barzilai-Borwein (BB) technique and a specific linear combination of two previous iterates to accelerate the convergence of modified FPC algorithms. We demonstrate the effectiveness of our algorithms for computing approximate and exact rational sum of squares (SOS) decompositions of polynomials with rational coefficients.
  14. [+] Yao Sun and Dingkang Wang. A Generalized Criterion for  Signature Related Gröbner Basis Algorithms.
    15. Abstract: A generalized criterion for signature related algorithms to compute Gröbner basis is proposed in this paper. Signature related algorithms are a popular kind of algorithms for computing Gröbner basis, including the famous F5 algorithm, the extended F5 algorithm and the GVW algorithm. The main purpose of current paper is to study in theory what kind of criteria is correct in signature related algorithms and provide a generalized method to develop new criteria. For this aim, a generalized criterion is proposed. The generalized criterion only relies on a general partial order defined on a set of polynomials. When specializing the partial order to appropriate specific orders, the generalized criterion can specialize to almost all existing criteria of signature related algorithms. For admissible partial orders, a complete proof for the correctness of the algorithm based on this generalized criterion is also presented. This proof has no demand on the computing order of critical pairs, and is also valid for non-homogeneous polynomial systems. More importantly, the partial orders implied by existing criteria are admissible. Besides, one can also check whether a new criterion is correct in signature related algorithms or even develop new criteria by using other admissible partial orders in the generalized criterion.
  15. [+] Deepak Kapur, Yao Sun and Dingkang Wang. Computing Comprehensive Gröbner Systems and Comprehensive Gröbner Bases Simultaneously.
    16. Abstract: In Kapur et al (ISSAC, 2010), a new method for computing a comprehensive Gröbner system of a parameterized polynomial system was proposed and its efficiency over other known methods was effectively demonstrated. Based on those insights, a new approach is proposed for computing a comprehensive Gröbner basis of a parameterized polynomial system. The key new idea is not to simplify a polynomial under various specialization of its parameters, but rather keep track in the polynomial, of the power products whose coefficients vanish; this is achieved by partitioning the polynomial into two parts— part and part for the specialization under consideration. During the computation of a comprehensive Gröbner system, for a particular branch corresponding to a specialization of parameter values, nonzero parts of the polynomials dictate the computation, i.e., computing S-polynomials as well as for simplifying a polynomial with respect to other polynomials; but the manipulations on the whole polynomials (including their zero parts) are also performed. Gröbner basis computations on such pairs of polynomials can also be viewed as Gröbner basis computations on a module. Once a comprehensive Gröbner system is generated, both nonzero and zero parts of the polynomials are collected from every branch and the result is a comprehensive Gröbner basis; every polynomial retrieved from a comprehensive Gröbner system is faithful, in the sense that it belongs to the ideal of the original parameterized polynomial system. This technique should be applicable to other algorithms for computing a comprehensive Gröbner system as well, thus producing both a comprehensive Gröbner system as well as a faithful comprehensive Gröbner basis of a parameterized polynomial system simultaneously. The approach is exhibited by adapting the recently proposed method for computing a comprehensive Gröbner system in (ISSAC, 2010) for computing a comprehensive Gröbner basis. The timings on a collection of examples demonstrate that this new algorithm for computing comprehensive Gröbner bases has better performance than other existing algorithms.
  16. [+] André Galligo and Daniel Bembe. Virtual Roots of a Real Polynomial and Fractional Derivatives.
    17. Abstract: After the works of Gonzales-Vega, Lombardi and Mahé, (1998) and Coste, Lajous, Lombardi, and Roy (2005), we consider the virtual roots of a univariate polynomial f with real coefficients and give quick proofs to establish their main properties. Using fractional derivatives, we associate to f a bivariate polynomial Pf(x, t) depending on the choice of an origin a, then two type of plan curves we call the FDcurve and the stem of f. We show, in the generic case, how to locate the virtual roots of f on the Budan table and on each of these curves. The paper is illustrated with examples and pictures computed with the computer algebra system Maple.
  17. [+] Alessandra Bernardi, Pierre Comon, Bernard Mourrain and Jérôme Brachat. Tensor decomposition and moment matrices.
    18. Abstract: In the paper, we address the important problem of tensor decompositions which can be seen as a generalisation of Singular Value Decomposition for 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 characterisation of border bases. A new algorithm is described which applies for general multihomogeneous tensors, extending the approach of J.J. Sylvester on binary forms. An example illustrates the algebraic operations involved in this approach and how the decomposition can be recovered from eigenvector computation.
  18. [+] Angelos Mantzaflaris and Bernard Mourrain. Deflation and Certified Isolation of Singular Zeros of Polynomial Systems.
    19. Abstract: We develop a new symbolic-numeric algorithm for the certification of singular isolated points, using their associated local ring structure and certified numerical computations. An improvement of an existing method to compute inverse systems is presented, which avoids redundant computations and reduces the size of the intermediate linear systems being solved. We derive a one-step deflation technique, from the description of the multiplicity structure in terms of differentials. The deflated system can be used in Newton-based iterative schemes with quadratic convergence. Starting from a polynomial system and a small-enough neighborhood, we obtain a criterion for the existence and uniqueness of a singular root of a given multiplicity structure, applying a well-chosen symbolic perturbation. Standard verification methods, based eg. on interval arithmetic and a fixed point theorem, are employed to certify that there exists a unique perturbed system with a singular root in the domain. Applications to topological degree computation and to the analysis of real branches of an implicit curve illustrate the method.
  19. [+] Chee Yap and Michael Sagraloff. A Simple But Exact and Efficient Algorithm for Complex Root Isolation.

    20. 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.
  20. [+] Jean-Charles Faugère and Chenqi Mou. Fast Algorithm for Change of Ordering of Zero-dimensional Gröbner Bases with Sparse Multiplication Matrices.

    21. 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.
  21. [+] Somit Gupta and Arne Storjohann. Computing Hermite forms of polynomial matrices.
    22. Abstract: This paper presents a new algorithm for computing the Hermite form of a polynomial matrix. Given a nonsingular n × n matrix A filled with degree d polynomials with coefficients from a field, the algorithm computes the Hermite form of A using an expected number of (n3d)1 + o(1) field operations. This is the first algorithm that is both linear in the degree d and cubic in the dimension n. The algorithm is randomized of the Las Vegas type.
  22. [+] Mark Giesbrecht and Daniel Roche. Diversification improves interpolation.
    23. Abstract: We consider the problem of interpolating an unknown multivariate polynomial with coefficients taken from a finite field or as numerical approximations of complex numbers. Building on the recent work of Garg and Schost, we improve on the best-known algorithm for interpolation over large finite fields by presenting a Las Vegas randomized algorithm that uses fewer black box evaluations. Using related techniques, we also address numerical interpolation of sparse complex polynomials, and provide the first provably stable algorithm (in the sense of relative error) for this problem, at the cost of modestly more interpolation points. A key new technique is a randomization which makes all coefficients of the unknown polynomial distinguishable, producing what we call a diverse polynomial. Another departure of our algorithms from most previous approaches is that they do not rely on root finding as a subroutine. We show how these improvements affect the practical performance with trial implementations.
  23. [+] Erich Kaltofen, Michael Nehring and B. David Saunders. Quadratic-time certificates in linear algebra.

    24. 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.
  24. [+] John Perry and Christian Eder. Signature-based algorithms to compute Gröbner bases.
    25. Abstract: This paper describes a Buchberger-style algorithm to compute a Groebner basis of a polynomial ideal, allowing for a selection criterion based on “signatures”. We explain how three recent algorithms can be viewed as different strategies for the new algorithm, and how other selection strategies can be formulated. We describe a fourth as an example. We analyze the strategies both theoretically and empirically, leading to some surprising results.
  25. [+] Curtis Bright and Arne Storjohann. Vector Rational Number Reconstruction.
    26. Abstract: The final step of some algebraic algorithms is to reconstruct the common denominator d of a collection of rational numbers (ni / d)1 ≤ i ≤ n from their images $(a_i)_{1\leq i\leq n} \bmod M$, subject to a condition such as 0 < d ≤ N and ∣ni∣ ≤ N for a given magnitude bound N. Applying elementwise rational number reconstruction requires that M ∈ Ω (N2). Using the gradual sub-lattice reduction algorithm of van Hoeij and Novocin (2010), we show how to perform the reconstruction efficiently even when the modulus satisfies a considerably smaller magnitude bound M ∈ Ω (N1 + 1 / c) for c a small constant, for example 2 ≤ c ≤ 5. Assuming c ∈ O(1) the cost of the approach is O(n(logM)3) bit operations using the original LLL lattice reduction algorithm, but is reduced to O(n(logM)2) bit operations by incorporating the L$^2$ variant of Nguyen and Stehle (2009). As an application, we give a robust method for reconstructing the rational solution vector of a linear system from its image, such as obtained by a solver using p-adic lifting.
  26. [+] Erich Kaltofen and Michael Nehring. Supersparse black box rational function interpolation.

    27. 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.
  27. [+] Soumojit Sarkar and Arne Storjohann. Normalization of row reduced polynomial matrices.
    28. Abstract: This paper gives gives a deterministic algorithm to transform an already row reduced matrix to canonical Popov form. Let $\K$ be a field. Given as input a row reduced matrix R over $\K[x]$, our algorithm computes the Popov form in about the same time as required to multiply together over $\K[x]$ two matrices of the same dimension and degree as R. We also show that the problem of transforming a row reduced matrix to Popov form is harder than polynomial matrix multiplication.
  28. [+] Tingting Fang and Mark van Hoeij. 2-descent for Second Order Linear Differential Equations.

    29. 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).

  29. [+] Michael Kerber and Michael Sagraloff. Efficient Real Root Approximation.
    30. Abstract: We consider the problem of approximating all real roots of a square-free polynomial f. Our algorithm assumes that corresponding isolating intervals are already provided and refines each of them to a certain width 2 - L, that is, each of the roots is approximated to L bits after the binary point. Our method is the first one that gives a certified answer to this problem in the context of bitstream polynomials, that is, it is assumed that the polynomial coefficients can be approximated to any specified error bound. For the refinement of an interval, we consider a variant of the quadratic interval refinement method which uses approximate evaluations only. We derive a general bit complexity in terms of characteristic values of the polynomial such as the size of the coefficients or the separation of the polynomial; in the special case of integer polynomials, our bound improves the previously best approach by a factor of degf.
  30. [+] Manuel Kauers and Carsten Schneider. A Refined Denominator Bounding Algorithm for Multivariate Linear Difference Equations.
    31. Abstract: We continue to investigate which polynomials can possibly occur as factors in the denominators of rational solutions of a given partial linear difference equation. In an earlier article we had introduced the distinction between periodic and aperiodic factors in the denominator, and we gave an algorithm for predicting the aperiodic ones. Now we extend this technique towards the periodic case and present a refined algorithm which also finds most of the periodic factors.
  31. [+] Alexey Pospelov. Fast Fourier Transforms over Poor Fields.

    32. 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 Ω (n1. 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.
  32. [+] B. David Saunders, David H. Wood and Bryan Youse. Symbolic-numeric exact rational linear system solution.

    33. 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.

  33. [+] Thomas Sturm and Ashish Tiwari. Verification and Synthesis Using Real Quantifier Elimination.
    34. Abstract: We present the application of real quantifier elimination methods to formal verification and synthesis of continuous and switched dynamical systems. Through a series of case studies, we show how first-order formulas over the reals arise when formally analyzing models of complex control systems. We present the models of the dynamical systems and the verification methodology in detail. The formulas described in the paper can serve as benchmarks for real quantifier elimination. Existing off-the-shelf quantifier elimination procedures are not successful in eliminating quantifiers from many of our benchmarks. We therefore automatically combine three established software components: virtual subtitution based quantifier elimination in Reduce/Redlog, cylindrical algebraic decomposition implemented in Qepcad, and the simplifier Slfq implemented on top of Qepcad. Corresponding computations can either be run in batch or interactively controlled from inside Reduce. We used this combination to successfully analyze models of various systems, including adaptive cruise control laws used in automobiles, the adaptive flight control system being proposed for next-generation flight control, and the classical inverted pendulum problem studied in control theory.
  34. [+] Adam Strzebonski and Elias Tsigaridas. Univariate real root isolation in an extension field.

    35. 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.
  35. [+] Jacques-Arthur Weil, Ainhoa Aparicio-Monforte, Moulay Barkatou and Sergi Simon. Formal first integrals along solutions of differential systems I.
    36. Abstract: We consider an analytic vector field ẋ = X(x) and study whether it may possess analytic first integrals via a variational approach. We assume that one solution Γ  is known and study the successive variational equations along Γ . Constructions of Morales-Ramis-Simo show that coefficients of the Taylor expansions of first integrals arise as rational solutions of the dual linearized variational equation. We show that they also satisfy linear “filter” conditions. Using this, we adapt the algorithms from to design algorithms optimized for this task and demonstrate their use. Part of this work stems from the first author’s PhD thesis .
  36. [+] Victor Y. Pan, Guoliang Qian and Ai-Long Zheng. GCDs and AGCDS of Univariate Polynomials by Matrix Methods.
    37. Abstract: We review the known algorithms for polynomial GCDs and present and analyze our novel techniques for the exact and numerical (approximate) computation of the GCDs by matrix methods.
  37. [+] Aurélien Greuet and Mohab Safey El Din. On the reachability the infimum of an unconstrained global optimization problem and real equation solving.

    38. 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 $Õ(n2(L + n2)(D(D - 1)n - 1)2)$. Experiments show its practical efficiency.
  38. [+] Andrew Novocin, Mark Van Hoeij and Jürgen Klüners. Generating Subfields.
    39. Abstract: Given a field extension K/k of degree n we are interested in finding the subfields of K containing k. There can be more than polynomially many subfields. We introduce the notion of generating subfields, a set of up to n subfields whose intersections give the rest. We provide an efficient algorithm which uses linear algebra in k or lattice reduction along with factorization in any extension of K. Our implementation shows that previously difficult cases can now be handled.
  39. [+] Andrew Novocin, William Hart and Mark Van Hoeij. Practical Polynomial Factorization in Polynomial Time.
    40. Abstract: State of the art factoring in Q[x] is dominated in theory by a combinatorial reconstruction problem while, excluding some rare polynomials, performance tends to be dominated by Hensel lifting. We present an algorithm which gives a practical improvement (less Hensel lifting) for these more common polynomials. In addition, factoring has suffered from a 25 year complexity gap because the best implementations are much faster in practice than their complexity bounds. We illustrate that this complexity gap can be closed by providing an implementation which is comparable to the best current implementations and for which competitive complexity results can be proved.
  40. [+] Changbo Chen and Marc Moreno Maza. Algorithms for Computing Triangular Decompositions of Polynomial Systems.

    41. Abstract: Methods for computing triangular decompositions of polynomial systems can be classified into two groups. First, those computing a series of regular chains C1…, Ce such that for each irreducible component V of the variety of the input system, one of the Ci’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) C1…, Cf such that the variety of the input system is the union of the quasi-components of the Ci’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.
  41. [+] Changbo Chen, James H. Davenport, Marc Moreno Maza, Bican Xia and Rong Xiao. Computing with Semi-Algebraic Sets Represented by  Triangular Decomposition.

    42. 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.
  42. [+] Li Guo, William Sit and Ronghua Zhang. On Rota’s Problem for Linear Operators in Associative Algebras.

    43. 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.
  43. [+] Benjamin A. Burton. Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations.

    44. 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.
  44. [+] Jeremy-Yrmeyahu Kaminski and Yann Sepulcre. Using Discriminant Curves to Recover a Surface of P^4 From Two Generic Linear Projections.

    45. 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.
Theme by grilldan.