第２２回助教の会

本年度の最終回，第２２回助教の会では数理情報学第２研究室助教の小林佑輔さんに発表していただきました．発表タイトルは「制約付き２マッチング問題に対するアルゴリズム」ということで，最適化と離散構造に関するお話でした．

組合せ最適化の分野における代表的・古典的問題のひとつに「最大マッチング問題」があります．与えられたグラフにおいて頂点の重複がないように枝の本数を最大化する問題です．この問題の解ではひとつの頂点につながる枝は高々１本ですが，２本まで許すことにして枝数の最大化を考えるのが「最大2-マッチング問題」です．この問題の解はサイクルとパスの集まりになりますが，最大マッチング問題に帰着されることが知られているので計算は多項式時間でできます．さらに，「長さ$k$以下のサイクルは使わない」という制約を入れたものを「制約付き最大2-マッチング問題」と呼びます．禁止サイクル長$k$の値が変わることによって問題の難しさが大きく変わってくることが知られています．

最大マッチング問題では，各枝に重みを与えることにより重みの和の最大化を考えることもできます．制約付き最大2-マッチング問題で各枝に重みを与えたものを「制約付き最大2-マッチング問題（重み付き）」と呼ぶことにします．重み無しの場合と同様に，制約付き最大2-マッチング問題（重み付き）においても禁止サイクル長$k$を変えることで問題の難しさが変わることが知られています（図１）．

図１　先行研究

 
$k=3$である場合については，計算時間評価の境目に当たる問題になっており，一般に多項式時間で解けるかどうかは分かっていません．グラフの次数を3以下に限った場合にはHartvigsen-Li (2007)により問題が多項式時間で解かれることが示されていますが，提案されているアルゴリズムは単純ではありません．今回の小林さんの研究では，グラフの次数を3以下に限った場合を考え，問題の構造をうまく抽出して利用することにより単純な局所探索アルゴリズムを得ています（図２）．得られたアルゴリズムの正当性は，離散凸解析とグラフに関する考察から導かれます．

図２　研究成果

もう少し詳しく見てみます（図３）．まず，枝集合の次数列（枝集合が与えられ場合の各頂点の次数を並べたもの）に注目します．制約付き最大2-マッチング問題（重み付き）を直接解くのではなく，次数列ごとに枝の重みの和を最大化することを考えます．ここで重要なのは，

・次数列から対応する重みの最大和を求める関数は次数列に関してM凹関数である
・グラフの次数列が指定されれば重みの最大和は多項式時間で計算可能である

という２点です．後者により，局所探索が実行可能であることが分かります．次数列が与えられた場合の重みの最大和の計算可能性はグラフに関する考察から得られますが，その際にグラフの次数が3以下であることが効いてきます．さらに前者と離散凸解析の結果から，次数列に関する局所探索により制約付き最大2-マッチング問題（重み付き）が多項式時間で解けることが保証されます．

図３　提案アルゴリズム

今回の小林さんの発表は，「個別の問題における計算可能性・計算時間」というミクロな視点と「効率的な計算を可能にする離散構造」というマクロな視点とを組み合わせた研究についてでした．次数列を経由することで，考えていた問題の離散構造が分かりやすい形で現れ，局所探索という単純なアルゴリズムで問題が解けることが示されました．ミクロとマクロをつなぐ中間的な手段を経由することの「うまさ」，妙味が感じられる内容で，とても興味深いものでした．


数理５研助教 廣瀬善大

Jokyo20130218 from y-kobayashi

第２１回助教の会

第21回目となる今回の数理助教の会は、国立情報学研究所　ERATO特任研究員の前原貴憲 (まえはらたかのり)さんに「行列の同時ブロック対角化問題」について発表していただきました。
タイトルにある「行列の同時ブロック対角化問題」とは n次の実正方行列がN個与えられた下で、共通の直交行列Pをうまくとってできるだけ細かいブロック対角行列に変形するという問題です。

この問題は、古くは、結晶物理に出てくるハミルトニアンの一般的な形を考える際にWignerが考えていました。その後も、物理では群論的手法として抽象的な議論がされてきました。しかし、このような問題は、工学における半正定値計画や、信号処理における独立成分分析、最近では、動的ネットワークの安定性解析など、いたるところに現れてきます。後者では、規模の大きい行列を数値的に扱うことを想定した　うまい同時ブロック対角化が議論されています。

理論的には one-by-one method として二つの可換な対称行列の同時対角化の証明が100年以上も前から知られていました。しかし、このような素朴な方法は、巨大な行列に対して数値的に対角化を行う場合には、誤差に弱いことが知られていました。 Bunse-Gerstner, Byers, Mehrmann (1990)は最適化の枠組みで、このような問題を取り扱っています。（Jacobi-like method）その後、JADEとよばれる方法によって、複数の行列の同時ブロック対角化が提案されましたが、厳密にうまくいくことが証明されたわけではありません。うまくいかない例もつくられています。


一方で、前原さんの研究では、このような問題に対して、数学的にしっかりとした理論を用いて、アルゴリズムを提案しています。前原さんのアイディアの数学的な基礎は1905年のSchurの研究にまでさかのぼります。（いわゆるSchur の補題として知られる結果。）　行列の組によって生成される＊代数 (star algebra) の交換子代数を考え、その元をランダムに一つとってきて、対角化する行列を見つけるというものです。行列の組がもつ対称性に注目し、行列自身を群の（有限次元）表現とみなすことで、既約分解の一般論を適用します。このような発想によって、one-by-one method の拡張を得たのが前原さんの一連の研究結果です。

スライドに出てくるArtin-Wedderburnの構造定理は、かなり抽象的な代数の話題ですが、これらの結果をうまく現実的な問題に適用できることが素晴らしいと思いました。ランダム行列理論を用いた誤差評価などは、数値的に統計的推定を扱う際にも役立ちそうで興味深かったです。 Jacobson根基が残るケース（半単純代数でないケース）の分解については、まだできていないとの話でしたが、工学的な応用のみならず、統計物理でよく出てくるHeisenberg群などの例もあるので、今後に期待したい所です。

また、この助教の会のブログをいつもご覧になっている皆さんの中には、坂下達哉さんの発表(第12回 2012年1月)の際の密度行列のテンソル積の既約分解の話 (同スライド p.23)が、前原さんの取り扱っている問題の特殊ケースになっていることに気付いた方もおられるかもしれません。発表の際にも指摘したのですが、坂下さんの研究では、並列計算を駆使して高精度の固有値計算を行っており、今回の前原さんの研究とも大いに関連があるように思いました。

simultaneous block diagonalization of matrices from tmaehara

数理４研　田中 冬彦