Search

This paper addresses the problem of computing valuations of the Dieudonné determinants of matrices over discrete valuation skew fields (DVSFs). Under a reasonable computational model, we propose two algorithms for a class of DVSFs, called split. Our algorithms are extensions of the combinatorial relaxation of Murota (1995) and the matrix expansion by Moriyama and Murota (2013) , both of which are based on combinatorial optimization. While our algorithms require an upper bound on the output, we give an estimation of the bound for skew polynomial matrices and show that the estimation is valid only for skew polynomial matrices. We consider two applications of this problem. The first one is the noncommutative weighted Edmonds' problem (nc-WEP), which is to compute the degree of the Dieudonné determinants of matrices having noncommutative symbols. We show that the presented algorithms reduce the nc-WEP to the unweighted problem in polynomial time. In particular, we show that the nc-WEP over the rational field is solvable in time polynomial in the input bit-length. We also present an application to analyses of degrees of freedom of linear time-varying systems by establishing formulas on the solution spaces of linear differential/difference equations. [ABSTRACT FROM AUTHOR]

One method to determine whether or not a system of partial differential equations is consistent is to attempt to construct a solution using merely the “algebraic data” associated to the system. In technical terms, this translates to the problem of determining the existence of regular realizations of differential kernels via their possible prolongations. In this paper we effectively compute an improved upper bound for the number of prolongations needed to guarantee the existence of such realizations, which ultimately produces solutions to many types of systems of partial differential equations. This bound has several applications, including an improved upper bound for the order of characteristic sets of prime differential ideals. We obtain our upper bound by proving a new result on the growth of the Hilbert–Samuel function, which may be of independent interest. [ABSTRACT FROM AUTHOR]

Abstract: The aim of this paper is to investigate the possibility of solving a linear differential equation of degree by means of differential equations of degree less than or equal to a fixed , . This paper recovers and extends work of G. Fano, M. F. Singer and E. Compoint. Representations of algebraic Lie algebras are the main tool. [Copyright &y& Elsevier]

Abstract: Let be a linear differential operator, where is the field of algebraic numbers. A holonomic function over is a solution to the equation . We will also assume that admits initial conditions in at a non-singular point . Given a broken-line path between and , which avoids the singularities of and with vertices in , we have shown in a previous paper [van der Hoeven, J., 1999. Fast evaluation of holonomic functions. Theoret. Comput. Sci. 210, 199–215] how to compute digits of the analytic continuation of  along in time . In a second paper [van der Hoeven, J., 2001b. Fast evaluation of holonomic functions near and in singularities. J. Symbolic Comput. 31, 717–743], this result was generalized to the case when is allowed to be a regular singularity, in which case we compute the limit of  when we approach the singularity along . In the present paper, we treat the remaining case when the end-point of is an irregular singularity. In fact, we will solve the more general problem to compute “singular transition matrices” between non-standard points above a singularity and regular points in near the singularity. These non-standard points correspond to the choice of “non-singular directions” in Écalle’s accelero-summation process. We will show that the entries of the singular transition matrices may be approximated up to decimal digits in time . As a consequence, the entries of the Stokes matrices for at each singularity may be approximated with the same time complexity. [Copyright &y& Elsevier]

Abstract: This paper advances the design of a unified model for the representation of search in first-order clausal theorem-proving, by extending to tableau-based subgoal-reduction strategies (e.g., model-elimination tableaux), the marked search-graph model, already introduced for ordering-based strategies, those that use (ordered) resolution, paramodulation/superposition, simplification, and subsumption. The resulting analytic marked search-graphs subsume AND–OR graphs, and allow us to represent those dynamic components, such as backtracking and instantiation of rigid variables, that have long been an obstacle to modelling subgoal-reduction strategies properly. The second part of the paper develops for analytic marked search-graphs the bounded search spaces approach to the analysis of infinite search spaces. We analyze how tableau inferences and backtracking affect the bounded search spaces during a derivation. Then, we apply this analysis to measure the effects of regularity and lemmatization by folding-up on search complexity, by comparing the bounded search spaces of strategies with and without these features. We conclude with a discussion comparing the marked search-graphs for tableaux, linear resolution, and ordering-based strategies, showing how this search model applies across these classes of strategies. [Copyright &y& Elsevier]

The notion of strict equivalence for order one differential equations of the form f ( y ′ , y , z ) = 0 with coefficients in a finite extension K of C ( z ) is introduced. The equation gives rise to a curve X over K and a derivation D on its function field K ( X ) . Procedures are described for testing strict equivalence, strict equivalence to an autonomous equation, computing algebraic solutions and verifying the Painlevé property. These procedures use known algorithms for isomorphisms of curves over an algebraically closed field of characteristic zero, the Risch algorithm and computation of algebraic solutions. The most involved cases concern curves X of genus 0 or 1. This paper complements work of M. Matsuda and of G. Muntingh & M. van der Put. [ABSTRACT FROM AUTHOR]

