修士論文 要旨

漸化式を用いた多面体上の格子点の数え上げ
数理情報学専攻 48206233
指導教員ある多面体上の格子点の集合は、行列 A ∈ Z
ベクトル b ∈ Zを用いて、{y ∈,= b} と表される。この集合の要素数を計算することは整数計

基底性より、∂i sj =
s1 ◦ fs1 ◦ f



..
..
∂i 
 = Qi .
.
sm ◦ fsm ◦ f

ラフの接続行列、b を全成分 1 のベクトルとすると、となるが、完全マッチングの数え上げは、二部グラフの場合でも、パーマネントの計算であり、P̸=NP の下で多項式時間で計算することはできない。

k=1 gijk (x)sk が成立する。ここ各成分が C(x1 , . . . , xn ) の行列 Qi を用いて、マッチングの数え上げなどを含む。例えば、A をグ|{y ∈ Zm
≥0 |Ay = b}| はグラフの完全マッチングの個数∑mで gijk (x) は C 係数の n 変数有理関数である。よって、

画問題の解の個数の数え上げに等しく、グラフの完全となる。この偏微分方程式系を Pfaﬃan 方程式系という。
これを用いて、数値的に f を計算できる。本研究でこの問題は、素朴な動的計画法を用いて、時間計算n平井広志 准教授

クトル空間をなす場合、基底 s1 = 1, . . . , sm がとれて、n×m

Zm≥0 |Ay祐樹

り、このイデアルを I とする。R/I が有理関数係数のベ1 多面体上の格子点の数え上げ
n松下nは、この手法を離散的な場合に適用して漸化式を得る。

量 O(m(||b||∞ + 1) ), 空間計算量 O((||b||∞ + 1) ) で+Zn 上の関数 f に対し、差分作用素 ∆+i を ∆i f (b) =計算できる。Barvinok[1] は m を固定したときの効率f (b + ei ) と定める。ここで ei は第 i 成分が 1 で他が的なアルゴリズムを与えている。Lasserre-Zeron[2] は、0 の整数ベクトルである。Pfaﬃan 方程式系は微分方程A が非負のケースで、次のような母関数を用いる手法

式系であるが、Zeilberger の方法 [5] で、差分方程式系を考案した。

を得ることができ、それが f を計算するための漸化式

補題 1 ([2]). 非負行列 A ∈ Zn×m
≥0 , 整数ベクトル b ∈になる。以上をまとめたのが、次のアルゴリズムである

Zn≥0 に対し、f (b) = {y ∈ Zm
≥0 |Ay = b} と定める。
∑ẑ(f ) = b∈Zn f (b)xb とすると、≥0ẑ(f ) =1(1 − xA1 ) · · · (1 − xAm )である。ただし、Ai は A の i 列目の列ベクトルを表し、c ∈ Zn に対し、xc = xc11 . . . xcnn と表記する。
母関数による手法は、最新の研究 [3] でも用いられ、時間計算量 O(poly(n, m, ||b||∞ )n(||b||∞ + 1) ), 空間計算量 O(poly(n, m, ||b||∞ )) を達成している。

2 漸化式による手法
計算の困難な関数に対して、その関数の偏微分方程式系から、数値的に計算するホロノミック勾配法という手法がある [4]。具体的には、多変数関数 f (x1 , . . . , xn )に対して、次のようなことを考える。
定義 2 (Pfaﬃan 方程式系). 有理係数の多項式環 R =[6]。
多面体上の格子点数え上げアルゴリズム

n入力:非負行列 A ∈ Zn×m
≥0 , ベクトル b ∈ Z

出力:f (b) = |{y ∈ Zm
≥0 |Ay = b}|1⃝ẑ(f) を解に持つ微分方程式を計算する
2⃝fを解に持つ差分方程式を計算する。
3⃝fに関する Pfaﬃan 方程式を計算する。
4 必要な初期値を計算し、f の値を計算する。
⃝

上記のアルゴリズムにおいて、微分方程式や微分方程式の集合は、微分作用素や差分作用素の入った環のイデアルをなしており、グレブナー基底を用いて計算できる。
この方法は、多面体上の格子点の数え上げに対して、新規的な手法であり、興味深いが、計算過程でグレブナー基底を用いるために計算量解析が困難になる。また、負成分を含む行列への拡張や、実装が行われていないなどの様々な課題が残されている。

3 成果 1: n = 1 の計算量解析

C(x1 , . . . , xn )[∂1 , . . . , ∂n ] を定める。R の元で、f を解

