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

关于使用随机和/或近似算法的符号数值计算的研究

基本信息

批准号：
21K11760
负责人：
関川浩
金额：
$ 1.41万
依托单位：
Tokyo University of Science
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

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

数值公式融合计算以高可靠的数学公式处理为基础，部分利用灵活高效的数值计算，是一种集可靠性、灵活性、高效性为一体的计算方法。其中，特别注重灵活性和系数有误差的目标多项式的计算方法解决了一类称为最近邻问题的优化问题，但它们存在计算量大的问题。为了解决这一问题，本研究的目的是将随机选择算法和近似算法应用于数值公式融合计算算法，以减少计算量，构建高效、灵活的计算方法。研究分为连续问题（例如实数或复数域上的多项式）和离散问题（例如有限域上的多项式）。为实现本研究目的而设定的任务如下。任务1是最近邻问题的常规数值式融合计算算法的构造和分析，任务2是使用随机选择算法和近似算法的数值式融合计算算法的构造和分析，任务3是构造和分析最近邻问题的数值公式融合计算算法这是解决方法的理论分析。今年取得的主要成果如下。关于任务 1，作为考虑找到接近给定平面分割图的 Voronoi 图问题的初步步骤，我们提出了一种算法，用于从生成点未知的曼哈顿距离的 Voronoi 图中找到生成点的问题关于2，找到一个在汉明距离上最接近给定多项式并且可以用组合表示的多项式的问题是，当只有一个多项式时，对已经构建的近似算法进行组织和扩展。