早戸拓也・廣田悠輔 n ハウスホルダー変換 n A=AT T 0 0 Aの固有値 逆変換 三重対角化 Aの固有ベクトル ハウスホルダー変換を使用した相似変換 [Hn-2…H1]A[Hn-2…H1]T=T Hi a = b 逆変換 A[Hn-2…H1]Tui=λi[Hn-2…H1]Tui Tui=λiui i 原理 ◦ 複数本のピボット行・列を溜めておき，後でまとめて更新 0 0 = – × – × BLAS2 保存するベクトル数が大切 依然としてBLAS2の計算が必要 BLAS3 原理 帯幅の設定が大切 ◦ 密行列Aを半帯幅LBの帯行列Bに変換 ◦ 帯行列Bを三重対角行列Tに変換 帯行列化 村田法 LB 0 B A 0 0 0 BLAS3 T 帯行列化の逆変換 逆変換の演算量が倍増 逆変換 固有値計算 三重対角化 村田法の逆変換 村田法 0 0 0 左からH を乗算 0 0 右からHT を乗算 ハウスホルダー変換では 左から直行行列H を乗算 0 原理 ◦ 帯行列の生成にする際，ブロックピボット行・列を保存しておき， 後でまとめて更新 0 = 0 – × 帯幅と保存するブロック列数が大切 – × 帯行列化の逆変換 LB 0 A[Hn-2…H1]Tui=λi[Hn-2…H1]Tui Bui=λiui 0 […HMB2+MB2…HMB2+1HMB2…H1]Tui MB MB2 解法 LB MB MB2 LAPACK Dongarra † † † Wu Dongarra + Bischof 20 40 100 1 2 4 1 2 4 †:ユーザー設定不可 計算機環境 ◦ Xeon X5355 2.66 [GHz] (Quad-core × 2) 2コアごとに L2 キャッシュ 4MB ◦ Red Hat Enterprise WS release 4 ◦ Intel Fortran Compiler 9 ◦ Intel Math Kernel Library テスト行列 ◦ 対称乱数行列 ◦ n = 3000，6000 アルゴリズム ◦ LAPACK ◦ Wu それぞれの最適値となるLB， MB，MB2で評価 PU数が大きい場合にLAPACKより高速 それぞれの最適値となる LB， MB，MB2 で評価 村田法の逆変換が大半を占める MB = 2，MB2 = 2 で評価 LBを大きく取ると高速 LB=100で評価 MBによって演算時間は大きく変化しない PU 数に応じて実行時間が減少 LB=100で評価 PU 数に応じて実行時間が減少 PU 数が大のときMB2が大で高速 Wuのアルゴリズムを8コアXeonマシンで評価した． ◦ 行列サイズが大きい場合，PU数が多い場合，適切なパラメ ータを設定することによりLAPACKより高速となった． ◦ Xeonマシンでは帯幅LBを大きくとると高速となった． ◦ MB2に適切な値を設定することにより，ブロック帯行列の逆 変換が高速となった． ◦ MBを変化させても殆ど演算時間は変化しなかった． 演算量 ◦ ハウスホルダーの演算量: 約 (4/3)n3 行列ベクトル積の演算量: rank-2更新の演算量: 約 (2/3)n3 ◦ 固有値を求めるための演算量: 約 (2/3)n3 O(n2)～ O(n3) • 分割統治法 • QR法 ◦ 逆変換: 約 2n2 m
© Copyright 2024 ExpyDoc
