JAIST Repository
https://dspace.jaist.ac.jp/

Title

ヘテロな分散システムの負荷均一化の最適解

Author(s)林, 幸雄

Citation

電子情報通信学会論文誌 A, J86‑A(10): 1075‑1081

Issue Date

2003‑10‑01

Type

Journal Article

Text version

publisher

URL

http://hdl.handle.net/10119/4730

RightsCopyright (C)2003 IEICE. 林 幸雄, 電子情報通信学会論文誌 A, J86‑A(10), 2003, 1075‑1081.
http://www.ieice.org/jpn/trans̲online/

Description

Japan Advanced Institute of Science and Technology

復計算によって各辺（ 通信路）上の負荷移動量を求め
ヘテロな分散システムの負荷均一化の最適解
幸雄†a)（ 正員）林

た後に，実際の負荷移動を行う．DF 法は本質的には拡散方程式を反復的に解いて負荷移動量を求める手法で，

Optimal Solutions of the Load Balancing in Heterogeneous

無駄な巡回フローをもたない最適解を与えること [5]Distributed Systems
Yukio HAYASHI† a) , Regular Member

が知られている．しかしながら，単純な時間差分によ†

北陸先端科学技術大学院大学 知識科学研究科，石川県

School of Knowledge Science, Japan Advanced Institute of
Science and Technology, Ishikawa-ken, 923–1292 Japana) E-mail: yhayashi@jaist.ac.jp

る方法では収束が遅いため，高速化のための種々のスキームが考えられている．特に最近，一般の結合構造に対して多項式を用いた OPS（ Optimal Polynomial

Scheme ）と呼ばれる手法が提案された [6]．この手法
では，拡散方程式における離散ラプラシアンの固有値

あらまし

サーバ性能が異なるヘテロな分散システ

でパラメータを設定すると，有限（ 相異なる固有値のムの負荷均一化において，その最適解が手法によらず

数 −1 ）回の反復で収束することが保証される．また，

初期負荷配分で決まること，通信相手の性能を隠蔽した上で均一化できること，及び ，ある保存則に従って従来の FOS（ First Order Scheme ），SOS（ Second
Order Scheme ），Chebyshev Scheme などを特殊形と収束することを示す．

して含んだ一般化された手法である [6] とともに，並キーワード

拡散法，拘束力学系，GRID

列計算機に適したグラフのデカルト積の構造にも適用

1. ま え が きできる [7]．更に DF 法は，サーバやプロセッサの性能

広域ネットワーク上の分散コンピューティングが近が異なるヘテロな場合にも拡張されている [8] が，性年注目を集めている [1], [2]．その重要課題の一つとし能の違いによって換算された負荷量は陽に扱われておて，動的でヘテロな分散システムの負荷均一化問題がらず，均一化のために移動すべきプロセス数と混同さある．並列計算機や分散システムにおいてできるだけれている．

少ない通信回数や通信量で，できるだけ素早く負荷の本論文では，ヘテロな分散システムの負荷均一化を均一化が行えるよう，様々なアルゴ リズムがこれまで考え，先の文献 [8] の問題点をふまえたうえで，計算提案されてきた．例えば ，あるしきい値より負荷量が手法及び スキームや実装技術に依存しない，最適解の少なくなった時点で自分の近傍に催促する Receiver

性質を明らかにする．

Initiation や，逆にしきい値より多くなった時点で負2. 負荷均一化問題

荷の移動先を探す Sender Initiation が知られている．

サーバ（ 一般に 計算機をさす ）性能が 異なるヘテ

これらは，処理が単純であることから用いられている

ロな分散システムの負荷均一化問題を考える．まず，が，しきい値の設定が難しいのに加えて，大域的な均サーバ間のネットワークは，有限連結で自己ループや一化が保証されず場当り的で [3]，場合によっては負荷

多重辺のないグラフ (V, E) において，頂点と辺の重の出戻りが起こりうる．あらかじめ負荷移動先の順番みをもつものとする．ここで，用語の定義を行う．

を定めた Round-Robin 法やランダムに移動先を選択する方法など も，同様に均一化の精度よりも処理の単純さを重視したものである．

性能：各頂点上のサーバ u ∈ V の性能を重み mV (u)で表し ，プロセスの処理スピード で定義する．
コスト ：辺 e = (u, v) ∈ E の重み mE (e) はコス

