1月第5週・2月第1週の振り返り

1月第5週・2月第1週（1/27-2/2）

並列プログラミング

ようやくMPIを用いた並列計算によるLU分解法の完全実装に成功し、無事レポートとして提出することができた。来学期以降も同じ課題が出るはずなので実際のコードは示さないが、アルゴリズムの意図を流れに沿って示すことで理解の一助になればと思う。以下で各プロセスは計算する列を分担している。

LUP分解（PA=LU）

Doolittle法を使うので、Lの対角成分は1と仮定する
左上からL, Uを交互に一列/一行ずつ確定していきたい
そのためループはk = 0, 1, ... (N-1)で回す

A[k][k]が担当範囲に含まれるプロセスは、A[k][k]とそれより下の要素の中で絶対値が大きいものを探し、Aおよび列ベクトルbのk行とlargest_abs_row行を入れ替える（部分ピボット選択）。得られた最大の対角要素で列を割り、Lのk列目を得る。Lのk列目情報をlargest_abs_rowの情報とともに他のプロセスに送信する。そのLと既に確定した自分のUを使ってk+1行/列以降の未確定範囲全体に減算を行う（k=0のときUの0行目は自明である）。Uのk+1行目が確定する
担当範囲が現在のkよりも左にあるプロセスは、既に自分が担当すべき範囲のL/Uを求め終わっているので、情報の受信後行入れ替えだけを行う
担当範囲が現在のkよりも右にあるプロセスは、受信したLと既に確定した自分のUを使ってk+1行/列以降の未確定範囲全体に減算を行う（k=0のときUの0行目は自明である）。Uのk+1行目が確定する

結果として各プロセスは自分の担当範囲におけるLとUが確定した状態になる

L(Ux)=Lc=Pbからcを求める

列ベクトルcもプロセス間で分担して求める
（まず左端のプロセスが上から順に担当範囲のcを確定する）
以下を繰り返す

確定されようとしているcの行が担当範囲にまだ達していないプロセスは何もしない
自分の担当するcが既に確定したプロセス群は自分の知るLとcを使って、下のほうのcを右側のプロセスが求められるよう、左隣から受け取った「引くべき値の部分和」にL*cを足して右隣のプロセスに渡す（リレーする）
当該ループで確定することになっているcを担当するプロセスは左隣のプロセスから「引くべき部分和」を受け取り、Pbから引いてcを確定させていく

Ux=cからxを求める

Lc=Pb同様だが方向が逆転し、またxの確定のためにはUで割る必要がある

とこのようになる。とはいえ既存のコードを言葉で表現するとこうだという話であり、この表現からコードに起こすのは難しいかもしれない。

一つ言えるのは、手書きで変数の動きを追うのであれば6x6行列を3プロセスで分担するケースを考えるべきだということである。上述したようにプロセスは担当範囲の値確定前・確定中・確定後の3種類に分けられ、また各プロセスが1行/1列しか担当しない場合は担当範囲の中で値を確定させる順番が考慮から抜けてしまうからである。そして具体的な値ではなく成分をそのまま $u_{02}, l_{10}$ のように扱うことでプログラム中で使うべき添え字が明確になるだろう。

ASP.NET Core MVC

ようやく今期の科目を完遂したので来週からはWebアプリケーションの続きをやっていく。