博 士 論 文 概 要

早稲田大学大学院理工学研究科

博 士 論 文 概 要

論 文 題 目

高精度計算を用いたポータブルな精度保証付き数値計 算法の研究

Studies on Portable Self-validating Methods with Accurate Computations

申 請 者

尾崎 克久

Katsuhisa Ozaki 氏 名

情報・ネットワーク専攻 情報数理工学研究 専攻・研究指導

(課程内のみ)

2006 年 12 月

科 学 技 術 計 算 を 行 う 際 、 ハ ー ド ウ ェ ア に よ っ て 高 速 に 実 行 可 能 な 浮 動 小 数 点 演 算 が よ く 用 い ら れ る 。 た だ し 浮 動 小 数 点 数 を 用 い た 計 算 で は 丸 め 誤 差 ・ 桁 落 ち 等 の 誤 差 が 発 生 し 、 解 析 的 な 解 か ら ほ ど 遠 い 計 算 結 果 を 得 る こ と が あ る ． そ こ で 真 の 解 と 数 値 解 の 距 離 で あ る 誤 差 を 知 る こ と は 非 常 に 大 切 な 問 題 で あ る 。 そ の た め に 誤 差 解 析 と い う 分 野 が 発 展 し 、 ア ル ゴ リ ズ ム が 導 く 数 値 解 に 対 す る 誤 差 の 上 限 を 式 で 与 え 、 数 値 解 の 持 つ 精 度 の 良 し 悪 し や 、 ア ル ゴ リ ズ ム 自 身 の 良 し 悪 し を 推 測 し 、議 論 が 行 わ れ て き た 。例 え ば 連 立 一 次 方 程 式 に 関 し て は 、条 件 数 や g r o w t h f a c t o r と い う 概 念 を 用 い て 、誤 差 の 上 限 を 式 で 抑 え る こ と は 可 能 で あ る 。し か し 、 真 の 条 件 数 は 数 値 計 算 で は 求 め ら れ ず 、g r o w t h f a c t o r は 非 常 に 大 き な 値 で あ る た め に 誤 差 は 過 大 評 価 さ れ 、 誤 差 の 上 限 を 実 用 的 か つ 定 量 的 な 評 価 で 得 る こ と は 難 解 な こ と だ と 考 え ら れ て き た 。 誤 差 を 定 量 的 に 求 め る 手 段 と し て よ く 用 い ら れ る 区 間 演 算 を 連 立 一 次 方 程 式 に 対 し て 適 用 す る と 近 似 計 算 に 要 す る 時 間 の 数 1 0 倍 の 時 間 を 要 し 、 ま た 誤 差 の 上 限 が 計 算 ご と に 膨 れ 上 が る た め に 問 題 が あ っ た 。 近 年 、O i s h i・R u m p ら に よ り 連 立 一 次 方 程 式 の 精 度 保 証 に つ い て は 求 解 に 要 す る 時 間 の 数 倍 の 時 間 を か け れ ば 、 実 用 的 か つ 定 量 的 な 誤 差 の 上 限 値 を 得 る こ と が 可 能 に な っ た 。 数 値 計 算 は 精 度 が 保 証 さ れ て い な い 結 果 を 返 す た め に 学 問 的 に は 未 成 立 と も 思 わ れ て い た が 、 精 度 保 証 付 き 数 値 計 算 は 実 用 的 な 時 間 で 実 装 さ れ る こ と か ら 確 立 し た 研 究 と し て 評 価 さ れ て い る 。 現 在 実 用 的 な 精 度 保 証 付 き 数 値 計 算 は 連 立 一 次 方 程 式 、 行 列 の 固 有 値 問 題 、 偏 微 分 方 程 式 、 数 値 積 分 等 の 様 々 な 分 野 で 達 成 さ れ 、 今 も 高 速 化 や 高 精 度 化 の 議 論 が 行 わ れ 、 進 歩 し 続 け て い る ．

そ の 背 景 の 中 で 本 論 文 で は 「 高 精 度 計 算 を 用 い た ポ ー タ ブ ル な 精 度 保 証 付 き 数 値 計 算 法 の 研 究 」 と し て 、 計 算 機 環 境 に 依 存 し な い 高 精 度 か つ 高 速 な 精 度 保 証 付 き 数 値 計 算 を 行 う 手 法 に つ い て 述 べ ら れ て い る 。特 に「J a v a に よ る 連 立 一 次 方 程 式 の 数 値 解 に 対 す る 精 度 保 証 法 」 と 「 計 算 幾 何 学 に 現 れ る 行 列 式 の 精 度 保 証 付 き 数 値 計 算 法 」 に つ い て 書 か れ て い る 。