一方，無駄な負荷移動をさけるため，移動すべき最トの逆数を表し，サーバ u,v 間の通信速度などで定義

適な負荷量の計算と，負荷の移動という 2 フェーズにする．インターネット環境では，速度が変動して値が基づく方法が考えられている．その最もよく知られた

定まらないと考えられるので，通信遅れの偏差などに手法として，次元交換（ DE： Dimension Exchange ）よる通信の不安定度でコストを定義する [9]．ただし ，法と拡散（ DF：Diﬀusion ）法がある [4]．DE 法は，規重みの意味が変れば ，後述する最適化の評価尺度が変則的な結合構造をもつ超並列計算機に適し ，一時刻にわる．

各プ ロセッサが 単一の通信ポートを介して一斉に右，

負荷量：各サーバ u ∈ V の負荷量を f (u) で表す．

左，上，下へといった具合いに交互に隣接プロセッサ

負荷量は，サーバが保持する未処理なプロセスの数を，と均一化を図る手法である．これに対して DF 法は，性能 mV (u) で割って換算した量で定義する．

非同期，マルチポートに適し ，局所的な拡散による反電子情報通信学会論文誌 A Vol. J86–A

本論文では，GRID 向けの課題 [1] を想定している
No. 10 pp. 1075–1081 2003 年 10 月

1075

電子情報通信学会論文誌 2003/10 Vol. J86–A No. 10ので，多数の独立した同程度のプロセスが存在するも一化されるのは性能で換算された負荷量 p(u)/mV (u)のとして，負荷量は任意に分割可能とする [4], [6], [7]．

であって，p(u) は性能に従って比例配分されたプロセ

3. ヘテロなネット ワークに対する作用素
3. 1 従来の離散ラプラシアン
従来の重み付き離散ラプラシアン [10], [11] は，負荷ス数と解釈すると矛盾がなくなる．

3. 2 非対称な新しい作用素
本節では，サーバ性能の違いによって辺の両端で重量ベクトル f = (f (1), . . . , f (u), . . . , f (|V |))T に作

み値が異なることから非対称行列となる，離散ラプラ用させたその u 成分表示で，シアン L を以下に提示する．これは，付録に示した

def

Lf (u) = −XmE (e) (f (v) − f (u)) ,

(1)

v∼u

作用素式 (A·1) の離散版に相当する（注 1 ）．
def

Lf (u) = −と定義される．ここで，v ∼ u は u の隣接点 v の集−
(2)の時間発展は総負荷量
解 Ave =

Pさせながら 収束することが 知られている（ 表記の混乱をさけるため，f (u) が時間 t の関数であることは省略）．
負荷均一化の意味としては，式 (2) 右辺，すなわち
式 (1) によって，各頂点 u のサーバが隣接点 v との負荷量の差に従って移動すべき量を求める点が本質的である．
一方，サーバ性能の違いを重み mV (u) で表現した
離散ラプラシアン Lc による拡散方程式，

XmE (e)

v∼u

(6)

X

g ii (v) (f (v) − f (u)) ,(7)

ここで，E は両方向のすべての有向辺の集合，有向辺

ei : u → v, ēi : v → u はその逆向辺，辺 ei の両端
defu, v における重みの差分，∆g ii (u) = g ii (v)−g ii (u) =|0, i ∈ {1, 2, . . . , |E|} とする．L の行列表現は，

2
...
...
6
.
..
6
..
.
6
6
def 6
L = 6−g ii (1)
0
6
6
..
6 ..
.
4 .
...

−g ii (u)

P

0

v∼u g

ii

(v)

..
.
...

...
..
.
..
.
..
.
...

3

...
.. 7
7
. 7
7
.. 7
,
. 7
7
7
.. 7
. 5
...

(3)

p(u)
p(v)
−
mV (v)mV (u)

となる．

,

この作用素 L による拡散処理では，各辺上の負荷
移動の出入り量が一致しない．すなわち，各辺 ei の(4)

両端 u, v での負荷の出入り量が，式 (7) より，

u に対して −g ii (v)(f (v) − f (u))

