氏名 : 栗山 進吾 (280067119)
所属 : 杉原研
題目 : 特異値分解を用いた密行列とベクトルの積の高速計算
概要 :
行列とベクトルの積の計算量は、M×N 行列のときO(MN)であるが、特異値分解(SVD)により行列のランク k の近似を作ることで、O(k(M+N))にすることができる。同じ行列に対して、ベクトルを変えながら何度も積を計算するような場合、前処理として一度SVDを計算してしまえば、繰り返し使えるので非常に有効である。
近似するランク k はできるだけ小さいほうがよいが、行列が小さいランクで十分近似できないことが多い。このような場合でも、行列をブロックに分けることにより、部分的にSVDを利用できることがある。その例として、Cauchy行列がある。今回は、このCauchy行列に対してSVDを適用するアルゴリズムを説明する。また実際に、Cauchy行列とベクトルの積の計算が現れる多項式内挿に適用して、その計算速度、精度をみる。
目次に戻る