J a v a は 多 く の ユ ー ザ を 持 つ プ ロ グ ラ ミ ン グ 言 語 で あ り 、近 年 は 高 速 化 の 技 術 が 発 達 し て 、 数 値 計 算 や シ ミ ュ レ ー シ ョ ン に も 用 い ら れ る 。 そ こ で 精 度 保 証 付 き 数 値 計 算 を J a v a で 行 う 際 に は 、J a v a は I E E E 7 5 4 が 定 め る 有 向 丸 め の 変 更 を サ ポ ー ト し て い な い こ と が 問 題 と な る （J N I を 用 い て 他 の 言 語 で 作 成 さ れ た 有 向 丸 め の 変 更 を 実 装 し た ラ イ ブ ラ リ を 用 い れ ば 可 能 で あ る が 、 ポ ー タ ビ リ テ ィ は 失 わ れ る ）。そ こ で 有 向 丸 め の 変 更 を 用 い な い 精 度 保 証 法 が 必 要 と な り 、デ フ ォ ル ト の 最 近 点 へ の 丸 め の 計 算 モ ー ド の み を 用 い て 事 前 誤 差 評 価 を 用 い る 手 法 が 有 効 で あ る が 、 こ の 手 法 は 起 こ り う る 最 大 の 誤 差 を 考 慮 す る た め に 、 誤 差 の 上 限 が 過 大 評 価 さ れ る こ と が あ る 。 そ こ で 従 来 手 法 と 計 算 量 が ほ ぼ 同 等 で か つ 誤 差 を 過 大 評 価 せ ず に J a v a で 実 装 で き る 連 立 一 次 方 程 式 の 数 値 解 に 対 す る 精 度 保 証 法 を 提 案 す る 。 精 度 保 証 の 基 本 式 に 対 し て 最 終 的 な 誤 差 上 限 に 大 き く 影 響 す る 部 分 の み に 高 速 か つ 高 精 度 な 内 積 計 算 法 を 適 用 し て 誤 差 の 過 大 評 価 を 防 ぎ 、 有 向 丸 め を 使 用 し な い

1

事 前 誤 差 評 価 を 用 い る こ と で J a v a の ポ ー タ ビ リ テ ィ が 保 た れ る 。 そ の 結 果 と し て ノ ル ム に よ る 過 大 評 価 の な い 誤 差 上 限 、 数 値 解 の 成 分 そ れ ぞ れ に 対 す る 過 大 評 価 の な い 誤 差 上 限 を 得 る 手 法 の 開 発 に 成 功 し て い る 。