も考えられている．
文 献 [8] で は ，p(u) は 負 荷 量と 定 義 され て い る
が ，こ れ はプ ロ セ ス 数と 考え るの が 妥 当で あ る ．
な ぜ な ら ，∀u ∈ V, v ∼ u に 対 す る ，平 衡 条 件

p̄(v)/mV (v) = p̄(u)/mV (u) より，拡散方 程式 (3)の解は，∆g ii (u)(f (v) − f (u)),

X

v∼u∈E

...

∂p(u)
= −Lc p(u),
∂t
def

=−

u∈V f (u) を保存して，均一u∈V f (u)/|V | との二乗誤差を単調減少

Lc p(u) = −

(5)

v∼u∈E

∂f (u)= −Lf (u),∂tPg ii (u)(f (v) − f (u))

v∼u∈E

合を表す．また，L による拡散方程式

defXv に対して −g ii (u)(f (u) − f (v))
と異なる点が特徴的である（ 移動方向を表す符号の違いを除いても g ii (u) =| g ii (v) なので，上記の量は不一致）．このことは，L が非対称行列で表されることによるもので，次章で述べる総負荷量の時間的変動にXも関係する．ここで，各辺の両端の頂点における負荷

p(v)

v∈V

p̄(u) = XmV (v)の出入り量が一致しないことは，それぞれ異なる性能

mV (u),

v∈Vとなり，異なる性能 mV (u) =| mV (v) であることかで換算される評価量であることによるもので，それらに相当する物理量であるプロセス数の出入り量は一致（ 注 1）：直観的には，各頂点上のサーバ性能の違いが ，多様体の各点における計ら，この p̄(u) は各頂点 u ∈ V ごとに別々の値をとる量（ 距離尺度）の違いに対応付けられる．ただし，連続版式 (A·1) と離散版式

が，これは明らかに不均一を意味する．したがって，均で両者ともに自己共役（ 対称な形式）となることに基づく．

1076(7) の対応付けは，差分近似というより，定理 1 のグリーンの公式 (11)，(12)

レ

タ

ー

していることに注意しよう（ Lc が L に帰着する後述

以上の議論から，⇔ を同値，← を対称な場合の限の結果から確かめられる）．
一方，従来の L と Lc では，式 (1) と式 (4) の右辺における各辺の両端の頂点での出入り量は等しくなる．
このことは，それぞれ総負荷量とプロセス総数が均一化処理の各時刻で変動せず保存されることを意味する．
さて，式 (7) は，

g ii (v) =mE (ei )> 0,
mV (u)diag(mV (u)) である．
定と表記すれば ，L ← ∆P ⇔ L,となり，これまで提案された離散ラプラシアンとの関係が整理できる．

(8)と表現すれば ，以下の調和振動子のばねモデル [12] に
一致する．

X
1
∆P f (u) = −mE (ei )(f (v) − f (u)),
mV (u) v∼udef(9)
ただし ，異なる質量 mV (u) =| mV (v) > 0，ばね定数mE (ei ) = mE (ēi ) > 0 と定義されている．したがって，負荷均一化のための拡散とばねモデルという応用

更に，式 (7) の L 及び連続版 (A·1) に対して，以下の基本定理が成り立つ（ 証明は付録に示す）．
［ 定理 1 ］ グリーンの公式

Z

M

Lf1 f2 dx =M

M提案した作用素 L と等価な式 (9) の表現から，負f1 Lf2 dx,(df1 , df2 )G = (Lf1 , f2 )G = (f1 , Lf2 )G ,
(12)
X
def 1
df1 (ei )df2 (ei )mE (ei ), (13)(df1 , df2 )G =2 e ,ēidef(Lf1 , f2 )G =Xi

Lf1 (u)f2 (u)mV (u),

(14)

u∈V
def

荷均一化のための拡散処理において，各サーバ u ∈ VZ(df1 , df2 )G dx =(11)上の意味付けから離れれば ，作用素として L は ∆Pと等価になる（ 注 2 ）．

Z

def

df1 (ei ) = f1 (v) − f1 (u)，df2 (ei ) = f2 (v) − f2 (u)．
［ 定理 2 ］ 最大最小の原理
境界条件のない有限な連結無向グラフ (V, E) におは通信相手となる隣接サーバ v ∼ u の負荷量 f (v)いて，∀u ∈ V, Lf (u) = 0 を満たす L-調和関数 f (u)と自分自身の性能 mV (u) を知るだけでよく，従来のは定数である．

