収束性の理論的解析

このように Bečka の動的順序は最⼤重みマッチングを使うことで局所的に最も良い並列ペアを選択 するが，そもそも最⼤重みマッチングをすることに意味があるのかどうか，それによって並列ペアを 選択するが，それがどれだけ良いものなのか，わかっていない．実際の計算では 2 つの近似（重みの 近似とマッチングに対する貪欲法）を⾏っているが，ここではそれらを無視して，正確な重みと正確 なマッチングを計算すると仮定した上で，最⼤重みマッチングが収束性にどれだけ影響を与えるのか を検証する．

3 章の通り，⾏列𝐶のブロック要素𝐶 _, を消去したとき，𝐶の⾮対⾓ブロックのフロベニウスノル ムの⾃乗和が減少する．すなわち𝐶^{( )}を𝐶^{( )}に変換したとき，

𝐶^{( )} = 𝐶⁽_, ⁾ − 2 𝐶^{( )}, . (5.19)

そこで，全体の⾮対⾓ブロックのフロベニウスノルムの⾃乗和に対する消去したブロック要素のフロ ベニウスノルムの⾃乗の⽐を𝑟を

𝑟 ≡

𝐶^{( )},

∑ 𝐶⁽_, ⁾

(5.20)

と定義すると

𝐶^{( )} = (1 − 𝑟) 𝐶^{( )}_, . (5.21)

よって，𝑟の下限を求めることによって⼀次収束の係数1 − 𝑟の上限を求めることができる．

最⼤重みマッチングにおいて，⾮対⾓ブロックのフロベニウスノルムの⾃乗和は枝の重みの和の 2

倍2 ∑_{( , )∈} 𝑔̂_, に⼀致し，消去したブロック要素のフロベニウスノルムの⾃乗和は，マッチングにお

ける枝の重みの和の 2 倍2 ∑_{( , )∈} 𝑔̂_, に⼀致する．そこで，あるグラフ𝑋における枝の重み和𝑆(𝑋) を次のように定義する：

𝑆(𝑋) =

( , )∈

̂

𝑔_, . (5.22)

このときグラフ𝐺における最⼤重みマッチング𝑀 について𝑟 = 𝑆(𝑀 )/𝑆(𝐺)を計算することが 問題である．そこで以下の定理を証明する．

定理 5.3. グラフ𝐺の枝の重みは𝑔̂_, ≥ 0を満たし，𝐺の頂点数𝑤は偶数であると仮定する．𝑀 が グラフ𝐺における最⼤重みマッチングであるとき，

𝑟 =𝑆(𝑀 ) 𝑆(𝐺) ≥ 1

2𝑤 − 3. (5.23)

ただし𝑆(𝐺) = 0のときは𝑟 = 1と定義する．

証明. グラフ𝐺は不⾜する枝を重み零の枝で補い，完全グラフになっていると仮定する．この証明で は，貪欲法によって𝐺のマッチングを計算することによって厳密解の下限を求める．

いま頂点数𝑤 = 2のとき，𝑆(𝑀 ) = 𝑆(𝐺) = ̂𝑔 _, . よって𝑟 = 1 ≥ . 次に頂点数2から𝑤 − 2ま で上式が成り⽴つと仮定する．このとき頂点数𝑤のグラフ𝐺 に対して貪欲法によって重み最⼤の枝 を選択したとする．この枝を(𝑖, 𝑗)とし，残余グラフ𝐺 = 𝐺 \(𝑖, 𝑗)とおき，差グラフ𝐺 = 𝐺 − 𝐺̄ とおく．𝐺 は完全グラフであるため，𝐺̄ の枝数は2𝑤 − 3である．𝑔̂_, は𝐺 全体における最⼤重み の枝であるため，𝑔̂_, = 0の場合，𝑆(𝐺 ) = 0である．そうでない場合，𝑔̂_, は𝐺̄ における最⼤重みの 枝でもあるため，

̂

𝑔_,

𝑆( ̄𝐺 ) ≥ 1

2𝑤 − 3. (5.24)

. . . . . . .

convergencerate

Bečkaʼs ordering Blocked classical ordering

図5.19 Bečka の動的順序とブロック版古典的ヤコビ法の収束率の上限の⽐較

そこで ^{( ̄ )}

( ) = 𝑡とおいたとき，帰納法の仮定を⽤いると 𝑟 = 𝑡

2𝑤 − 3+ 1 − 𝑡

2𝑤 − 7. (5.25)

これは𝑡 = 1のとき最⼩値をとるため，𝑟 ≥ .

よって𝑟の下限を計算できた．またこの証明では貪欲法によって真の解の下限を得ているため，同 じ結果が貪欲法においても成り⽴つ．

この𝑟の下限は，並列化の効果を表している．並列化を⾏わない動的順序の場合，つまり，1 ステッ プごとにフロベニウスノルム最⼤の⾮対⾓ブロックを消去するブロック版古典的ヤコビ法における消 去ブロックの⽐は𝑟 =

( ) である．そこで両者を⽐較するため 1 巡回における収束率の極限を調 べると，Bečka のオーダリングの場合，

lim→ (1 − 𝑟) = e . (5.26)

⼀⽅，ブロック版古典的ヤコビ法の場合，

lim→ (1 − 𝑟 )

( )

= e . (5.27)

よって両者は反復数 2 倍分だけ異なることになる．⾔い換えると，それぞれにおける最悪のケース同

⼠を⽐較すると，Bečka の動的順序は相⼿の 2 倍の計算量になる代わりに並列化可能である．実際に は，𝑤が現実的に⼩さな数値である場合には収束率の差はもっと縮まる．図 5.19にそれぞれの 1 巡回 における収束率の上限を⽰しているが，𝑤が⼩さいところでは差が縮まっていることがわかる．