大規模連立一次方程式を解くための インターネットサービスシステムの構築 趙 涛(東京大学) 鄭 波(東京大学) 張 紹良(名古屋大学) 2007年3月7日 流れ 研究背景 既存システムの紹介 本システムの目的 本システム使用流れ 本システム構築と実装 まとめ 背景1 大規模連立一次方程式は様々な領域に 必要不可欠 航空管制 Air Traffic Control 天体物理学 Astrophysics 生化学 Biochemistry 化学工学 Chemical Engineering 反応速度論 Chemical Kinetics サーキット物理学 Circuit Physics コンピュータシステムシミュレーション Computer System Simulation 人口統計学 Demography 経済学 Economics 有限要素法 Finite Element Analysis 流体力学 Fluid Flow 線形計画法 Linear Programming 原子炉デザイン Nuclear Reactor Design 海洋学 Oceanography 石油工学 Petroleum Engineering パワーシステムネットワーク Power System Networks 構造工学 Structural Engineering 測量学 Surveying 自然現象 分 析 定式化 偏微分方程式 Ax = b A:大規模連立一次方程式 離散化 背景2 連立一次方程式解法開発の現状 直接法 Gauss消去法 LU分解 ... 反復法 定常反復法 Jacobi法 Gauss-Seidel法 SOR法 SSOR法 ... 非定常反復法 GMRES法 GCR法 共役勾配法(Conjugate Gradient法) 双共役勾配法(Bi-CG法) CGS法 Bi-CGSTAB法 GPBi-CG法 ... 係数行列のサイズが小さい方 程式だけに適用 大規模連立一次方程式、特に 大規模疎行列に適用 どの反復法もすべての方程式 を解けるとは言えない 解法の選択はユーザに困難で ある 背景3 利用者と研究者それぞれの立場 大規模連立一次方程式の解法を利用する人は利用 者と呼ぶ。利用者は自分の方程式に一番有効な解 法のみに興味にもつ。 大規模連立一次方程式の解法を開発する人は研究 者と呼ぶ。研究者は解法の実際のパフォーマンスを 把握したい。 利用者の場合 解法実装のために様々可能な手段 プログラム言語:Fortran、C++など 線形計算ライブラリ:LAPACK、Templatesなど 数学ソフトウェア:Matlab、Mathematicsなど どんな方法でも、解法の実装は難しい。一般の場合は 利用者 研究者 研究者の場合 方程式のデータを集めるために様々な手段 方程式を提供するウェブサイト:Matrix market、Netlibなど 関連研究室からもらう 関連会社からもらう 以上の方法でも、方程式のデータは不足する。実際に 方程式の出所は利用者ーー 利用者 互いに有利である 研究者 既存システム1ーーITBL ITBLは反復法評価のインターネットシステムである http://www.itbl.jp 利 用 者 方程式の解 方程式の提供 • 研究者は新解法を開発 しても、自分で登録できない 解法 方程式 解法の評価を見れる 研 究 者 既存システム2 ーーMatrix Market Matrix marketは行列データを提供するウェブサイトである http://math.nist.gov/MatrixMarket/ 利 用 者 方程式の提供 • 方程式のデータベースと して豊富であるが、計算 サーバの性能はない 方程式 方程式データのダウンロード 研 究 者 既存システム3ーーMatlab Matlabは数値解析ソフトウェアである 利 用 者 アルゴリズムを実装して、方程式を解くことができる ライブラリ • 方程式のデータベースが ない • 解法も登録できない 方程式を入力して、解法を検証できる 研 究 者 既存システムの比較 ITBL Matrix Market Matlab 本システム 方程式のデータベース ○ ○ × ○ 解法のデータベース × × × ○ 計算サーバ ○ × ○ ○ 目標 本研究の目的 インターネット上に利用者と研究者の間交流の場を提供する 利 用 者 方程式の解 方程式の提供 解法 • 方程式のデータベース • 解 法のデータベース • 計算サーバ 方程式 ZZZシステムと呼ぶ 解法の提供 解法の検証 研 究 者 本システムの使用流れーー実例 方程式データ 行列ORSREG 1は数値油層モデルの構築問題から得る行列である。 行列の形は 数値型: 対称性: サイズ: 非ゼロ要素数: 解法 GPBi-CG法 適用範囲は 数値型: 対称性: 複素数 非対称 実数 非対称 2205 × 2205 14133 本システムの使用流れーー計算タスク入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 本システムの使用流れーー計算タスク入力画面 計算タスク 入力画面 Equations Add 追加 方程式追加 Algorithms Add 追加 G O 追加 解法追加 本システムの使用流れーー方程式入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 Format Add 追加 Matrix Add 追加 Vector Add 追加 NEXT 追加 本システムの使用流れーー方程式入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 Format Add 追加 Matrix Add 追加 Vector Add 追加 NEXT 追加 書式 行列 ベクトル 本システムの使用流れーー書式入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 本システムの使用流れーー書式入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 書式登録 G O 追加 内部書式 書式検索 本システムの使用流れーー方程式入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 本システムの使用流れーー方程式入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 入力した書式 本システムの使用流れーー行列入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 行列入力画面 • Upload • Inner • Search NEXT 追加 本システムの使用流れーー行列入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 NEXT 追加 • Search 行列アップロード NEXT 追加 (ORSREG 1) 行列入力画面 • Upload • Inner 内部行列 • Search NEXT 追加 行列検索 本システムの使用流れーー方程式入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 行列入力画面 • Upload • Inner • Search NEXT 追加 本システムの使用流れーー方程式入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 行列入力画面 • Upload • Inner アップロード • Search した行列NEXT 追加 本システムの使用流れーーベクトル入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 行列入力画面 • Upload • Inner • Search NEXT 追加 ベクトル入力画面 • Upload • Inner • Search NEXT 追加 本システムの使用流れーーベクトル入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 行列入力画面 • Upload ベクトルアップロード • Inner • Search 追加 内部ベクトルNEXT ベクトル入力画面 (すべて1) • Upload • Inner ベクトル検索 • Search NEXT 追加 本システムの使用流れーー方程式入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 行列入力画面 • Upload • Inner • Search NEXT 追加 ベクトル入力画面 • Upload • Inner • Search NEXT 追加 本システムの使用流れーー方程式入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 行列入力画面 • Upload • Inner • Search NEXT 追加 ベクトル入力画面 • Upload • Inner 入力したベクトル • Search NEXT 追加 本システムの使用流れーー計算タスク入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 行列入力画面 • Upload • Inner • Search NEXT 追加 ベクトル入力画面 • Upload • Inner • Search NEXT 追加 本システムの使用流れーー計算タスク入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 入力した方程式 行列入力画面 • Upload • Inner • Search NEXT 追加 ベクトル入力画面 • Upload • Inner • Search NEXT 追加 本システムの使用流れーー解法入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 解法入力画面 • Input • Inner • Search NEXT 追加 行列入力画面 • Upload • Inner • Search NEXT 追加 NEXT 追加 ベクトル入力画面 • Upload • Inner • Search NEXT 追加 本システムの使用流れーー解法入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 解法入力画面 • Input • Inner • Search NEXT 追加 解法登録 NEXT 追加 (GPBi-CG) 行列入力画面 • Upload • Inner • Search NEXT 追加 内部解法 ベクトル入力画面 • Upload • Inner • Search NEXT 追加 解法検索 本システムの使用流れーー計算タスク入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 解法入力画面 • Input • Inner • Search NEXT 追加 行列入力画面 • Upload • Inner • Search NEXT 追加 NEXT 追加 ベクトル入力画面 • Upload • Inner • Search NEXT 追加 本システムの使用流れーー計算タスク入力画面 方程式入力画面 計算タスク 入力画面 Equations Add 追加 Algorithms Add 追加 G O 追加 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 解法入力画面 • Input • Inner • Search NEXT 追加 行列入力画面 • Upload • Inner • Search NEXT 追加 NEXT 追加 ベクトル入力画面 入力した解法 • Upload • Inner • Search NEXT 追加 本システムの使用流れーー計算中画面 方程式入力画面 計算タスク 入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 Equations Add 追加 Algorithms Add 追加 解法入力画面 G O 追加 書式入力画面 • Input • Inner • Search NEXT 追加 行列入力画面 • Upload • Inner • Search NEXT 追加 NEXT 追加 ベクトル入力画面 • Upload 計算中画面 Computing … OVER 追加 • Inner • Search NEXT 追加 本システムの使用流れーー計算中画面 方程式入力画面 計算タスク 入力画面 書式入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 Equations Add 追加 Algorithms Add 追加 解法入力画面 G O 追加 行列入力画面 • Upload • Input • Inner • Inner • Search NEXT 追加 • Search 計算進捗 NEXT 追加 ベクトル入力画面 • Upload 計算中画面 Computing … OVER 追加 • Inner • Search NEXT 追加 本システムの使用流れーー計算結果画面 書式入力画面 方程式入力画面 計算タスク 入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 NEXT 追加 Equations Add 追加 Algorithms Add 追加 行列入力画面 解法入力画面 G O 追加 • Upload • Input • Inner • Inner • Search • Search NEXT 追加 NEXT 追加 ベクトル入力画面 • Upload 計算中画面 Computing … OVER 追加 計算結果画面 Result BACK 追加 • Inner • Search NEXT 追加 本システムの使用流れーー計算結果画面 書式入力画面 方程式入力画面 計算タスク 入力画面 Format Add 追加 • Upload Matrix Add 追加 • Inner Vector Add 追加 • Search NEXT 追加 計算結果 NEXT 追加 Equations Add 追加 Algorithms Add 追加 行列入力画面 解法入力画面 G O 追加 • Upload • Input • Inner • Inner • Search • Search NEXT 追加 NEXT 追加 ベクトル入力画面 計算中画面 Computing … OVER 追加 計算結果画面 Result BACK 追加 • Upload 残差収束履歴 • Inner • Search NEXT 追加 本システムの構築図 データベース 方程式のデータベース 計算サーバ 解法のデータベース 解 法 方程式 設定 ユーザ 結果 Internet Webサーバー 計算サーバー 本システム実装1ーー方程式データベース 行列書式のツールの構築 ZZZ行列書式定義言語を開発した だれでも行列書式を定義できる 自分の行列 + 例: 書式定義書 登録 ZZZシステム たくさんの行列を受けられる 複素数MM書式 (\\%(~<br>)*<br>)* <int:{ROW_NUM;}> <sp>+<int:{COL_NUM;}> (<sp>+<int:{NONZERONUM;}>)? (<br><sp>*<int:{ROW;}><sp>+ <int:{COL;}><sp>+<number: {ELE_REAL;}><sp>+ <number:{ELE_IMAGE;}>)*<br>* 本システムの実装2ーー解法データベース ZZZプログラム言語を開発した 例、GPBiCG法はZZZ言語で実装できる ... its = its + 1; while(rLog > -12 && its < max_time) { print("its = ");print(its); print(", rLog = ");println(rLog); PnHn = RnHn + (Pn0Hn0 Pn0AGn0) * beta_n0; PnAHn = A * PnHn; tmpd1 = r0 ^ RnHn; tmpd2 = r0 ^ PnAHn; alpha_n = tmpd1 / tmpd2; Rn1AGn0 = RnHn0 - RnHn (RnAHn0 + Pn0AHn0 * beta_n0 - PnAHn) * alpha_n; Rn1Hn = RnHn - PnAHn * alpha_n; Rn1AHn = A * Rn1Hn; if(its == 2) { Rn1Hn; ... t2 = Rn1AHn ^ 本システムの実装2ーー解法データベース ZZZプログラム言語の紹介 データ型 int string boolean 運算 算術運算: +, -, *, / 比較運算: <, <=, >, >=, ==, != 論理運算: &&, ||, ! フロー制御 選択(if) ループ(while) 内部関数 abs() log() … doubl e comp lex matri x 本システムの実装3ーー計算サーバ 即時通信 即時通信 ユーザ Webサーバ ZZZ計算サーバと通信できる 計算サーバ 他のサーバ いつでも、どこからでも計算サーバを利用することで、必要な計算 結果を入手できる まとめ 方程式のデータベースを構築して、どの利用者も 自分の方程式をアップロードできる 解法のデータベースを構築して、どの研究者も自 分の解法をアップロードできる 計算サーバを構築して、いつでも、どこからでも必 要な計算結果を入手できる
© Copyright 2024 ExpyDoc