Hasil untuk "cs.SC"

Hadrien Brochet, Frédéric Chyzak, Pierre Lairez

We present a new algorithm for solving the reduction problem in the context of holonomic integrals, which in turn provides an approach to integration with parameters. Our method extends the Griffiths--Dwork reduction technique to holonomic systems and is implemented in Julia. While not yet outperforming creative telescoping in D-finite cases, it enhances computational capabilities within the holonomic framework. As an application, we derive a previously unattainable differential equation for the generating series of 8-regular graphs.

Gleb Pogudin

When using resultants for elimination, one standard issue is that the resultant vanishes if the variety contains components of dimension larger than the expected dimension. J. Canny proposed an elegant construction, generalized characteristic polynomial, to address this issue by symbolically perturbing the system before the resultant computation. Such perturbed resultant would typically involve artefact components only loosely related to the geometry of the variety of interest. For removing these components, J.M. Rojas proposed to take the greatest common divisor of the results of two different perturbations. In this paper, we investigate this construction, and show that the extra components persistent under taking different perturbations must come either from singularities or from positive-dimensional fibers.

Antonio Jiménez-Pastor, Ali Kemal Uncu

The Factorial Basis method, initially designed for quasi-triangular, shift-compatible factorial bases, provides solutions to linear recurrence equations in the form of definite-sums. This paper extends the Factorial Basis method to its q-analog, enabling its application in q-calculus. We demonstrate the adaptation of the method to q-sequences and its utility in the realm of q-combinatorics. The extended technique is employed to automatically prove established identities and unveil novel ones, particularly some associated with the Rogers-Ramanujan identities.

Weidong Wang, Jing Yang

In this paper, we develop two variants of Bezout subresultant formulas for several polynomials, i.e., hybrid Bezout subresultant polynomial and non-homogeneous Bezout subresultant polynomial. Rather than simply extending the variants of Bezout subresultant formulas developed by Diaz-Toca and Gonzalez-Vega in 2004 for two polynomials to arbitrary number of polynomials, we propose a new approach to formulating two variants of the Bezout-type subresultant polynomials for a set of univariate polynomials. Experimental results show that the Bezout-type subresultant formulas behave better than other known formulas when used to compute multi-polynomial subresultants, among which the non-homogeneous Bezout-type formula shows the best performance.

Philippe Pébay, J. Maurice Rojas, David C. Thompson

Sturm's Theorem is a fundamental 19th century result relating the number of real roots of a polynomial $f$ in an interval to the number of sign alternations in a sequence of polynomial division-like calculations. We provide a short direct proof of Sturm's Theorem, including the numerically vexing case (ignored in many published accounts) where an interval endpoint is a root of $f$.

Colin Faverjon, Marina Poulet

This paper is devoted to the study of the analytic properties of Mahler systems at 0. We give an effective characterisation of Mahler systems that are regular singular at 0, that is, systems which are equivalent to constant ones. Similar characterisations already exist for differential and (q-)difference systems but they do not apply in the Mahler case. This work fills in the gap by giving an algorithm which decides whether or not a Mahler system is regular singular at 0. In particular, it gives an effective characterisation of Mahler systems to which an analog of Schlesinger's density theorem applies.

Dong Lu, Dingkang Wang, Fanghui Xiao

This paper is concerned with factor left prime factorization problems for multivariate polynomial matrices without full row rank. We propose a necessary and sufficient condition for the existence of factor left prime factorizations of a class of multivariate polynomial matrices, and then design an algorithm to compute all factor left prime factorizations if they exist. We implement the algorithm on the computer algebra system Maple, and two examples are given to illustrate the effectiveness of the algorithm. The results presented in this paper are also true for the existence of factor right prime factorizations of multivariate polynomial matrices without full column rank.

Marijn J. H. Heule, Manuel Kauers, Martina Seidl

It is known since the 1970s that no more than 23 multiplications are required for computing the product of two 3 x 3-matrices. It is not known whether this can also be done with fewer multiplications. However, there are several mutually inequivalent ways of doing the job with 23 multiplications. In this article, we extend this list considerably by providing more than 13 000 new and mutually inequivalent schemes for multiplying 3 x 3-matrices using 23 multiplications. Moreover, we show that the set of all these schemes is a manifold of dimension at least 17.

Viviane Ledoux, Guillaume Moroz

In approximation theory, it is standard to approximate functions by polynomials expressed in the Chebyshev basis. Evaluating a polynomial $f$ of degree n given in the Chebyshev basis can be done in $O(n)$ arithmetic operations using the Clenshaw algorithm. Unfortunately, the evaluation of $f$ on an interval $I$ using the Clenshaw algorithm with interval arithmetic returns an interval of width exponential in $n$. We describe a variant of the Clenshaw algorithm based on ball arithmetic that returns an interval of width quadratic in $n$ for an interval of small enough width. As an application, our variant of the Clenshaw algorithm can be used to design an efficient root finding algorithm.

David Harvey, Joris van der Hoeven

