アルゴリズム

並列計算の数理とアルゴリズム

フレデリック・マグレス
フランソワ=グザヴィエ・ルー
桑原 拓也

森北出版

はじめに
序文

第I部 並列計算機,プログラミング,アルゴリズム
第1章 計算機のアーキテクチャ

  • 1.1 並列計算の種類
  • 1.2 メモリのアーキテクチャ
  • 1.3 ハイブリッドアーキテクチャ

第2章 並列化とプログラミングのモデル

  • 2.1 並列化
  • 2.2 性能評価基準
  • 2.3 データの並列化
  • 2.4 特殊な例:ベクトル化
  • 2.5 通信タスク
  • 演習問題

第3章 並列アルゴリズムの基礎知識

  • 3.1 漸化式の並列アルゴリズム
  • 3.2 局所化と分散:行列の積
  • 演習問題

さらに理解するために

第II部 行列の数値解析に必要な基礎知識
第4章 行列の数値解析の総論

  • 4.1 線型代数の基礎知識
  • 4.2 行列の性質

第5章 疎行列

  • 5.1 疎行列の起源
  • 5.2 疎行列の並列構造化:共有メモリ
  • 5.3 疎行列のブロックによる並列構造化:分散メモリ

第6章 線型システムの解法

  • 6.1 直接法
  • 6.2 反復法

さらに理解するために

第III部 直接法による解法
第7章 LU分解による線型システムの解法

  • 7.1 LU分解の原理
  • 7.2 ガウス分解
  • 7.3 ガウス-ジョルダン分解
  • 7.4 対称行列のためのクラウト分解とコレスキー分解

第8章 密行列のLU分解法の並列化

  • 8.1 ブロックによる分解
  • 8.2 メッセージ通信によるプログラミング環境でのブロック分解の実装
  • 8.3 前進・後退代入による並列化
  • 演習問題

第9章 疎行列のLU分解法

  • 9.1 分解処理された行列の構造
  • 9.2 シンボリック分解とリナンバリング
  • 9.3 消去木
  • 9.4 消去木と依存
  • 9.5 入れ子分割法(ND法)
  • 9.6 前進・後退代入法
  • 演習問題

さらに理解するために

第IV部 反復法による解法
第10章 クリロフ空間の総論

  • 10.1 クリロフ空間
  • 10.2 アーノルディ基底の構築

第11章 対称正値行列のための完全正規直交化法

  • 11.1 対称行列のためのランチョス基底の構築
  • 11.2 ランチョス法
  • 11.3 共役勾配法:CG 法
  • 11.4 勾配法の比較
  • 11.5 正値対称行列のための前処理法の原理
  • 演習問題

第12章 任意行列のための完全直交化法

  • 12.1 一般化最小残差法:GMRES法
  • 12.2 対称行列の場合:MINRES法
  • 12.3 ORTHODIR法
  • 12.4 非対称行列のための前処理の原理
  • 演習問題

第13章 非対称行列のための双直交化法

  • 13.1 非対称行列のためのランチョス双直交基底
  • 13.2 非対称ランチョス法
  • 13.3 双共役勾配法:BiCG法
  • 13.4 準最小残差法:QMR法
  • 13.5 安定化双共役勾配法:BiCGSTAB法

第14章 クリロフ法の並列化

  • 14.1 密な行列-ベクトル積の並列化
  • 14.2 点集合による疎な行列-ベクトル積の並列化
  • 14.3 要素集合による疎な行列-ベクトル積の並列化


第15章 並列前処理法

  • 15.1 不完全分解法
  • 15.2 シュール補行列法
  • 15.3 代数的マルチグリッド型の方法
  • 15.4 加法シュワルツ法による前処理法
  • 演習問題

さらに理解するために

結言
演習問題略解
参考文献
索引