Linear relations among algebraic solutions of differential equations

For any univariate polynomial with coefficients in a differential field of characteristic zero and any integer, q, there exists an associated nonzero linear ordinary differential equation (LODE) with the following two properties. Each term of the LODE lies in the differential field generated by the rational numbers and the coefficients of the polynomial, and the qth power of each root of the polynomial is a solution of this LODE. This LODE is called a qth power resolvent of the polynomial. We will show how one can get a resolvent for the logarithmic derivative of the roots of a polynomial from the αth power resolvent of the polynomial, where α is an indeterminate that takes the place of q. We will demonstrate some simple relations among the algebraic and differential equations for the roots and their logarithmic derivatives. We will also prove several theorems regarding linear relations of roots of a polynomial over constants or the coefficient field of the polynomial depending upon the (nondifferential) Galois group. Finally, we will use a differential resolvent to solve the Riccati equation.     

A Gröbner Free Alternative for Polynomial System Solving

Given a system of polynomial equations and inequations with coefficients in the field of rational numbers, we show how to compute a geometric resolution of the set of common roots of the system over the field of complex numbers. A geometric resolution consists of a primitive element of the algebraic extension defined by the set of roots, its minimal polynomial, and the parametrizations of the coordinates. Such a representation of the solutions has a long history which goes back to Leopold Kronecker and has been revisited many times in computer algebra. We introduce a new generation of probabilistic algorithms where all the computations use only univariate or bivariate polynomials. We give a new codification of the set of solutions of a positive dimensional algebraic variety relying on a new global version of Newton's iterator. Roughly speaking the complexity of our algorithm is polynomial in some kind of degree of the system, in its height, and linear in the complexity of evaluation of the system. We present our implementation in the Magma system which is called Kronecker in homage to his method for solving systems of polynomial equations. We show that the theoretical complexity of our algorithm is well reflected in practice and we exhibit some cases for which our program is more efficient than the other available software.     

An algorithm for computing the factor ring of an ideal in a Dedekind domain with finite rank

We give an algorithm for computing the factor ring of a given ideal in a Dedekind domain with finite rank, which runs in deterministic and polynomial time. We provide two applications of the algorithm:judging whether a given ideal is prime or prime power. The main algorithm is based on basis representation of finite rings which is computed via Hermite and Smith normal forms.     

Solution of a stochastic Darcy equation by polynomial chaos expansion

This paper deals with solving a boundary value problem for the Darcy equation with a random hydraulic conductivity field.We use an approach based on polynomial chaos expansion in a probability space of input data.We use a probabilistic collocation method to calculate the coefficients of the polynomial chaos expansion. The computational complexity of this algorithm is determined by the order of the polynomial chaos expansion and the number of terms in the Karhunen–Loève expansion. We calculate various Eulerian and Lagrangian statistical characteristics of the flow by the conventional Monte Carlo and probabilistic collocation methods. Our calculations show a significant advantage of the probabilistic collocation method over the directMonte Carlo algorithm.     

Reducing systems of linear differential equations to a passive form

In this paper, an application of the Riquer-Thomas-Janet theory is described for the problem of transforming a system of partial differential equations into a passive form, i.e., to a special form which contains explicitly both the equations of the initial system and all their nontrivial differential consequences. This special representation of a system markedly facilitates the subsequent integration of the corresponding differential equations. In this paper, the modern approach to the indicated problem is presented. This is the approach adopted in the Knuth-Bendix procedure [13] for critical-pair/completion and then Buchberger's algorithm for completion of polynomial ideal bases [13] (or, alternatively, for the construction of Groebner bases for ideals in a differential operator ring [14]). The algorithm of reduction to the passive form for linear system of partial differential equations and its implementation in the algorithmic language REFAL, as well as the capabilities of the corresponding program, are outlined. Examples illustrating the power and efficiency of the system are presented.     

On the generalized Ritt problem as a computational problem

The Ritt problem asks if there is an algorithm that decides whether one prime differential ideal is contained in another one if both are given by their characteristic sets. We give several equivalent formulations of this problem. In particular, we show that it is equivalent to testing whether a differential polynomial is a zero divisor modulo a radical differential ideal. The technique used in the proof of this equivalence yields algorithms for computing a canonical decomposition of a radical differential ideal into prime components and a canonical generating set of a radical differential ideal. Both proposed representations of a radical differential ideal are independent of the given set of generators and can be made independent of the ranking.     

On Integral Representation Formulae for Biharmonic Functions on the Ball

Biharmonic functions are solutions of the fourth order partial differential equation ΔΔu = 0. A simple method is proposed for deriving integral representation formulae for these functions u on the n‐dimensional ball. Poisson‐type representations in the setting of Hardy Spaces are obtained for biharmonic functions subject to Dirichlet, Riquier and other boundary conditions. The approach exploits algebraic properties of a first order partial differential operator and its resolvent.     

Generalized Sobolev's phi function for the resolvent of a Milne-type integral equation with a degenerate kernel

It is well known in the field of radiative transfer that Sobolev was the first to introduce the resolvent into Milne's integral equation with a displacement kernel. Thereafter it was shown that the resolvent plays an important role in the theory of formation of spectral lines. In the theory of line-transfer problems, the kernel representation in Milne's integral equation has been used to provide an approximate solution in a manner similar to that given by the discrete ordinales method.In this paper, by means of invariant imbedding we show how to determine an exact solution of a Milne-type integral equation with a degenerate kernel, whose form is more general than the Pincherle-Gourast kernel. A Cauchy system for the resolvent is expressed in terms of generalized Sobolev's Φ- and Ψ-functions, which are computed by solving a system of differential equations for auxiliary functions. Furthermore, these functions are expressed in terms of components of the kernel representation.     

