We review the definition and main properties of differential subresultants in order to achieve their implementation in Maple, using the DEtools package. The focus is on computing GCRDs of ordinary differential operators with non necessarily rational coefficients. Determinant expressions provide explicit control, enabling the treatment of coefficients with parameters. Applications to commuting ordinary differential operators illustrate the effectiveness of the method.
We study certain linear algebra algorithms for recursive block matrices. This representation has useful practical and theoretical properties. We summarize some previous results for block matrix inversion and present some results on triangular decomposition of block matrices. The case of inverting matrices over a ring that is neither formally real nor formally complex was inspired by Gonzalez-Vega et al.
In this paper, we give an algorithm for finding general rational solutions of a given first-order ODE with parametric coefficients that occur rationally. We present an analysis, complete modulo Hilbert's irreducibility problem, of the existence of rational solutions of the differential equation, with parametric coefficients, when the parameters are specialized.
We introduce a new method for discovering matrix multiplication schemes based on random walks in a certain graph, which we call the flip graph. Using this method, we were able to reduce the number of multiplications for the matrix formats (4, 4, 5) and (5, 5, 5), both in characteristic two and for arbitrary ground fields.
Effective methods are introduced for testing zero-dimensionality of varieties at a point. The motivation of this paper is to compute and analyze deformations of isolated hypersurface singularities. As an application, methods for computing local dimensions are also described. For the case where a given ideal contains parameters, the proposed algorithms can output in particular a decomposition of a parameter space into strata according to the local dimension at a point of the associated varieties. The key of the proposed algorithms is the use of the notion of comprehensive Gröbner systems.
We propose an algebraic geometric approach for studying rational solutions of first-order algebraic ordinary difference equations. For an autonomous first-order algebraic ordinary difference equations, we give an upper bound for the degrees of its rational solutions, and thus derive a complete algorithm for computing corresponding rational solutions.
We show that reverse mode automatic differentiation and symbolic differentiation are equivalent in the sense that they both perform the same operations when computing derivatives. This is in stark contrast to the common claim that they are substantially different. The difference is often illustrated by claiming that symbolic differentiation suffers from "expression swell" whereas automatic differentiation does not. Here, we show that this statement is not true. "Expression swell" refers to the phenomenon of a much larger representation of the derivative as opposed to the representation of the original function.
For an elliptic curve $E$ over a finite field $\F_q$, where $q$ is a prime power, we propose new algorithms for testing the supersingularity of $E$. Our algorithms are based on the Polynomial Identity Testing (PIT) problem for the $p$-th division polynomial of $E$. In particular, an efficient algorithm using points of high order on $E$ is given.
In this paper, we give decision criteria for normal binomial difference polynomial ideals in the univariate difference polynomial ring F{y} to have finite difference Groebner bases and an algorithm to compute the finite difference Groebner bases if these criteria are satisfied. The novelty of these criteria lies in the fact that complicated properties about difference polynomial ideals are reduced to elementary properties of univariate polynomials in Z[x].
In this paper, we briefly discuss the dynamic and functional approach to computer symbolic tensor analysis. The ccgrg package for Wolfram Language/Mathematica is used to illustrate this approach. Some examples of applications are attached.
Moulay A. Barkatou, Maximilian Jaroschek, Suzy S. Maddah
In this paper, we present an algorithm for computing a fundamental matrix of formal solutions of completely integrable Pfaffian systems with normal crossings in several variables. This algorithm is a generalization of a method developed for the bivariate case based on a combination of several reduction techniques and is implemented in the computer algebra system Maple.
Consider the problem: given a real number $x$ and an error bound $ε$, find an interval such that it contains the $\sqrt[n]{x}$ and its width is less than $ε$. One way to solve the problem is to start with an initial interval and to repeatedly update it by applying an interval refinement map on it until it becomes narrow enough. In this paper, we prove that the well known Secant-Newton map is optimal among a certain family of natural generalizations.
In this paper, we consider the problem of computing estimates of the domain-of-attraction for non-polynomial systems. A polynomial approximation technique, based on multivariate polynomial interpolation and error analysis for remaining functions, is applied to compute an uncertain polynomial system, whose set of trajectories contains that of the original non-polynomial system. Experiments on the benchmark non-polynomial systems show that our approach gives better estimates of the domain-of-attraction.
We present a criterion for the existence of telescopers for mixed hypergeometric terms, which is based on multiplicative and additive decompositions. The criterion enables us to determine the termination of Zeilberger's algorithms for mixed hypergeometric inputs.
Truncated Fourier Transforms (TFTs), first introduced by Van der Hoeven, refer to a family of algorithms that attempt to smooth "jumps" in complexity exhibited by FFT algorithms. We present an in-place TFT whose time complexity, measured in terms of ring operations, is comparable to existing not-in-place TFT methods. We also describe a transformation that maps between two families of TFT algorithms that use different sets of evaluation points.
Insa and Pauer presented a basic theory of Groebner basis for differential operators with coefficients in a commutative ring in 1998, and a criterion was proposed to determine if a set of differential operators is a Groebner basis. In this paper, we will give a new criterion such that Insa and Pauer's criterion could be concluded as a special case and one could compute the Groebner basis more efficiently by this new criterion.
We describe an algorithm that takes as input a complex sequence $(u_n)$ given by a linear recurrence relation with polynomial coefficients along with initial values, and outputs a simple explicit upper bound $(v_n)$ such that $|u_n| \leq v_n$ for all $n$. Generically, the bound is tight, in the sense that its asymptotic behaviour matches that of $u_n$. We discuss applications to the evaluation of power series with guaranteed precision.