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是对最近概率的求解方案分析的理论分析。 The main results obtained this year are as follows: As a preliminary step to considering the problem of finding a Voronoi diagram close to a given planar division figure, we proposed an algorithm for the problem of finding a Voronoi diagram with a Manhattan distance whose mother points are unknown, and for Problem 2, we organize and extend the approximate algorithm that has already been constructed when there is one polynomial, in the case of one多项式，对于找到可以在最近的锤距离距离表示的多项式问题的问题。

项目成果

期刊论文数量（8）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

合成で表現可能な最近接多項式

可以用组合表示的最接近多项式

DOI：
发表时间：
2023
期刊：
数式処理
影响因子：
0
作者：
Shin Funada;Jun Suzuki;伊賀捺津美，佐藤豊展，柴本　勇;関川浩
通讯作者：
関川浩

有限体上の多項式のdecomposition

有限域上多项式的分解

DOI：
发表时间：
2022
期刊：
影响因子：
0
作者：
Kiyomi Masashi;Horiyama Takashi;Otachi Yota;関川浩
通讯作者：
関川浩

The nearest function represented by a convex combination of given functions with constraints

由给定函数与约束的凸组合表示的最接近函数

DOI：
发表时间：
2021
期刊：
影响因子：
0
作者：
Ikeda Masahiro;Miyauchi Atsushi;Takai Yuuki;Yoshida Yuichi;Naoya Toriyabe and Takuya Kida;丹治春人，今堀慎治;Hiroshi Sekigawa
通讯作者：
Hiroshi Sekigawa

マンハッタン距離ボロノイ図の母点探索

曼哈顿距离 Voronoi 图的生成点搜索