Lc による式 (3)，(4) のように相手の性能 mV (v) を知る必要がない．通信相手の性能を隠蔽して負荷均一化が 行えることは ，必要最低限の情報開示のみで処理が行えることを意味するもので，ボランティアコン
ピューティング 的な GRID [1] にふさわし い．また ，各頂点 u ∈ V における性能と負荷量の積がプロセス数なので，mV (u)f (u) = p(u),4. 最適な負荷均一解の性質
本章では，L による拡散方程式∂f (u)= −Lf (u),
∂t

(15)

を考え，その時間発展の力学系としての特性を明らかにする．特に，DF 法はある二次計画（ QP ）問題を解くことと等価で最適な負荷均一解を与えること [5], [6](10)とすれば ，式 (4) は式 (9) 及び 式 (8) を伴う式 (7) に帰着する．よって，文献 [8] における p(u) をプ ロセス数と解釈することに一貫した意味を与えることができる．
一方，前節の式 (1) による重み付き離散ラプラシア
ン L は ，サーバ性能がすべて同一な場合 mV (u) =mV (v) に相当する，g ii (v) = g ii (u) のときに限られる．また，行列表現でから，以下に示す「初期負荷配分に依存した総負荷量の変化」は手法によらず，性能が異なるヘテロな分散システムの負荷均一化に本質的なものとなる．すなわ
ち，その最適な負荷均一解で以下の現象は必ず起こる．

4. 1 保存則と収束性
まず定理 1 において，∀u ∈ V, f2 (u) = const. を考えれば df2 (u) = 0 になることから，以下の定理を得る．ただし ，f 0 = (f 0 (1), . . . , f 0 (u), . . . , f 0 (|V |))T
は初期負荷量ベクトルとする．
（ 注 2）：式 (8) から，∆P は L に帰着する．逆に，後述する定理 3 の保存則Tii∀f , mT
V Lf = 0 ⇔ L mV = 0 を満たす L における g (u) から，

CL = Lc C = L,def

が 成り立つ ．ここで ，|V | × |V | の 対 角行列 C =mV (u) の一意存在性を示すこともでき，離散版の L から ∆P への一意な変換式 (8) も成り立つ．

1077

電子情報通信学会論文誌 2003/10 Vol. J86–A No. 10［ 定理 3 ］ 重み付き総負荷量の保存

ここで，B は |V | × |E| の接続行列（各要素は，辺 ei

拡散方程式 (15) は重み付き総負荷量を保存する．すが入る頂点：−1，出る頂点：+1 ），W = diag(mE (e))，

p0 と p̄ はサーバ上のプロセスの初期配分ベクトルと解ベクトル，z 0 の各要素 ze i はプ ロセスのフロー量

なわち，∀t >= 0 で，−ZM

Lf (x) dx = 0,

XX
∂f (u)mV (u)×mV (u)×Lf (u) = 0,
=−
∂t
u∈V
u∈V
X

mV (u)×f 0 (u) =u∈VXmV (u)×f (u).

(16)

u∈V

この定理から，式 (10) に従ったプ ロセス総数に相P当する重み付き総負荷量 u∈V mV (u)f (u) は保存さPれるが，総負荷量自身の値

u∈V f (u) は変化し得る

ことがわかる（ 注 3 ）．
更に定理 1 において ∀u ∈ V , f1 (u) = f2 (u) とす

P

れば ，

u∈V Lf1 (u)f1 (u)mV (u) = 0 を得る．これ

>

より，

X

= −2

X

∂f (u)
∂t

u∈V f

min
s.t.

1 T −1z W z,
2
C −1 B z = f 0 − f¯,

(20)
(21)

に変換される．式 (10) によって Lc は L に帰着するので，QP 問題式 (20)，(21) を解くことは L による

DF 法と等価になる．
式 (21) は負荷均一化条件を表すが ，閉路上の無駄な巡回フロー（プロセスのたらい回し ）をもつ可能解ことを意味する．
関係式 (10) から，他の従来のスキームも負荷量に関するものに書換え可能である．例えば，m − 1 回のLf (u)f (u)mV (u) <= 0.

反復で収束を保証する，OPS より簡略化された OPT

