On the Study of Symbolic-Numeric Computation Using Randomized and/or Approximation Algorithms

点击翻译按钮获取中文摘要

数値数式融合計算は信頼性の高い数式処理を基本とし、部分的に、柔軟で効率がよい数値計算を利用した、信頼性、柔軟性、効率性を合わせ持つ計算法である。その中でもとくに柔軟性を重視した、係数に誤差のある多項式などを対象とする計算法では、最近接問題という一種の最適化問題を解くことになるが、計算量が多いという問題点があった。これを解決するため、本研究は、数値数式融合計算アルゴリズムに乱択アルゴリズムや近似アルゴリズムを援用して計算量を削減し、効率性と柔軟性を持つ計算法を構築することを目的とする。研究は、実数体あるいは複素数体上の多項式などの連続的な問題と、有限体上の多項式などの離散的な問題に分けて扱う。本研究の目的を達成するため設定した課題は以下の通りである。課題１は最近接問題に対する従来の数値数式融合計算アルゴリズムの構築とその解析、課題２は乱択アルゴリズムや近似アルゴリズムを用いた数値数式融合計算アルゴリズムの構築とその解析、課題３は最近接問題の解についての理論的な解析である。本年度に得た主な成果は以下の通りである。課題１については、与えられた平面分割図形に近いボロノイ図を求める問題を考察する前段階として、母点が不明なマンハッタン距離によるボロノイ図から母点を求める問題に対しアルゴリズムを提案したこと、課題２については、与えられた多項式にハミング距離で一番近く合成で表現可能な多項式を求める問題に対し、多項式が一つの場合に、すでに構築した近似アルゴリズムを整理、拡張したこと、である。