We consider the problem of counting (stable) equilibriums of an important family of algebraic differential equations modeling multistable biological regulatory systems. The problem can be solved, in principle, using real quantifier elimination algorithms, in particular real root classification algorithms. However, it is well known that they can handle only very small cases due to the enormous computing time requirements. In this paper, we present a special algorithm which is much more efficient than the general methods. Its efficiency comes from the exploitation of certain interesting structures of the family of differential equations. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we provide an algorithm to compute explicit rational solutions of a rational system of autonomous ordinary differential equations (ODEs) from its rational invariant algebraic curves. The method is based on the proper rational parametrization of these curves and the fact that by linear reparametrizations, we can find the rational solutions of the given system of ODEs. Moreover, if the system has a rational first integral, we can decide whether it has a rational general solution and compute it in the affirmative case. [Copyright &y& Elsevier]

Abstract: Let be the ring of power series over an effective ring . In , it was first shown that differential equations over may be solved in an asymptotically efficient way using Newton’s method. More precisely, if denotes the complexity for multiplying two polynomials of degree over , then the first coefficients of the solution can be computed in time . However, this complexity does not take into account the dependency on the order of the equation, which is exponential for the original method () and quadratic for a recent improvement (). In this paper, we present a technique for further improving the dependency on , by applying Newton’s method up to a lower order, such as , and trading the remaining Newton steps against a lazy or relaxed algorithm in a suitable FFT model. The technique leads to improved asymptotic complexities for several basic operations on formal power series, such as division, exponentiation and the resolution of more general linear and non-linear systems of equations. [Copyright &y& Elsevier]

Abstract: Consider a power series , which is obtained by a precise mathematical construction. For instance, might be the solution to some differential or functional initial value problem or the diagonal of the solution to a partial differential equation. In cases when no suitable method is available beforehand for determining the asymptotics of the coefficients , but when many such coefficients can be computed with high accuracy, it would be useful if a plausible asymptotic expansion for could be guessed automatically. In this paper, we will present a general scheme for the design of such “asymptotic extrapolation algorithms”. Roughly speaking, using discrete differentiation and techniques from automatic asymptotics, we strip off the terms of the asymptotic expansion one by one. The knowledge of more terms of the asymptotic expansion will then allow us to approximate the coefficients in the expansion with high accuracy. [Copyright &y& Elsevier]

Abstract: Hypersurface isolated singularities are considered in the context of algebraic analysis. A method for computing relative Čech cohomology representations of algebraic local cohomology classes supported at the isolated singular point is described. An effective method to test membership and a method to compute the normal form for the Jacobi ideal are presented. The main purpose of this paper is to provide an effective algorithm for computing annihilating ideals, in the ring of partial differential operators, of the algebraic local cohomology class that generates the dual vector space to the local Milnor algebra. [Copyright &y& Elsevier]

Abstract: In this paper, we generalize the results of Feng and Gao [Feng, R., Gao, X.S., 2006. A polynomial time algorithm to find rational general solutions of first order autonomous ODEs. J. Symbolic Comput., 41(7), 735–762] to the case of difference equations. We construct two classes of ordinary difference equations () whose solutions are exactly the univariate polynomial and rational functions respectively. On the basis of these and the difference characteristic set method, we give a criterion for an with any order and nonconstant coefficients to have a rational type general solution. For the first-order autonomous (constant coefficient) , we give a polynomial time algorithm for finding the polynomial solutions and an algorithm for finding the rational solutions for a given degree. [Copyright &y& Elsevier]

Abstract: In this paper we present a new algorithmic approach for computing the Hilbert function of a finitely generated difference-differential module equipped with the natural double filtration. The approach is based on a method of special Gröbner bases with respect to “generalized term orders” on and on difference-differential modules. We define a special type of reduction for two generalized term orders in a free left module over a ring of difference-differential operators. Then the concept of relative Gröbner bases w.r.t. two generalized term orders is defined. An algorithm for constructing these relative Gröbner bases is presented and verified. Using relative Gröbner bases, we are able to compute difference-differential dimension polynomials in two variables. [Copyright &y& Elsevier]

Abstract: Let be a rational function in one variable. By Lüroth’s theorem, the collection of intermediate fields is in bijection with inequivalent proper decompositions , with of degrees . In [Alonso, Cesar, Gutierrez, Jaime, Recio, Tomas, 1995. A rational function decomposition algorithm by near-separated polynomials. J. Symbolic Comput. 19, 527–544] an algorithm is presented to calculate such a function decomposition. In this paper we describe a simplification of this algorithm, avoiding expensive solutions of linear equations. A MAGMA implementation shows the efficiency of our method. We also prove some indecomposability criteria for rational functions, which were motivated by computational experiments. [Copyright &y& Elsevier]

Abstract: Let and , where is an effective field and and are given a suitable asymptotic ordering . Consider the mapping , where . For , it is natural to ask how to solve the system . In this paper, we will effectively characterize and show how to compute a so called distinguished right inverse of . We will also characterize the solution space of the homogeneous equation . [Copyright &y& Elsevier]