すなわ ち，拡散方程式 (15) では ，平均初期負荷量Pdef(20) はネットワーク全体における通信コストを最小化

u∈V

Ave =

上記の QP 問題式 (18)，(19) は，その重み付きフ
ロー量ベクトル z = W 1/2 z 0 と関係式 (10) より，するフロー配分 z（ または z  = W −1/2 z ）を求める

mV (u)(Ave − f (u)) ×u∈Vに関する変数で，その正値が辺 ei の方向を表す．

も含むので，最小化式 (20) が必要となる．その際，式∂ X
mV (u)(Ave − f (u))2∂t u∈V=2

def0(u)/|V | と各時刻 t の負荷量 f (u) との差の重み付き二乗和を単調減少させながら解が収束する．
次に定理 2 より，拡散方程式 (15) は負荷を均一化する唯一の解X

mV (v)f (v)def v∈V¯X:
f (u) =mV (v)

const.,(17)（ OPTimal scheme ）は，



p = I−
k

1
λk+1

LC

−1



pk−1 ,と表される [8] ので，式 (10) と C −1 L = L より，


fk = I −

1
λk+1



L f k−1 ,となり，前述のように通信相手の性能を隠蔽したうえ
で負荷均一化が実行できる．ここで，pk と f k はそれv∈Vをもつことがわか る．もちろん ，平衡条件は ∀u ∈ぞれ k 回目の反復におけるプロセス数ベクトルと負荷

V, v ∼ u に 対し て ，f¯(u) = f¯(v) である ．L が(V, E) 上の作用素であるにもかかわらず，解 (17) と順に k = 1, . . . , m − 1 ），m はその個数である（ 事前

上記の単調減少性に関するマクロな量が，結合構造を表す辺 e ∈ E に無関係であることは注目に値する．
さて，最適な負荷均一解の性質を議論し よう．文献 [8] では，Lc による DF 法が以下の QP 問題を解く

量ベクトル，λk+1 は Lc の相異なる正の実固有値（昇にすべての固有値を計算しておく必要がある点は，これらスキームの問題なのでここでは議論しない）．

4. 2 DF 法の挙動
図 1 は 拡散方程式 (15) の軌跡と ，その総負荷量の 時 間 的変 化を 模 式的に 三 次 元空 間で 表 現し たもことと等価であることが示されている．

min

1 0T 0
z z,
2

(18)

（ 注 3）：負荷量はプ ロセス数を性能で割った値なので，例えば ，性能が 2 倍のs.t.

BW 1/2 z 0 = p0 − p̄,

(19)

れない．

1078

サーバにプロセスを移動すると，負荷量とし ては半分になり，総負荷量は保存さ

レ

タ

ー

最適基準に対しても，成り立つことを強調したい．
謝辞

付録に示した数学的な議論に対して有益な御指摘を頂きました，東北大学大学院理学研究科の砂田利一教授及び 情報科学研究科の浦川肇教授に感謝申し上げます．本研究の一部は，文部科学省科学研究費

13680404 の援助を受けている．
文

献

[1]

佐藤三久，“グローバルコンピューティングへの期待 [8],”[2]V.S. Sunderam and G.A. Geist, “Heterogeneous par-Computer Today, no.104, pp.65–71, 2001.
allel and distributed computing,” Parallel Comput.,vol.25, pp.1699–1721, 1999.
[3]

W. Shu and M.Y. Wu, “Runtime Incremental parallelscheduling on distributed memory computers,” IEEE
Trans. Parallel Distrib. Syst., vol.7, no.6, pp.637–649,

Fig. 1

図 1 拘束面上の軌跡
Trajectory on a constrained plain.

1996.
[4]

C. Xu and F.C.M. Lau, Load Balancing in Parallel
Computers -Theory and Practice-, Kluwer Academicのである．すなわち，頂点番号 u ∈ {1, 2, . . . , |V |}を 添字とみなし た |V | 次元の f -座標系を 力学系のPublishers, 1997.
[5]

rithm for dynamic load balancing,” Parallel Comput.,状 態 空 間とし て みれば ，総 負 荷 量が 保 存され るこ
とは 単体

P

u∈V f (u) = const.（ 図中の一点鎖線のvol.25, pp.417–444, 1999.
[6]

