@techreport{oai:ipsj.ixsq.nii.ac.jp:00029343,
 author = {中田, 和秀 and 張紹良 and Kazuhide, Nakata and Shao-Liang, Zhang},
 issue = {77(2001-HPC-087)},
 month = {Jul},
 note = {Lovasz 数を半正定値計画問題として定式化し、それを内点法によって多項式時間内で解くことが可能である。この場合、内点法の各ステップにおいて、係数行列が密となる線形方程式系を解くことになる。この線形方程式系の大きさはLovasz数を計算するグラフの枝の数と等しくなるため、グラフが大規模になるにつれ、線形方程式系も大規模となる。このとき、線形方程式系の解法として直接法を適用することは、計算時間やメモリ使用量の点で困難となる。このため、直接法を利用する代わりに、クリロフ部分空間法を利用することが試みられてきた。本発表では、これらの枠組みのもと、大規模なグラフに対するLovasz 数の計算を行う。このとき、より大きなグラフに対するLovasz 数を計算するため、この問題における特有の性質を生かしたいくつかの計算手法を提案する。最後に、実際に大規模なグラフに対するLov?'{a}sz数の計算を行うことにより、これらの手法の有用性について検証する。, 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.},
 title = {半正定値計画問題に対するクリロフ部分空間法の適用},
 year = {2001}
}