Diagonalization of max-plus matrices and its applications

点击翻译按钮获取中文摘要

離散事象システムの漸近的な振る舞いを調べるうえで，max-plus代数上の行列固有値に関する理論を整備することは重要である．本年度は，max-plus行列の固有多項式の相異なる根に付随するベクトルが互いに1次独立であることを示した．この結果は論文誌に投稿中である．また，max-plus行列が優対角という性質を持つ場合に，固有値や固有ベクトルを用いて行列を標準形へと相似変形できることを示した．ここで得られる標準形は上三角行列であり，対角行列と同様にべき乗の計算が容易に行える．優対角行列は，固有多項式のすべての根の重複度が1となるような行列のうちの代表的なものである．そのため，より一般の行列に対する対角化あるいは上三角化を考えるうえでの基礎になる結果が得られたことになる．この結果は複数の学会で発表され，論文誌への投稿を準備中である．代数的固有ベクトルの導出過程ではmax-plus代数上の線形方程式を解く必要があるが，その解法の1つに交互法がある．交互法では通常は1つの解しか見つけることができないが，それを適当な初期ベクトルの集合に適用することで，解空間の基底をなすベクトルをすべて求めるアルゴリズムを考案した．これは，固有値問題の観点からは，「固有ベクトル」から「固有空間」へと広まったことを意味する．この結果は論文誌に投稿中である．また，交互法における実際の計算を高速化するため，行列の疎化を利用した新たなアルゴリズムを開発した．これは，最大値をとる過程で真に必要な成分は少数に限られているというmax-plus代数の本質を用いた手法であり，他の様々な計算への波及効果が期待される．この結果については査読付き国際会議ACDA23での発表が決定している．