Hasil untuk "cs.SC"

Hui Huang

Leveraging a general framework adapted from symbolic integration, a unified reduction-based algorithm for computing telescopers of minimal order for hypergeometric and q-hypergeometric terms has been recently developed. In this paper, we conduct a deeper exploration and put forth a new argument for the termination of the algorithm. This not only provides an independent proof of existence of telescopers, but also allows us to derive unified upper and lower bounds on the order of telescopers for hypergeometric terms and their q-analogues. Compared with known bounds in the literature, our bounds, in the hypergeometric case, are exactly the same as the tight ones obtained in 2016; while in the q-hypergeometric case, no lower bounds were known before, and our upper bound is sometimes better and never worse than the known one.

Shaoshi Chen, Manuel Kauers, Christoph Koutschan et al.

Elaborating on an approach recently proposed by Mark van Hoeij, we continue to investigate why creative telescoping occasionally fails to find the minimal-order annihilating operator of a given definite sum or integral. We offer an explanation based on the consideration of residues.

Jonas Stübbe, Anne Remke, Erika Ábrahám

This paper presents optimizations to improve the scalability of reachability analysis on a subclass of hybrid automata extended with stochasticity. The optimizations target different components of the analysis, such as quantifier elimination for state set projection, and automated parameter selection during the numerical integration. Most importantly, whereas the original method combines forward and backward reachability, we show that the usage of backward reachability is optional for computing maximal reachability probabilities.

Shaoshi Chen, Ruyong Feng, Pingchuan Ma et al.

For given multivariate functions specified by algebraic, differential or difference equations, the separability problem is to decide whether they satisfy linear differential or difference equations in one variable. In this paper, we will explain how separability problems arise naturally in creative telescoping and present some criteria for testing the separability for several classes of special functions, including rational functions, hyperexponential functions, hypergeometric terms, and algebraic functions.

Xavier Dahan, Tristan Vaccon

Newton's method is an ubiquitous tool to solve equations, both in the archimedean and non-archimedean settings -- for which it does not really differ. Broyden was the instigator of what is called "quasi-Newton methods". These methods use an iteration step where one does not need to compute a complete Jacobian matrix nor its inverse. We provide an adaptation of Broyden's method in a general non-archimedean setting, compatible with the lack of inner product, and study its Q and R convergence. We prove that our adapted method converges at least Q-linearly and R-superlinearly with R-order $2^{\frac{1}{2m}}$ in dimension m. Numerical data are provided.

Alin Bostan, Ryuhei Mori

We present a simple and fast algorithm for computing the $N$-th term of a given linearly recurrent sequence. Our new algorithm uses $O(\mathsf{M}(d) \log N)$ arithmetic operations, where $d$ is the order of the recurrence, and $\mathsf{M}(d)$ denotes the number of arithmetic operations for computing the product of two polynomials of degree $d$. The state-of-the-art algorithm, due to Charles Fiduccia (1985), has the same arithmetic complexity up to a constant factor. Our algorithm is simpler, faster and obtained by a totally different method. We also discuss several algorithmic applications, notably to polynomial modular exponentiation, powering of matrices and high-order lifting.

Seung Gyu Hyun, Stephen Melczer, Éric Schost et al.

Following recent work by van der Hoeven and Lecerf (ISSAC 2017), we discuss the complexity of linear mappings, called untangling and tangling by those authors, that arise in the context of computations with univariate polynomials. We give a slightly faster tangling algorithm and discuss new applications of these techniques. We show how to extend these ideas to bivariate settings, and use them to give bounds on the arithmetic complexity of certain algebras.

Alessio Caminata, Elisa Gorla

In this note, we leverage some of our results from arXiv:1706.06319 to produce a concise and rigorous proof for the complexity of the generalized MinRank Problem in the under-defined and well-defined case. Our main theorem recovers and extends previous results by Faugère, Safey El Din, Spaenlehauer (arXiv:1112.4411).

Jonas Klappert, Fabian Lange

We present the open-source $\texttt{C++}$ library $\texttt{FireFly}$ for the reconstruction of multivariate rational functions over finite fields. We discuss the involved algorithms and their implementation. As an application, we use $\texttt{FireFly}$ in the context of integration-by-parts reductions and compare runtime and memory consumption to a fully algebraic approach with the program $\texttt{Kira}$.

Gavin Harrison, Jeremy Johnson, B. David Saunders

We determine the probability, structure dependent, that the block Wiedemann algorithm correctly computes leading invariant factors. This leads to a tight lower bound for the probability, structure independent. We show, using block size slightly larger than $r$, that the leading $r$ invariant factors are computed correctly with high probability over any field. Moreover, an algorithm is provided to compute the probability bound for a given matrix size and thus to select the block size needed to obtain the desired probability. The worst case probability bound is improved, post hoc, by incorporating the partial information about the invariant factors.

