理論グループのミーティングの報告
第4回

日時：97/05/27
場所：斎藤理一郎助教授教官室 西5-517 

二分法と逆反復法を行なうために必要なGSの構成と基本的なデータフロー(グェンが
説明した)

二分法

    

  1. アルゴリズム

  2. 必要なGSの構成とデータフロー

  3. 計算時間

   

逆反復法

    

  1. アルゴリズム

  2. GSの構成とデータフロー

  3. 計算時間






逆変換を行なう時のデータフロー(松尾が説明した)

A~ の 固有ベクトル V と Wk ベクトルの内積(V*Wk) をとり、
それに Ck をもちいて
V = V - Ck*(V*Wk)Wk を k=N-1 から 1 までおこなうと V は
A の固有ベクトルになる。



           +---+
           | M |      GS のどれかが持っている、Wk をGL にコピー
           +---+
        Wk   ↓     
           +---+    
           |GS |    
           +---+    
             ↓      ※k step
             ↓
             ↓
    +---+  +---+
    | M |  |GL |
    |   |←|   |
    +---+  +---+
         Wk


         +---+  +---+  +---+ 
         | M |  | M |  | M | それぞれの GSの 持っている A~ の固有ベクトルVと
         +---+  +---+  +---+ Wk の 内積を もとめ GS 内に保存( TMP ) 
     V    ↓     ↓     ↓   
         +---+  +---+  +---+  
         |GS |  |GS |  |GS |  TMP 
         +---+  +---+  +---+
     Wk    ↑     ↑     ↑ 
           −−−−−−−−
           ↑
  +---+  +---+              ※ k step
  | M |→|GL |
  +---+  +---+

         +---+  +---+  +---+ 
         | M |  | M |  | M |
         +---+  +---+  +---+  GLメモリからは ベクトルWk に Ck を 乗せられて
      V   ↑↓   ↑↓   ↑↓  GS へ
         +---+  +---+  +---+  GSメモリからは 固有ベクトル V  の要素が
         |GS |  |GS |  |GS |  - Ck*Wk * TMP ひかれて GS メモリへ戻る 
         +---+  +---+  +---+  
           ↑     ↑     ↑
           −−−−−−−−
           ↑  Ck*Wk
  +---+  +---+               ※ 2k step
  | M |→|GL |
  +---+  +---+
       Wk


 合計 4k step で k=2 〜 N とすると 約 2N^2  それが N/Ngs 回実行されるから
      2N^3/Ngs step かかる



 戻る