次 に 計 算 幾 何 学 に 現 れ る 行 列 式 に 対 す る 高 速 な 精 度 保 証 付 き 数 値 計 算 法 の 開 発 に つ い て 議 論 さ れ て い る 。 計 算 幾 何 学 に お け る 初 等 的 な 判 定 問 題 は 低 次 元 の 行 列 式 の 符 号 を 判 定 す る 問 題 に 帰 着 さ れ る こ と が 知 ら れ て い る が 、 本 論 文 で は 点 と 平 面 の 位 置 関 係 を 判 定 す る 問 題 が 扱 わ れ て い る 。 数 値 計 算 に よ り 行 列 式 を 求 め た 場 合 は 浮 動 小 数 点 演 算 に よ る 誤 差 の た め に 正 し い 判 定 結 果 を 返 さ な い 場 合 が あ り 、 問 題 視 さ れ て い る 。こ の 問 題 点 に 対 し て 従 来 の 手 法 で は 多 倍 長 精 度 計 算 を 用 い て 、 な る べ く 正 し い 結 果 を 得 る よ う に 対 処 し て い た が 、 多 倍 長 精 度 演 算 は ソ フ ト ウ ェ ア に よ り 仮 想 的 に 指 数 部 ・ 仮 数 部 を 拡 張 し て 実 行 さ れ る た め に 低 速 で あ る が 、 近 年 浮 動 小 数 点 数 演 算 の み を 用 い て 高 精 度 計 算 を 行 う 手 法 を S h e w c h u k が 開 発 し 、 従 来 の 多 倍 長 精 度 計 算 よ り も 高 速 で あ る こ と を 示 し た 。数 年 後 に D e m m e lと H i d a に よ り 、 行 列 式 の 計 算 は 浮 動 小 数 点 数 の 和 に 誤 差 な く 変 換 し 、 高 精 度 に ベ ク ト ル の 総 和 を 計 算 す る ア ル ゴ リ ズ ム を 適 用 す れ ば 、 問 題 が 悪 条 件 な 場 合 に は よ り 高 速 に 実 行 可 能 で あ る こ と が 示 さ れ た 。 近 年 Ｒ ｕ ｍ ｐ ・O g i t a・O i s h i ら に よ り 開 発 さ れ た ベ ク ト ル の 総 和 に 対 す る 計 算 結 果 が 実 数 で 計 算 し た 真 の 値 の 必 ず 隣 の 浮 動 小 数 点 数 を 返 す （f a i t h f u l と 呼 ば れ る ） 高 速 か つ 高 精 度 な ア ル ゴ リ ズ ム が 開 発 さ れ た 。 こ こ で 行 列 式 を 浮 動 小 数 点 数 の 和 に 誤 差 な く 展 開 し 、f a i t h f u l な 結 果 を 返 す ア ル ゴ リ ズ ム を 適 用 す れ ば 問 題 に 必 要 な 行 列 式 の 符 号 は 保 証 さ れ る が 、 こ こ で 行 列 式 か ら 生 成 さ れ る ベ ク ト ル の 持 つ 特 殊 な 構 造 を 考 慮 し た 計 算 を 行 い 、 ま た 符 号 が 正 し い こ と が 保 証 さ れ る よ う に 終 了 条 件 を 緩 和 す る こ と で 、 よ り 高 速 な ア ル ゴ リ ズ ム を 開 発 す る こ と に 成 功 し た 。 ま た S h e w c h u k に よ る 適 応 的 な 手 法 と 合 わ せ る と 、 簡 単 な 問 題 は 高 速 に 精 度 保 証 で き 、 悪 条 件 な 問 題 は 提 案 手 法 を 用 い て よ り 高 速 に 行 列 式 の 符 号 が 保 証 さ れ る こ と が 示 さ れ て い る 。

以 下 は 、 各 章 の 構 成 に 基 づ き 、 本 論 文 の 概 要 を 述 べ る 。 本 論 文 は ５ 章 か ら な っ て い る 。

第 1 章 「 序 論 」 で は 本 論 文 で 用 い る 浮 動 小 数 点 数 、 最 近 点 へ の 丸 め モ ー ド の み を 用 い た 浮 動 小 数 点 数 演 算 に よ る 事 前 誤 差 評 価 に つ い て 述 べ 、 連 立 一 次 方 程 式 の 数 値 解 の 精 度 保 証 法 ・ 高 精 度 計 算 を 紹 介 し 、 次 章 以 降 の 準 備 を 行 っ て い る 。

第 2 章 「J a v a に よ る 連 立 一 次 方 程 式 の 数 値 解 の 高 精 度 な 精 度 保 証 法 」 で は J a v a が I E E E 7 5 4 が 定 め る 浮 動 小 数 点 数 演 算 に お け る 有 向 丸 め を 実 装 し て い な い 点 を 考 慮 し て も 、 連 立 一 次 方 程 式 の 数 値 解 が 持 つ 誤 差 を 過 大 評 価 し な い 手 法 を 構 築 し て い る 。 有 向 丸 め を 用 い ず に 誤 差 の 上 限 を 求 め る に は 事 前 誤 差 評 価 と い う 手 法 を

3

用 い る が 、 事 前 誤 差 評 価 は 起 こ り う る 最 大 の 誤 差 を 常 に 考 慮 す る た め に 、 誤 差 の 過 大 評 価 は 避 け ら れ な い ． 特 に J a v a を 用 い る 場 合 に は 事 前 誤 差 評 価 を さ ら に 有 向 丸 め を 用 い ず に 、 最 近 点 へ の 丸 め モ ー ド の み で 評 価 す る 形 式 を 用 い る の で 誤 差 は よ り 過 大 評 価 と な る 。 こ の 問 題 点 を 解 決 す る た め に 浮 動 小 数 点 演 算 の み を 使 用 し た 高 精 度 計 算 を 用 い る が 、 最 終 的 な 誤 差 上 限 に 直 接 関 連 す る 残 差 の 計 算 の み に 適 宜 高 精 度 計 算 を 用 い た こ と に よ り 、 コ ス ト の 増 加 を 抑 え る こ と に 成 功 し 、 計 算 時 間 は 先 行 研 究 に よ る 手 法 と ほ ぼ 同 じ 時 間 で 実 行 で き る こ と が 示 さ れ て い る 。