Pascal Koiran

We give a separation bound for the complex roots of a trinomial $f \in \mathbb{Z}[X]$. The logarithm of the inverse of our separation bound is polynomial in the size of the sparse encoding of $f$; in particular, it is polynomial in $\log (°f)$. It is known that no such bound is possible for 4-nomials (polynomials with 4 monomials). For trinomials, the classical results (which are based on the degree of $f$ rather than the number of monomials) give separation bounds that are exponentially worse.As an algorithmic application, we show that the number of real roots of a trinomial $f$ can be computed in time polynomial in the size of the sparse encoding of~$f$. The same problem is open for 4-nomials.

Johan S. R. Nielsen, Arne Storjohann

We describe how to solve simultaneous Padé approximations over a power series ring $K[[x]]$ for a field $K$ using $O~(n^{ω- 1} d)$ operations in $K$, where $d$ is the sought precision and $n$ is the number of power series to approximate. We develop two algorithms using different approaches. Both algorithms return a reduced sub-bases that generates the complete set of solutions to the input approximations problem that satisfy the given degree constraints. Our results are made possible by recent breakthroughs in fast computations of minimal approximant bases and Hermite Padé approximations.

Guénaël Renault, Tristan Vaccon

Nowadays, many strategies to solve polynomial systems use the computation of a Gr{ö}bner basis for the graded reverse lexicographical ordering, followed by a change of ordering algorithm to obtain a Gr{ö}bner basis for the lexicographical ordering. The change of ordering algorithm is crucial for these strategies. We study the p-adic stability of the main change of ordering algorithm, FGLM. We show that FGLM is stable and give explicit upper bound on the loss of precision occuring in its execution. The variant of FGLM designed to pass from the grevlex ordering to a Gr{ö}bner basis in shape position is also stable. Our study relies on the application of Smith Normal Form computations for linear algebra.

Sébastien Maulat, Bruno Salvy

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.

Xiaolin Qin, Zhi Sun, Tuo Leng et al.

Computing the determinant of a matrix with the univariate and multivariate polynomial entries arises frequently in the scientific computing and engineering fields. In this paper, an effective algorithm is presented for computing the determinant of a matrix with polynomial entries using hybrid symbolic and numerical computation. The algorithm relies on the Newton's interpolation method with error control for solving Vandermonde systems. It is also based on a novel approach for estimating the degree of variables, and the degree homomorphism method for dimension reduction. Furthermore, the parallelization of the method arises naturally.

Shaoshi Chen, Manuel Kauers

We analyze the differential equations produced by the method of creative telescoping applied to a hyperexponential term in two variables. We show that equations of low order have high degree, and that higher order equations have lower degree. More precisely, we derive degree bounding formulas which allow to estimate the degree of the output equations from creative telescoping as a function of the order. As an application, we show how the knowledge of these formulas can be used to improve, at least in principle, the performance of creative telescoping implementations, and we deduce bounds on the asymptotic complexity of creative telescoping for hyperexponential terms.

Luca De Feo, Éric Schost

An Artin-Schreier tower over the finite field F_p is a tower of field extensions generated by polynomials of the form X^p - X - a. Following Cantor and Couveignes, we give algorithms with quasi-linear time complexity for arithmetic operations in such towers. As an application, we present an implementation of Couveignes' algorithm for computing isogenies between elliptic curves using the p-torsion.

Frédéric Chyzak, Manuel Kauers, Bruno Salvy

We extend Zeilberger's approach to special function identities to cases that are not holonomic. The method of creative telescoping is thus applied to definite sums or integrals involving Stirling or Bernoulli numbers, incomplete Gamma function or polylogarithms, which are not covered by the holonomic framework. The basic idea is to take into account the dimension of appropriate ideals in Ore algebras. This unifies several earlier extensions and provides algorithms for summation and integration in classes that had not been accessible to computer algebra before.

Juan Gerardo Alcazar

In this paper we study the local behavior of an algebraic curve under a geometric construction which is a variation of the usual offsetting construction, namely the {\it generalized} offsetting process (\cite {SS99}). More precisely, here we discuss when and how this geometric construction may cause local changes in the shape of an algebraic curve, and we compare our results with those obtained for the case of classical offsets (\cite{JGS07}). For these purposes, we use well-known notions of Differential Geometry, and also the notion of {\it local shape} introduced in \cite{JGS07}.

Alexander Yu. Vlasov

The advantages of mixed approach with using different kinds of programming techniques for symbolic manipulation are discussed. The main purpose of approach offered is merge the methods of object oriented programming that convenient for presentation data and algorithms for user with advantages of functional languages for data manipulation, internal presentation, and portability of software.