本研究では、n = 1 の場合に、グレブナー基底を用いに持つ微分方程式全体の集合は、R の左イデアルであない方法を考案することで、Hirai 19[6] の手法に上から漸化式を用いた多面体上の格子点の数え上げ (松下 祐樹)の計算量評価を与えることに成功した。なお、n = 1 の場合に、A ∈ Zm , b ∈ Z が与えられ、{x ∈ Zm
≥0 |Ax = b}を計算する問題は、ナップサックの制約に対応する。
補題 3. ẑ(f ) =∏mi=1 (1 − x∏m1i=1 (1−xAi ) とする。ここで、g(x) =Ai) とおくと、()∂′
g(x)+ g (x) ◦ ẑ(f ) = 0∂x

図 1. A の点が貼る錐

図 2. 錐と新しい座標が成立する。また、この微分方程式から、先行研究 [6]こで、図 2 のように、超平面を用いて新たな座標軸をの方法で、差分方程式を計算すると、定義してやると、各点を非負にできる。代数的には、m∏可逆な行列 B で、BA ∈ Rn×mとなるような B を≥0(1 − ∆−Ai ) ◦ f = 0かけることに等しい。また、可逆な行列 B に対し、

i=1

Ax = b ⇔ BAx = Bb が成立するので、入力 (A, b) にという差分方程式が得られる。

対し、このような B を構築して、(BA, Bb) に対して、
実は、この差分方程式は、包除原理を用いて、f を計算する場合の漸化式となる。gcd(g(x), g ′ (x)) で割ったアルゴリズムを適用することで、負成分を含む行列にアルゴリズムを拡張に成功した。

あとの微分方程式から差分方程式を計算すると、より最大項の小さい漸化式が得られる。その漸化式を用いると、次の定理が得られる。

5 成果 3: 特異点の発見
本研究では、先行研究 [6] の手法を実装することで、定理 4. 多項式 h(x) = gcd(g(x), g′ (x)), 集合 S = {d ∈漸化式の遷移が上手く行かない点が発生することを発g(x) ∂N|d を約数に持つ ai が存在する } と す る 。 h(x)∂x +見した。これは、漸化式を導出する段階で、有理関数係

g ′ (x)h(x)と い う 微 分 方 程 式 を 用 い て 、漸 化 式 を 構 成 する と 、そ の 漸 化 式 の 次 数 は∑d∈S ϕ(d) で あ る 。た数の環のグレブナー基底に関する演算を行うが、分母が0 となるような点を代入してしまうと、計算が正しくなだし、ϕ はオイラートーシェント関数を表す。このらない。逆に、そのような点を経由しなければ正しく演漸化式をもとに、f (b) を計算した場合、時間計算量算が行えることを示した。そして、係数付きの漸化式をO((b + m)構成することも提案している。

∑d∈S ϕ(d)), 空間計算量 O(∑d∈S ϕ(d)) を達成する。
先行研究 [6] ではグレブナー基底を用いるために、計算量解析が困難であったが、定理 1 の方法で導出した漸化式より、最大項の小さいものが得られることが示せるので、上からの計算量評価が可能となる。

4 成果 2: 負成分を含む行列への対応
定義 5 (端点を有する多面体). {x ∈ Rm
≥0 |Ax = 0} ={0} なる多面体を端点を有する多面体と定める。
行列 A が非負なら、多面体 {x ∈ Rm |Ax = b} は端点を有する多面体である。A に負の成分を含む場合でも、多面体が端点を有することもある。本研究では、行列 A ∈ Rn×m が {x ∈ Rm
≥0 |Ax = 0} = {0} を満たすときに非負に変換するアルゴリズムを考案した。アルゴリズムのアイデアは次のようなものである。
まず、{x ∈ Rm
≥0 |Ax = 0} = {0} となる場合に、{Ax|x ∈ Rn≥0 } を図示すると図 1 のようになる。こ参考文献[1] A.I.Barvinok, Polynomial time algorithm for counting
integral points in polyhedra when the dimension isfixed. Math. Oper. Res., Vol. 19(1994), 769–779.
[2] J.B.Lasserre and E.S.Zeron, On counting integral
points in a convex rational polytope. Math. Oper.
Res., Vol. 28(2003), 853–870.
[3] H.Hirai, R.Oshiro and K.Tanaka, Counting integral
points in polytopes via numerical analysis of contour
integration. Math. Oper. Res., Vol. 45(2020), 455–464.
[4] H.Nakayama, K.Nishiyama, M.Noro, K.Ohara, T.Sei,
N.Takayama and A.Takemura, Holonomic gradientdescent and its application to Fisher-Bingham integral. Adv. Appl. Math., Vol. 47(2011), 639–658.
[5] D.Zeilberger, A holonomic systems approach to special functions identities. J. Comput. Appl. Math., Vol.
32(1990), 321–368.
[6] 平井広志 “漸化式に基づく多面体内の格子点の数え上げについて”, 応用数理学会研究部会連合発表会, 筑波大学, つ
くば市 2019 年 3 月