R. Diekmann, A. Frommer, and B. Monien, “Eﬃcient schemes for nearest neighbor load balancing,”

正三角形 ）上に軌跡が 拘束され ，重み付き総負荷量Pu∈V mV (u)f (u) が保存されることは，単体以外のY.F. Hu and R.J. Blake, “An improved diﬀusion algo-

Parallel Comput., vol.25, pp.789–812, 1999.
[7]

R. Elsässer, A. Frommer, B. Monien, and R. Preis,

ある超平面（ 図中の実線の三角形）上に拘束されるこ“Optimal and alternating-direction load balancingとを意味する．その際，離散ラプ ラシアン L が複素

schemes,” Euro-Par’99, LNCS, 1685, ed. P. Amestoy,

固有値をもてば振動現象が生じ ，その軌跡が単体より

et al., pp.280–290, 1999.
[8]

手前に出た図中の薄い影部分にあるときは総負荷量はbalancing schemes on heterogeneous networks,” Proc.

増加し，単体より奥の濃い影部分では減少することになる．総負荷量の時間的変化は，幾何学的にはこのよ

SPAA, pp.30–38, 2000.
[9]

in Proc. ICCS, LNCS, Springer, 2003.
[10]

F.R.K. Chung, Spectral Graph Theory, chapter 1,[11]

American Mathematical Society, 1994.
浦川 肇，ラプラス作用素とネットワーク，第 7 章，裳華

[12]

房，1996.
砂田利一，“離散スペクトル幾何学，” 数学のたのしみ，上

本論文では，ヘテロな分散システムの負荷均一化問
題を考え，計算手法及び スキームや実装技術に依存しない，最適解の性質を明らかにした．具体的には，以下の結果が得られた．

野健爾，志賀浩二，砂田利一編，no.12, pp.67–80, 日本
評論社，1999.

（ 1 ） サーバ性能が異なるヘテロな分散システムの負荷均一化に対する DF 法を，非対称行列で表される[13]（ 2 ） ヘテロな分散システムの負荷均一化における性質として，その最適解が総負荷量を保存しないこと，

Y. Hayashi, “A Laplacian suitable for diﬀusion
or delivery on heterogeneous structures,”

L で規定することで，通信相手の性能を隠蔽したうえ
で負荷均一化が実現できることを示した．

Y. Hayashi, “Eﬃcient load balancing by adaptive bypasses for the migration on the internet,” to appear

うに理解することができる．

5. む す び

R. Elsässer, B. Monien, and R. Preis, “Diﬀusive load

Proc.

ISITA/NOLTA, pp.351–354, 2002.
[14]

浦川 肇，変分法と調和写像，pp.68–72, 裳華房，1990.

付

録及び ，DF 法としての拡散処理が発散や周期解をもた付録 1. では，従来の Levi-Civita 接続の代わりに情ず，初期負荷配分に従ったある保存量をもって収束す

報幾何学の双対接続を用いたラプラシアン L [13] と，ること，が明らかになった．

その計量の偏微分 ∂i g ii (x) を辺 ei の両端点 u, v にお特にこれらは，様々な通信コストに基づく異なった

ける重みの差分 ∆g ii (u) に対応付けた離散ラプラシア1079電子情報通信学会論文誌 2003/10 Vol. J86–A No. 10

ン (7) に対して，定理 1 を証明する（ ∂i = ∂/∂xi ）．

と定義することができる [14]．ゆえに，上記の左辺に更に付録 2. では定理 2 を証明する．

相当する

def

1. 定理 1 の証明
コンパクト Riemann 多様体 M 上の C ∞ 関数 f (x)

Xn

X ij

∂i (g ij ∂j f1 f2 ) − ∂j (g ij f1 ∂i f2 )∂ 2 f (x)Lf (x) = −g (x) i j
∂x ∂x
ij

X

∂i g ik (x)ik∂i (g ij ∂j f1 f2 )dx は Ua の境界での値を代入したものとなるが，Ua 上のコンパクトな台の閉
包は Ua に含まれるので，これは 0 になる．

= − (Lf1 f2 − f1 Lf2 ) ,∂f (x)
.
∂xk

(A·1)

{1, . . . , n} である．
まず，式 (A·1) に対する定理 1 の連続版を証明する．
コンパクトな多様体 M 上の C ∞ 関数 f1 , f2 を考える（連続版についてのみ，以下の議論は i =| k, gij=| 0