Operator kernel estimates for functions of generalized Schrödinger operators

We study the decay at large distances of operator kernels of functions of generalized Schrödinger operators, a class of semibounded second order partial differential operators of mathematical physics, which includes the Schrödinger operator, the magnetic Schrödinger operator, and the classical wave operators (i.e., acoustic operator, Maxwell operator, and other second order partial differential operators associated with classical wave equations). We derive an improved Combes-Thomas estimate, obtaining an explicit lower bound on the rate of exponential decay of the operator kernel of the resolvent. We prove that for slowly decreasing smooth functions the operator kernels decay faster than any polynomial.

     

Primary decomposition of modules: A computational differential approach

We study primary submodules and primary decompositions from a differential and computational point of view. Our main theoretical contribution is a general structure theory and a representation theorem for primary submodules of an arbitrary finitely generated module over a polynomial ring. We characterize primary submodules in terms of differential operators and punctual Quot schemes. Moreover, we introduce and implement an algorithm that computes a minimal differential primary decomposition for a module.     

Centers of quasi-homogeneous polynomial differential equations of degree three

We characterize the centers of the quasi-homogeneous planar polynomial differential systems of degree three. Such systems do not admit isochronous centers. At most one limit cycle can bifurcate from the periodic orbits of a center of a cubic homogeneous polynomial system using the averaging theory of first order.     

Positively finitely related profinite groups

We define and study the class of positively finitely related (PFR) profinite groups. Positive finite relatedness is a probabilistic property of profinite groups which provides a first step to defining higher finiteness properties of profinite groups which generalize the positively finitely generated groups introduced by Avinoam Mann. We prove many asymptotic characterisations of PFR groups, for instance we show the following: a finitely presented profinite group is PFR if and only if it has at most exponential representation growth, uniformly over finite fields (in other words: the completed group algebra has polynomial maximal ideal growth). From these characterisations we deduce several structural results on PFR profinite groups.     

倒向随机方程期权定价模型的一类随机算法

期权定价问题可以转化为对倒向随机微分方程的求解,进而转化为对相应抛物型偏微分方程的求解.为了求解与倒向随机微分方程相应的二阶拟线性抛物型微分方程初值问题,引入一类新的随机算法-分层方法取代传统的确定性数值算法.这种数值方法理论上是通过弱显式欧拉法,离散其相应随机系统解的概率表示而得到.该随机算法的收敛性在文中得到证明,其稳定性是自然的.并构造了易于数值实现的基于插值的算法,实证研究说明这种算法能很好地提供期权定价模型的数值模拟.     

Branching diffusion representation of semi-linear elliptic PDEs and estimation using Monte Carlo method

We study semi-linear elliptic PDEs with polynomial non-linearity in bounded domains and provide a probabilistic representation of their solution using branching diffusion processes. When the non-linearity involves the unknown function but not its derivatives, we extend previous results in the literature by showing that our probabilistic representation provides a solution to the PDE without assuming its existence. In the general case, we derive a new representation of the solution by using marked branching diffusion processes and automatic differentiation formulas to account for the non-linear gradient term. We consider several examples and estimate their solution by using the Monte Carlo method.     

On the Complexity Exponent of Polynomial System Solving

Foundations of Computational Mathematics - We present a probabilistic Las Vegas algorithm for solving sufficiently generic square polynomial systems over finite fields. We achieve a nearly...     

Arc Length Estimation and the Convergence of Polynomial Curve Interpolation

When fitting parametric polynomial curves to sequences of points or derivatives we have to choose suitable parameter values at the interpolation points. This paper investigates the effect of the parameterization on the approximation order of the interpolation. We show that chord length parameter values yield full approximation order when the polynomial degree is at most three. We obtain full approximation order for arbitrary degree by developing an algorithm which generates more and more accurate approximations to arc length: the lengths of the segments of an interpolant of one degree provide parameter intervals for interpolants of degree two higher. The algorithm can also be used to estimate the length of a curve and its arc-length derivatives. AMS subject classification (2000) 65D05, 65D10     

On the resolvent of linear nonautonomous partial functional differential equations

We give sufficient conditions for the existence of the resolvent operator for nonautonomous linear partial differential equations with delay, where the highest order derivatives are undelayed. Furthermore we analyse the connection between the resolvent and the solution operator of the homogeneous equation.     

Applying sieving to the computation of quadratic class groups

We present a new algorithm for computing the ideal class group of an imaginary quadratic order which is based on the multiple polynomial version of the quadratic sieve factoring algorithm. Although no formal analysis is given, we conjecture that our algorithm has sub-exponential complexity, and computational experience shows that it is significantly faster in practice than existing algorithms.

     

General polynomial roots and their multiplicities in O(N)memory and O(N2)Time

For a given real or complex polynomial p of degree n we modify the Euclidean algorithm to find a general tridiagonal matrix representation T of the monic version of p and then use the tridiagonal DQR eigenvalue algorithm on T in order to find

all roots ofp with their multiplicities in O(n²) operations

and 0(n) storage. We include details of the implementation and comparisons with several, standard and recent, essentially 0(n³) polynomial root finders.