並列処理シリーズ 9
並列数値処理 - 高速化と性能向上のために -
本書は並列処理を用い,全体としての演算経過時間を短縮する数値処理アルゴリズムの説明を主眼としている。固有値の求階や連立一次方程式の解法はもとより,並列ソート技法,並列擬似乱数生成技法や高速フーリエ変換技法に言及した。
- 発行年月日
- 2010/04/30
- 判型
- A5 上製
- ページ数
- 272ページ
- ISBN
- 978-4-339-02589-7
- 内容紹介
- 目次
- レビュー
本書は並列処理を用い,全体としての演算経過時間を短縮する数値処理アルゴリズムの説明を主眼としている。固有値の求階や連立一次方程式の解法はもとより,並列ソート技法,並列擬似乱数生成技法や高速フーリエ変換技法に言及した。
刊行のことば
はしがき
1. 基本演算
1.1 行列およびベクトルの分散方法
1.1.1 一次元分散
1.1.2 二次元分散
1.2 ベクトルどうしの演算
1.3 行列とベクトルの積
1.4 行列の転置
1.5 行列の積
1.5.1 キャノン(Cannon)のアルゴリズム
1.5.2 フォックス(Fox)のアルゴリズム
1.5.3 転置を行った後での行列積
1.5.4 SUMMA,PUMMA
1.5.5 ストラッセン(Strassen)のアルゴリズム
1.6 一次回帰型演算
1.7 リダクション演算
1.8 BLASとPBLAS
1.8.1 レベル1 BLAS
1.8.2 レベル2 BLAS
1.8.3 レベル3 BLAS
1.9 より深く勉強するために
章末問題
2. 密行列に対する連立一次方程式
2.1 はじめに
2.2 ガウス・ジョルダン法
2.3 ガウス消去法
2.3.1 ピボッティング
2.4 LU分解法
2.4.1 LU分解法の種類
2.4.2 縦ブロックガウス法
2.4.3 代入計算
2.5 より深く勉強するために
章末問題
3. 疎行列に対する連立一次方程式
3.1 はじめに
3.2 データー構造と基本演算
3.2.1 行列の格納形式
3.2.2 データー分散と基本演算
3.2.3 通信方式
3.3 疎行列用直接解法
3.4 定常的反復法
3.4.1 ヤコビ法(Jacobi法)
3.4.2 ガウス・ザイデル法(Gauss-Seidel法)
3.4.3 SOR法
3.4.4 Red-Black SOR法
3.5 対称行列のための非定常的反復法
3.5.1 共役勾配法
3.5.2 前処理付き共役勾配法
3.5.3 不完全コレスキー分解前処理付き共役勾配法
3.5.4 ブロック化不完全コレスキー分解を利用した共役勾配法
3.5.5 ヤコビ(Jacobi)前処理を利用した共役勾配法
3.5.6 多項式前処理行列を利用した共役勾配法
3.6 非対称行列のための非定常的反復法
3.6.1 共役残差法
3.6.2 双共役勾配法
3.6.3 自乗共役勾配法
3.6.4 安定化双共役勾配法
3.7 クリロフ部分空間法を用いた反復解法
3.7.1 一般化共役残差法
3.7.2 一般化最小残差法
3.7.3 非対称行列における前処理
3.8 より深く勉強するために
3.9 公開ライブラリーについて
3.9.1 BlockSolve
3.9.2 PETSc
3.9.3 HINTS
章末問題
4. 固有値・固有ベクトル
4.1 はじめに
4.1.1 標準固有値問題
4.1.2 一般固有値問題
4.2 対称固有値問題の解法
4.2.1 ヤコビ法
4.2.2 三重対角行列への変換
4.2.3 QR法
4.2.4 二分法
4.2.5 逆反復法
4.2.6 密集固有値に対する問題
4.2.7 分割統治法
4.2.8 ランチョス法(Lanczos法)
4.2.9 一般対称固有値問題
4.3 非対称固有値問題の解法
4.3.1 ヘッセンベルグ形(Hessenberg形)への変換
4.3.2 ヘッセンベルグ-QR 法(Hessenberg-QR法)
4.3.3 アーノルディ法(Arnoldi法)
4.3.4 一般非対称固有値問題
4.4 より深く勉強するために
章末問題
5. 高速フーリエ変換
5.1 はじめに
5.1.1 離散フーリエ変換(DFT)
5.1.2 クーリー・チューキー(Cooley-Tukey)のアルゴリズム
5.1.3 ストッカム(Stockham)のアルゴリズム
5.1.4 三角関数表
5.1.5 逆FFT
5.1.6 周波数間引き型FFT
5.1.7 多次元FFT
5.2 単体プロセッサー向けの高速化手法
5.2.1 ループ長の増加
5.2.2 配列アクセスの最適化
5.2.3 ロード/ストアの削減
5.2.4 コピーの削減
5.2.5 演算量の削減
5.3 分散メモリー向けの並列FFTアルゴリズム
5.3.1 三次元FFTの並列化
5.3.2 三次元モデルによる一次元FFT
5.3.3 三次元モデルによるベクトル化と並列化
5.3.4 データー分割の最適化
5.3.5 その他の最適化手法
5.4 FFTの拡張
5.4.1 混合基底のFFT
5.4.2 実数FFT
5.5 より深く勉強するために
章末問題
6. 擬似乱数
6.1 はじめに
6.2 乱数の検定
6.2.1 平均値検定
6.2.2 頻度検定(一様性)
6.2.3 複数プロセッサー間の独立性検定
6.3 擬似乱数生成アルゴリズム
6.3.1 合同乗算法
6.3.2 M系列乱数
6.4 並列計算機向きアルゴリズム
6.4.1 プロセッサー間の乱数の独立性
6.4.2 合同乗算法
6.4.3 M系列乱数
6.5 より深く勉強するために
章末問題
7. ソート
7.1 はじめに
7.2 逐次ソートアルゴリズム
7.2.1 バブルソート
7.2.2 挿入ソート
7.2.3 選択ソート
7.2.4 シェルソート
7.2.5 クイックソート
7.2.6 マージソート
7.2.7 ラディックスソート
7.3 並列ソートアルゴリズム
7.3.1 高い位からのラディックスソートを利用した並列ソート
7.3.2 ソーティングネットワークを利用した並列ソート
7.3.3 レギュラーサンプリングソート
7.3.4 ランダムサンプリングソート
7.4 より深く勉強するために
章末問題
参考文献
索引