第 3 章「J a v a に よ る 連 立 一 次 方 程 式 の 数 値 解 に 対 し 成 分 毎 に 高 精 度 な 誤 差 限 界 を 与 え る 精 度 保 証 法 」 で は 連 立 一 次 方 程 式 の 数 値 解 の 成 分 そ れ ぞ れ に 対 し て 誤 差 評 価 を 与 え る 手 法 が 構 築 さ れ て い る 。 第 ２ 章 で 述 べ た 手 法 は 連 立 一 次 方 程 式 の 数 値 解 が 持 つ 誤 差 に 対 し て ノ ル ム に よ る 高 精 度 な 誤 差 限 界 を 与 え る 手 法 で あ る が 、 解 の 絶 対 値 の 大 き さ に 差 が あ る と き に は 、 ノ ル ム に よ る 誤 差 限 界 は 絶 対 値 の 大 き な 解 の 誤 差 に 依 存 し て し ま う た め に 、 絶 対 値 の 小 さ な 解 に 対 し て は 良 い 誤 差 限 界 を 与 え る こ と は で き な い 。 ま た ス ケ ー リ ン グ 処 理 も あ る 程 度 以 上 の 絶 対 値 の 差 が あ る と き に は 有 効 で な い た め に 、精 度 保 証 式 を 拡 張 し 、適 宜 高 精 度 計 算 を 適 用 し て 、 数 値 解 の 成 分 そ れ ぞ れ に 対 し て 過 大 評 価 を 起 こ さ な い 精 度 保 証 法 を 開 発 す る こ と に 成 功 し て い る 。

第 4 章 「 計 算 幾 何 学 に 現 れ る 行 列 式 の 高 速 か つ ロ バ ス ト な 計 算 法 」 に つ い て は 、 計 算 幾 何 学 の 初 等 的 な 問 題 で あ る 点 と 平 面 の 位 置 関 係 を 判 定 す る 問 題 に 対 し て 難 し さ に 比 例 し た コ ス ト を か け る 手 法 が 構 築 さ れ て い る ． 通 常 の 浮 動 小 数 点 数 を 用 い た 数 値 計 算 で は 丸 め 誤 差 ・ 桁 落 ち 等 の 誤 差 が 発 生 す る た め に 、 点 と 平 面 の 位 置 関 係 が 間 違 え ら れ て 判 定 さ れ る こ と が あ る 。 こ の 問 題 を 解 決 す る た め に 、 最 近 開 発 さ れ た R u m p・O g i t a・O i s h i ら に よ る ベ ク ト ル の 総 和 を 高 精 度 に 計 算 す る 方 法 を 用 い る ． 行 列 式 の 計 算 は 誤 差 な く ベ ク ト ル の 総 和 に 変 換 す る こ と が で き る た め に 、 直 に 高 精 度 計 算 を 用 い る こ と も 可 能 で あ る が 、 行 列 式 か ら 生 成 さ れ る ベ ク ト ル の 総 和 は 特 別 な 構 造 を 持 ち 、 絶 対 値 の 差 が 大 き く 離 れ て い る こ と に 着 目 し 、 高 精 度 計 算 の 計 算 手 法 と の 関 連 を 整 理 し 、 必 要 な 部 分 の み を 計 算 す る よ う に ア ル ゴ リ ズ ム を 組 む こ と に よ り 高 速 な ア ル ゴ リ ズ ム の 開 発 に 成 功 し て い る 。 ま た 前 半 部 分 は S h e w c h u k の 適 応 的 な 手 法 を そ の ま ま 継 続 し て 用 い 、 問 題 が 簡 単 な と き に は 現 在 最 高 の 手 法 を 適 用 し 、 問 題 が 悪 条 件 な 場 合 に は 最 も 高 速 な 提 案 手 法 を 用 い る バ ラ ン ス の 良 い 形 式 で 構 築 さ れ て い る 。

第 5 章 「 結 論 」 で は 本 論 文 の ま と め と 結 論 が 記 さ れ て い る 。

研 究 業 績

種 類 別 題名、 発表・発行掲載誌名、 発表・発行年月、 連名者（申請者含む）

論文

論文

国 際 会 議 論文

国 際 会 議 論文

講演

講演

講演

講演

講演

講究録

国際会議