に対して両辺の積分

X  ij

Xであることと，余境界作用素（ またはこう配と呼ばれ

i,j

X

i

{∂i g ij ∂j f1 f2i=+ g ij ∂i ∂j f1 f2p

あることから左辺は 0 になる．なぜなら，M はコン
パクトなので，その細分として局所有限開被覆がとれ，その座標近傍系 {(Ua , a); a ∈ A} に対して，（1） 0<= ϕa (x) <= 1, x ∈ M , a ∈ A，
（ 2 ） 各 a ∈ A に対し {x ∈ M ; ϕa (x) =| 0} の閉
包 supp(ϕ) が Ua に含まれる，a∈A ϕa (x) = 1，を満たす 1 の分割 {ϕa ; a ∈ A} が存在し，コンパクトdef

な台 supp(f ) = {x ∈ M ; f (x) =| 0} の閉包がコンパクトである M 上の関数 f (x) の積分

1080

ϕa (x)f (x)dx =

XZ
a∈A

Ua

ンの公式 (12) が成立する．f1 と f2 を左右入れ換えても同様である [QED]．

det(gij )dx に固執せず， M dx を両辺に施すと，M がコンパクトでP(f1 (u) − f1 (v))f2 (u)mE (ei ).

v∼u

ゆえに，グラフ上の作用素式 (7) について，グリー= −(Lf1 f2 − (df1 , df2 )G ),（ 3 ） 各点 x ∈ M で，

i

XX
u

+ g ij ∂j f1 ∂i f2 },

R

i

1 X
=
(f1 (u) − f 1(v))(f2 (u) − f2 (v))mE (ei )2 e ,ē

i,jとなる．通常の体積に関する測度(f1 (u) − f1 (v))f2 (u)mE (ei ).

v∼u

1 X
df1 (ei )df2 (ei )mE (ei )2 e ,ēる）df の内積の定義より，

M a∈A

XX

えていることから，

i,j

Z X

Lf1 (u)f2 (u)mV (u)u

一方，(13) の右辺において，ei と ēi で辺を二重に考g ∂i ∂j f + ∂i g ij ∂j f ,∂i (g ij ∂j f1 f2 ) =dx をとると，左辺は 0 にな

次に離散版について考える．式 (7) と式 (9) の対応

=



M

付けから，式 (14) の右辺は，

u

式 (A·1) が，Rる．よって，式 (11) が成り立つ．

の場合でも成立するので一般形で書く）
．

X

o

i,j

ここで，[g ij ] は Riemann 計量 [gij ] の逆行列，i, j, k ∈Lf = −

M

同様に，と，以下の作用素 L を考える．

−

R

R

M

f (x)dx を，

ϕa (x)f (x)dx,

2. 定理 2 の証明
V 中で f (u) が最大値と仮定する（ 最小値でも以下同様）．また，この頂点 u の隣接点 v ∼ u における最def
大値を f (v  ) とし ，w(u, v) = g ii (v) と表記する．
L-調和関数は，w(u, v) > 0, ∀u ∈ V に対して，−

Xw(u, v)(f (v) − f (u)) = 0 ⇔v∼uf (u) = X

1

X

w(u, v)f (v),w(u, v) v∼uv∼uを満たすものであることから，

f (u) = X
v∼u

1

X

w(u, v) v∼uw(u, v)f (v)

レ

タ

ー

X

=

w(u, v)

<
= X

v∼u





f (v ) = f (v ),w(u, v)v∼uとなり，f (u) の最大値性の仮定により f (u) = f (v  )となる（ 不等号の場合は仮定に矛盾）．
一方，f (u) の最大値性と w(u, v) > 0 により，Lf (u) = −Xw(u, v)(f (v) − f (u))

Xw(v, v  )(f (v  ) − f (v)) >
= 0,

v∼v 

における和の各項が非負となるので，f (u) が L-調和
であるには，∀v ∼ u に対して，f (u) = f (v) = f (v  )でなければならない．グラフは連結なので隣接するすべての頂点でこれが成り立つ．ゆえに，f (u) は定数となる [QED]．
（ 平成 15 年 4 月 8 日受付，6 月 3 日最終原稿受付）v∼u1081