FEM5

Report
スカイライン法
2013年9月20日
後 保範
1
有限要素法の線形計算
有限要素法離散化
対称疎行列
直接解法
反復解法
対称帯行列
スカイライン法
スパースソルバ
非対称疎行列
直接解法
反復解法
非対称帯行列
スパースソルバ
2
対称スカイライン行列の形(×)
この部分が
非ゼロになる
この形は
不可能
3
対称スカイライン行列の形(○)
この影響は
行列内だけ
計算可能
4
対称スカイライン行列の持ち方
IDX[k]: k列の先頭行番号
k
データの
並び順
A[PT[k]] :
Kの対角要素
5
対称スカイライン行列の消去計算
Aの位置: PT[k]-k
IDX[k]
内積で更新
i
内積で更新
i
k
Aの位置: PT[k]
6
対称スカイライン消去1(全体)
for (k=1; k<n; k++)
{ KP = PT[k] – k;
//密A[0][k]に対応位置
for (i=IDX[k]; i<k; i++)
{ i列によるk列の消去計算 }
k列の正規化計算
}
7
対称スカイライン消去2(消去)
JS = Math.max(IDX[k], IDX[i]);
IP = PT[i] – i;
S = 0.0;
for (j=JS; j<i; j++)
{ S += A[IP+j]*A[KP+j]; }
A[KP+i] -= S;
8
対称スカイライン消去3(正規化)
S = 0.0;
for (i=IDX[k]; i<k; i++)
{ Val = A[KP+i] / A[PT[i]];
S += Val*A[KP+i];
A[KP+i] = Val;
}
A[PT[k]] -= S;
9
対称スカイライン前進代入
for (k=1; k<n; k++)
{ KP = PT[k] – k;
S = 0.0;
for (i=IDX[k]; i<k; i++)
{ S += A[KP+i]*B[i]; }
B[k] -= S;
for (k=0; k<n; k++)
{ B[k] = B[k] / A[PT[k]; }
}
10
対称スカイライン後退代入
for (k=n-1; k>0; k--)
{ KP = PT[k] – k;
for (i=IDX[k]; i<k; i++)
{ B[i] -= A[KP+i]*B[k]; }
}
11
3x3ブロックスカイライン法
• 構造解析用のスカイライン法
• 構造解析は1節点が3自由度を持つ場合が多
いことに着目した方法
• スカイラインに1要素を3x3の行列として、ポイ
ンターを持つ
• 3自由度を持たない点は、ダミー自由度を挿
入して、1節点3自由度にする
• ポインタ処理に対し演算量が9倍になるため、
高速化が期待される
12
帯行列の分解前後
13
スカイライン行列の分解前後
14
スパースソルバの分解前後
15
スカイライン用番号変換
• RCM法
Reverse Cuthill-Mckee Algorithm
• 目的
UTDU分解において生じる帯幅(スカイライン
幅)の縮小
• 基本的な考え方
既にラベル付けされた頂点に頂点を優先的に
番号付けしていく。最後に番号を逆順に。
16
スパースソルバ用番号変換
• 最小次数順位法
Minimum Degree Ordering Algorithm
• 目的
UTDU分解において生じるfill-in最小化
• 基本的な考え方
結合接点の少ない順に番号を付ける
17

similar documents