点と平面の位置関係を判定する高速かつロバストなアルゴリズム、応用数理学会 論文誌特集号 16:4、pp. 195-204、尾崎克久・荻田武史・S. M. Rump・大石進一。

A Method of Obtaining Verified Solutions for Linear Systems suited for Java, Journal of Computational and Applied Mathematics (special issue), 2007, pp.

337-344, K. Ozaki, T. Ogita, S. Miyajima, S. Oishi, S. M. Rump．(in press)

Fast Adaptive Algorithm of Geometric Predicates using Floating-Point Arithmetic、

12th GAMM - IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics (SCAN 2006), University of Duisburg-Essen, Duisburg, Germany, September, 2006, pp. 115-116, K. Ozaki, T. Ogita, S.M.Rump, S. Oishi．

Componentwise Verified Solutions of Linear Systems suited for Java, Proc. of 2005 International Symposium on Nonlinear Theory and its Applications, Bruges, Belgium, October, 2005, pp. 749-752, K. Ozaki, T. Ogita, S. Miyajima, S. Oishi, S. M . Rump．

点と平面の位置関係を判定する高速かつ適応的な手法について、数値解析シンポジウム ２００６、パナヒルズ大阪、2006 年 6 月、pp.5-8、尾崎克久・荻田武史・S.M.Rump・大 石進一。

入力誤差を含めた点と平面の位置関係を判定する高速なアルゴリズム、平成１８年応用 数理学会、研究部会連合発表会、早稲田大学、2006 年 3 月、尾崎克久・荻田武史・S.M.Rump・

大石進一。

高精度な内積計算の計算幾何学への応用、第３回計算数学研究会、兵庫県立淡路夢舞台 国際会議場、2006 年 1 月、尾崎克久・荻田武史・大石進一。

丸めモードを利用しない連立一次方程式の数値解の高速精度保証法, 研究集会「２１世 紀における数値解の新展開」、京大数理解析研究所、2004 年 11 月、荻田武史・尾崎克久・

S.M. Rump・大石進一。

Java による連立一次方程式のための精度保証法、日本応用数理学会年会、中央大学、2004 年 9 月、講演予稿集、pp.324-325、尾崎克久・荻田武史・宮島信也・大石進一。

Ｊａｖａによる連立一次方程式の数値解の精度保証法、京都大学数理解析研究所講究録 1441(2005)、pp. 75-88、尾崎克久・荻田武史・宮島信也・大石進一。

Adaptive Verification Method for Dense Linear Systems, International Symposium on Nonlinear Theory and its Applications (NOLTA2006), Bologna, Italy, September, 2006, pp. 323-326, K. Ozaki, T. Ogita, S. Oishi.

6

研 究 業 績

種 類 別 題名、 発表・発行掲載誌名、 発表・発行年月、 連名者（申請者含む）

国際会議

紀要

紀要

講演

講演

講演

著書

Fast Error Estimation for Eigenvalues of Symmetric Matrix without Directed Rounding, Proc. of 2004 International Symposium on Nonlinear Theory and its Application, Fukuoka, Japan, December, 2004, pp. 167-170, S. Miyajima, T. Ogita, K. Ozaki, S. Oishi．

Spherical Data and Ray Tracing in 4-dimensional Space, Proc. of The School of Science of Tokai University, March, 2004, pp.57-69, K. Ozaki, A. Koriyama．

球面法によるレイトレーシングとその応用、東海大学紀要理学部 第 38 巻、2003 年 3 月、

pp. 81-95、尾崎克久・郡山彬。

４次元空間における２次元オブジェクトの可視化について，日本シミュレーション学会 大会，中央大学，2006 年 6 月、pp. 73-76、尾崎克久・郡山彬・大石進一。

ポータブルかつ高精度な初等関数の精度保証付き数値計算とその応用、日本シミュレー ション学会大会、防衛大学校、2005 年 7 月、pp.193-196、発表論文集、尾崎克久・荻田 武史・大石進一。

交点判定簡略化レイトレーシング法による幾何学的授業について、教育システム情報学 会全国大会、香川大学、2004 年 8 月、講演論文集、pp.193-194、郡山彬・峯崎俊哉・尾 崎克久。

Java ではじめるレイトレーシング入門, 森北出版, 2005 年 5 月、郡山彬・原正雄・峯崎 俊哉・尾崎克久。

研 究 業 績

種 類 別 題名、 発表・発行掲載誌名、 発表・発行年月、 連名者（申請者含む）