半正定値計画問題に対するクリロフ部分空間法の適用

• Item type: SIG Technical Reports(1)
• 公開日: 2001-07-25
• タイトル: 半正定値計画問題に対するクリロフ部分空間法の適用
• タイトル / 言語: en
• タイトル: Incorporating Krylov - Subspace Methods for Semidefinite Programs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学 工学系研究科 物理工学専攻
• 著者所属: 東京大学 工学系研究科 物理工学専攻
• 著者所属(英): en
• 著者所属(英): Department of Applied Physics, Graduate School of Engineering, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Applied Physics, Graduate School of Engineering, University of Tokyo
• 著者名: 中田, 和秀; 張紹良
• 著者名(英): Kazuhide, Nakata; Shao-Liang, Zhang
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Lovasz 数を半正定値計画問題として定式化し、それを内点法によって多項式時間内で解くことが可能である。この場合、内点法の各ステップにおいて、係数行列が密となる線形方程式系を解くことになる。この線形方程式系の大きさはLovasz数を計算するグラフの枝の数と等しくなるため、グラフが大規模になるにつれ、線形方程式系も大規模となる。このとき、線形方程式系の解法として直接法を適用することは、計算時間やメモリ使用量の点で困難となる。このため、直接法を利用する代わりに、クリロフ部分空間法を利用することが試みられてきた。本発表では、これらの枠組みのもと、大規模なグラフに対するLovasz 数の計算を行う。このとき、より大きなグラフに対するLovasz 数を計算するため、この問題における特有の性質を生かしたいくつかの計算手法を提案する。最後に、実際に大規模なグラフに対するLov?'{a}sz数の計算を行うことにより、これらの手法の有用性について検証する。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: As a semidefinite program, the computation of the Lovasz number can be solved by a interior-point method in a polynomial time. When one uses a interior-point method for the computation, one has to solve a linear system whose size is the number of edges of the graph and whose coefficient matrix is fully dense in each step of the interior-point method. Therefore, for a huge graph, it is difficult to apply direct methods to the dense linear systems which become huge. In the present paper, we exploit some Krylov-subspace methods for solving the huge and dense linear systems. In terms of the charcatic of the Lovasz number's proplem, several special techniques are proposed for solving the linear systems rapidly. Finally, computational experiments are reported to confirm whether these methods work effectively for computing the Lovasz number for huge graph.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 情報処理学会研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 2001, 号 77(2001-HPC-087), p. 13-18, 発行日 2001-07-25
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会