Abstract: Let be a linear differential operator, where is an effective algebraically closed subfield of . It can be shown that the differential Galois group of  is generated (as a closed algebraic group) by a finite number of monodromy matrices, Stokes matrices and matrices in local exponential groups. Moreover, there exist fast algorithms for the approximation of the entries of these matrices. In this paper, we present a numeric–symbolic algorithm for the computation of the closed algebraic subgroup generated by a finite number of invertible matrices. Using the above results, this yields an algorithm for the computation of differential Galois groups, when computing with a sufficient precision. Even though there is no straightforward way to find a “sufficient precision” for guaranteeing the correctness of the end result, it is often possible to check a posteriori whether the end result is correct. In particular, we present a non-heuristic algorithm for the factorization of linear differential operators. [Copyright &y& Elsevier]

Abstract: An algorithm is presented that computes explicit generators for the ring of differential operators on an orbifold, the quotient of a complex vector space by a finite group action. The algorithm also describes the relations among these generators. The algorithm presented in this paper is based on Schwarz’s study of a map carrying invariant operators to operators on the orbifold and on an algorithm to compute rings of invariants using Gröbner bases due to Derksen [Derksen, Harm, 1999. Computation of invariants for reductive groups. Adv. Math. 141 (2), 366–384]. It is also possible to avoid using Derksen’s algorithm, instead relying on the Reynolds operator and the Molien series. [Copyright &y& Elsevier]

Abstract: The calculation of threshold conditions for models of infectious diseases is of central importance for developing vaccination policies. These models are often coupled systems of ordinary differential equations, in which case the computation of threshold conditions can be reduced to the question of stability of the disease-free equilibrium. This paper shows how computing threshold conditions for such models can be done fully algorithmically using quantifier elimination for real closed fields and related simplification methods for quantifier-free formulas. Using efficient quantifier elimination techniques for special cases that have been developed by Weispfenning and others, we can also compute whether there are ranges of parameters for which sub-threshold endemic equilibria exist. [Copyright &y& Elsevier]

Abstract: In this paper, we analyze the complexity of a zero-test for expressions built from formal power series solutions of first order differential equations with non-degenerate initial conditions. We will prove a doubly exponential complexity bound. This bound establishes a power series analogue for “witness conjectures”. [Copyright &y& Elsevier]

Abstract: In this paper we give a very easy to compute necessary condition in the monodromy problem for all singular point of analytic differential systems in the real plane. Our main tool is considering the analytic function, angular speed, and studying its limit through straight lines to the singular point. [Copyright &y& Elsevier]

Abstract: In this paper, we report on a new theorem that generalizes Liouville’s theorem on integration in finite terms. The new theorem allows dilogarithms to occur in the integral in addition to transcendental elementary functions. The proof is based on two identities for the dilogarithm, that characterize all the possible algebraic relations among dilogarithms of functions that are built up from the rational functions by taking transcendental exponentials, dilogarithms, and logarithms. This means that we assume the integral lies in a transcendental tower. [Copyright &y& Elsevier]

Abstract: Let be the ring of polynomials with complex coefficients and the Weyl algebra of order over . Elements in are linear differential operators with polynomial coefficients. For each polynomial , the ring of rational functions with poles along has a natural structure of a left -module which is finitely generated by a classical result of I.N. Bernstein. A central problem in this context is how to find a finite presentation of starting from the input . In this paper we use Gröbner base theory in the non-commutative frame of the ring to compare to some other -modules arising in Singularity Theory as the so-called logarithmic -modules. We also show how the analytic case can be treated with computations in the Weyl algebra if the input data is a polynomial. [Copyright &y& Elsevier]

Abstract: One approach for computations with special functions in computer algebra is the systematic use of analytic functions whenever possible. This naturally leads to problems of how to answer questions about analytic functions in a fully effective way. Such questions comprise the determination of the radius of convergence or the evaluation of the analytic continuation of the function at the endpoint of a broken line path. In this paper, we propose a first definition for the notion of an effective analytic function and we show how to effectively solve several types of differential equations in this context. We will limit ourselves to functions in one variable. [Copyright &y& Elsevier]

Abstract: This paper is an informal introduction to differential Galois theory. It surveys recent work on differential Galois groups, related algorithms and some applications. [Copyright &y& Elsevier]

In this paper, we propose algorithms for the following problems in the implicitization of a set of differential rational parametric equations P. (1) To find a characteristic set for the implicit prime ideal of P. (2) To find a canonical representation for the image of P. (3) To decide whether the parameters of P are independent, and if not, to re-parameterize P so that the new parametric equations have independent parameters. (4) To compute the inversion maps of P, and as a consequence, to decide whether P is proper. If the implicit variety is of dimension one and P is not proper, to find a proper re-parameterization for P. [Copyright &y& Elsevier]

This paper presents a matching pursuit technique for computing the simplest normal forms of vector fields. First a simple, explicit recursive formula is derived for general differential equations, which reduces computation to the minimum. Then a matching pursuit technique is introduced and applied to the Takens–Bogdanov dynamical singularity. It is shown that unlike other methods for computing normal forms, the technique using matching pursuit does not need any algebraic constraints which are required for the existence of the simplest normal form. The efficient method and matching pursuit technique, which have been implemented using Maple, can be “automatically” executed on various computer systems. A number of examples are presented to demonstrate the advantages of the technique. [Copyright &y& Elsevier]