We prove that $n$-bit integers may be multiplied in $O(n \log n \, 4^{\log^* n})$ bit operations. This complexity bound had been achieved previously by several authors, assuming various unproved number-theoretic hypotheses. Our proof is unconditional, and depends in an essential way on Minkowski's theorem concerning lattice vectors in symmetric convex sets.

Chun-Ming Yuan, Zhi-Yong Zhang

The sparse difference resultant introduced in \citep{gao-2015} is a basic concept in difference elimination theory. In this paper, we show that the sparse difference resultant of a generic Laurent transformally essential system can be computed via the sparse resultant of a simple algebraic system arising from the difference system. Moreover, new order bounds of sparse difference resultant are found. Then we propose an efficient algorithm to compute sparse difference resultant which is the quotient of two determinants whose elements are the coefficients of the polynomials in the algebraic system. The complexity of the algorithm is analyzed and experimental results show the efficiency of the algorithm.

Alin Bostan, Xavier Caruso, Eric Schost

The $p$-curvature of a system of linear differential equations in positive characteristic $p$ is a matrix that measures how far the system is from having a basis of polynomial solutions. We show that the similarity class of the $p$-curvature can be determined without computing the $p$-curvature itself. More precisely, we design an algorithm that computes the invariant factors of the $p$-curvature in time quasi-linear in $\sqrt p$. This is much less than the size of the $p$-curvature, which is generally linear in $p$. The new algorithm allows to answer a question originating from the study of the Ising model in statistical physics.

Olivier Ruatta, Mark Sciabica, Agnes Szanto

We propose a generalization of the Weierstrass iteration for over-constrained systems of equations and we prove that the proposed method is the Gauss-Newton iteration to find the nearest system which has at least $k$ common roots and which is obtained via a perturbation of prescribed structure. In the univariate case we show the connection of our method to the optimization problem formulated by Karmarkar and Lakshman for the nearest GCD. In the multivariate case we generalize the expressions of Karmarkar and Lakshman, and give explicitly several iteration functions to compute the optimum. The arithmetic complexity of the iterations is detailed.

Shaoshi Chen, Ruyong Feng, Guofeng Fu et al.

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 present an application.

Xiaolin Qin, Yong Feng, Jingwei Chen et al.

We present a new algorithm for solving the real roots of a bivariate polynomial system $Σ=\{f(x,y),g(x,y)\}$ with a finite number of solutions by using a zero-matching method. The method is based on a lower bound for bivariate polynomial system when the system is non-zero. Moreover, the multiplicities of the roots of $Σ=0$ can be obtained by a given neighborhood. From this approach, the parallelization of the method arises naturally. By using a multidimensional matching method this principle can be generalized to the multivariate equation systems.

Yong Yao

The theory part of this paper is sketched as follows. Based on column stochastic average matrix $T_n$ selected as a basic substitution matrix, the method of advanced successive difference substitution is established. Then, a set of necessary and sufficient conditions for deciding positive semi-definite form on $\R^n_+$ is derived from this method. And furthermore, it is proved that the sequence of SDS sets of a positive definite form is positively terminating. Worked out according to these results, the Maple program TSDS3 not only automatically proves the polynomial inequalities, but also outputs counter examples for the false. Sometimes TSDS3 does not halt, but it is very useful by experimenting on so many examples.

Gérard Henry Edmond Duchamp, Christophe Tollu, K. A. Penson et al.

The framework used to prove the multiplicative law deformation of the algebra of Feynman-Bender diagrams is a \textit{twisted shifted dual law} (in fact, twice). We give here a clear interpretation of its two parameters. The crossing parameter is a deformation of the tensor structure whereas the superposition parameters is a perturbation of the shuffle coproduct of Hoffman type which, in turn, can be interpreted as the diagonal restriction of a superproduct. Here, we systematically detail these constructions.

Jaime Gutierrez, Rosario Rubio, David Sevilla

In this paper we present an algorithm to compute all unirational fields of transcendence degree one containing a given finite set of multivariate rational functions. In particular, we provide an algorithm to decompose a multivariate rational function f of the form f=g(h), where g is a univariate rational function and h a multivariate one.

Yong Feng, Jingzhong Zhang, Xiaolin Qin et al.

In some fields such as Mathematics Mechanization, automated reasoning and Trustworthy Computing etc., exact results are needed. Symbolic computations are used to obtain the exact results. Symbolic computations are of high complexity. In order to improve the situation, exactly interpolating methods are often proposed for the exact results and approximate interpolating methods for the approximate ones. In this paper, we study how to obtain exact interpolation polynomial with rational coefficients by approximate interpolating methods.

Gilles Villard

Kaltofen has proposed a new approach in [Kaltofen 1992] for computing matrix determinants. The algorithm is based on a baby steps/giant steps construction of Krylov subspaces, and computes the determinant as the constant term of a characteristic polynomial. For matrices over an abstract field and by the results of Baur and Strassen 1983, the determinant algorithm, actually a straight-line program, leads to an algorithm with the same complexity for computing the adjoint of a matrix [Kaltofen 1992]. However, the latter is obtained by the reverse mode of automatic differentiation and somehow is not ``explicit''. We study this adjoint algorithm, show how it can be implemented (without resorting to an automatic transformation), and demonstrate its use on polynomial matrices.