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
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-21K11760/
• 关键词: 数値数式融合計算; 近似アルゴリズム; 計算機代数; 計算幾何; 多項式の合成; ボロノイ図; 乱択アルゴリズム; 多項式; 方程式

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

Numerical value fusion calculation is based on reliability and high accuracy numerical value processing, partial reliability and flexibility, and numerical value calculation is based on reliability, flexibility and efficiency. The calculation method of the nearest problem is to solve an optimization problem. The calculation amount is to solve the problem. This study aims to reduce the computational complexity, flexibility, and flexibility of numerical fusion algorithms. This paper deals with the problem of polynomial continuity over complex prime fields and discrete polynomial continuity over finite fields. The purpose of this study is to achieve the following objectives: Topic 1: Analysis of the construction of the nearest numerical expression fusion calculation; Topic 2: Analysis of the construction of the nearest numerical expression fusion calculation; Topic 3: Analysis of the theory of the nearest numerical expression fusion calculation This year's main achievements are as follows: Problem 1: The first order and parent point are unknown. Problem 2: The second order and parent point are unknown. Problem 3: The second order and parent point are Polynomials are constructed in an approximate manner, arranged, expanded, and distributed.

项目成果

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

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

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

有限体上の多項式のdecomposition

有限域上多项式的分解

• 发表时间: 2022
• 作者: Kiyomi Masashi;Horiyama Takashi;Otachi Yota;関川浩
• 通讯作者: 関川浩

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

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

• 发表时间: 2021
• 作者: Ikeda Masahiro;Miyauchi Atsushi;Takai Yuuki;Yoshida Yuichi;Naoya Toriyabe and Takuya Kida;丹治春人，今堀慎治;Hiroshi Sekigawa
• 通讯作者: Hiroshi Sekigawa

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

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

• 发表时间: 2022
• 作者: 山中悠輔;武田渉;関川浩
• 通讯作者: 関川浩

メビウス変換の凸結合

莫比乌斯变换的凸组合

• 发表时间: 2020
• 作者: 若菜魁;関川浩
• 通讯作者: 関川浩