2-3 Numerical Analysis, HGM, HGD.
.

2-3 Numerical Analysis, HGM, HGD

2-3 Numerical Analysis of Pfaﬃan SystemLet f be a holonomic function annihilated by a holonomic ideal I .
Let S = {1, s2 , . . . , sr } be a basis of Rn /(Rn I ) regarded as a vector
space over C(x) (basis of standard monomials). Put
F = (f , s2 • f , . . . , sr • f )T . Then F satisﬁes the following Pfaﬃansystem.
∂F= Pi F , i = 1, . . . , n,∂xi
where Pi is an r × r square matrix whose entries are rationalfunctions.
When xi ’s are parametrized as xi = ai t + bi where ai , bi areconstants, F (at + b) = F (a1 t + b1 , . . . , an t ∑+ bn ) satisﬁes thedF
ordinary diﬀerential equation (ODE) dt = ( ni=1 Pi (at + b)ai ) F .
We can numerically solve it by the Runge-Kutta method when an
initial value of F is given.

2-3 Numerical Analysis, HGM, HGDThe Runge-Kutta method by an example

Exercise 2.3.1 Suppopse that the function F satisﬁes dF
dt = −F ,F (t+h)−F (t)dFF (0) = 1. Approximating dt (t) by
where h is a smallhF (t+h)−F (t)number, we have
= −F (t). Then, F (kh) will behapproximated by fk determined by
fk+1 − fk= −fk ,
hf0 = 1(ﬁrst order Runge-Kutta scheme). Solve this recurrence and provethat fk converges to exp(−t) when k → ∞ and h → 0 keeping thecondition kh = t.
Packages for RK GSL (Gnu Scientiﬁc Library), deSolve in R.

2-3 Numerical Analysis, HGM, HGD

HGM, HGD
We call the method of evaluating the normalizing constant by utilizing
holonomic ideals, Pfaﬃan systems and Runge-Kutta methods the holonomic
gradient method (HGM).
∂F
For F = (f , s2 • f , . . . , sr • f )T , we have ∂x= Pi F , i = 1, . . . , n. Then, thei
gradient of F and inparticular that of f can be expressed in terms of the valuesof Pi and F . The Hessian is equal to∂2F∂Pi= ∂j • (Pi F ) =F + Pi Pj F∂xi ∂xj
∂xj

(1)

Solving optimization problems by these gradient and Hessian is called theholonomic gradient descent (HGD). For example, Fisher’s maximal likelihoodQu(x,Tk )estimate of parameters x is the maximization problem of L(x) = N
k=1 z(x)where Ti ’s are given data. The gradient and Hessian of log L(x) is expressed interms of Pi , F (where f (x) = z(x), normalising constant of u) and u and thenthe gradient descent method works.
Note The gradient cannot be evaluated by the HGM on or near the singularlocus of the Pfaﬃan system.

2-3 Numerical Analysis, HGM, HGDExercise
Exercise 2.3.2 For u(θ, t) = exp(−t − θt 3 ), we deﬁne thenormalizing constant∫ +∞z(θ) =u(θ, t)dt.
0(1) By utilizing the diﬀerential equation(27θ3 ∂θ2 + 54θ2 ∂θ + 6θ + 1)z(θ) = 1,determine the value of z(θ) at θ = 4 from the valuesz(1) = 0.5688899, z 0 (1) = −0.1136692. Use a package for theRunge-Kutta method.
(2) Suppose that Tk are given N numbers. Put∏u(θ,Tk )L(θ) = N
k=1 z(θ) (likelihood function). Express (the gradient)d0dθ log L(θ) in terms of z(θ), z (θ) and the exponential function.
How do we maximize L to obtain the ﬁtting parameter θ for Tk ’s?
2-3 Numerical Analysis, HGM, HGD

Supplemental exercise
Exercise 2.3.3 For u(θ, t) = exp(θ1 t1 + θ2 t2 )δ(t12 + t22 − 1), wedeﬁne the normalizing constant∫∫z(θ) =u(θ, t)dt1 dt2 =exp(θ1 t1 + θ2 t2 )dH(t)R2S1where dH(t) = darg(t) is the Haar measure on the unit circle S 1 .
By utilizing the Pfaﬃan system()
01∂F= P1 F , P1 =,θ12
θ22 −θ12∂θ122
θ1 +θ2θ1 (θ12 +θ22 ))(θ20∂F
θ1= P2 F , P2 =θ1 θ2−2θ2∂θ2222
θ +θ
θ +θ2
1

2

12

where F = (z, ∂1 • z)T , ∂1 = ∂θ∂ 1 , determine the value of z(θ) at
θ = (7, 4) from the value F = (9.839989, 3.995237) at θ = (1, 1).
Use a package for the Runge-Kutta method.
2-3 Numerical Analysis, HGM, HGD

What we need to study to apply the HGM or the HGD.
1A Pfaﬃan system for the normalizing constant. It can beobtained by computer algebra algorithms, but interesting
problems are sometimes too large for general algorithms. We
derive it by hand or by specialized algorithms. (cf. Finding aMarkov basis by hand or by 4ti2.)

2A method to evaluate initial values of F . The numericalintegration may be slow or inaccurate.

3An eﬃcient numerical solver for a large scale ODE. Note The
holonomic rank gives the complexity to solve the ODE.

4The HGM or HGD for degenerate parameters. In other words,
we need to study a Pfaﬃan system when parameters are
restricted on singular locus. (The existence and algorithms
follow from the theory and algorithms for D-modules.).

.
2-3 Numerical Analysis, HGM, HGD