Development of linear solvers on max-plus algebra and its applications

max-plus代数线性求解器的开发及其应用

• 批准号: 19K03624
• 负责人: 福田 亜希子
• 金额: $ 2.83万
• 依托单位: Shibaura Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19K03624/
• 关键词: max-plus代数; 超離散化; 固有値; 超離散ハングリー戸田方程式; 超離散ハングリーロトカ・ボルテラ系; セルオートマトン; 超離散バーガース方程式; Max-plus代数; Kaczmarz法; ダイクストラ法; Min-plus代数; min-plus代数; 保存量; 最短経路問題; トロピカル代数; ネットワーク; 離散ハングリー戸田方程式; 量子ウォーク; max-plusウォーク; 可積分系; アルゴリズム

固有値計算のためのqd法やdLV法の漸化式は離散可積分系として有名な離散戸田方程式や離散ロトカ・ボルテラ系と一致するなど，高精度な固有値計算アルゴリズムと離散可積分系との興味深い関係が知られている。以前の研究において，これらを超離散化して得られる超離散戸田方程式および超離散ロトカ・ボルテラ系，またそれらの拡張であるI型超離散ハングリーロトカ・ボルテラ系およびI型超離散ハングリー戸田方程式がmin-plus代数上の固有値計算アルゴリズムとして解釈できることを明らかにしていた。2022年度はまず，上記のI型超離散ハングリー戸田方程式に関する成果を論文にまとめ，ソーティングアルゴリズムとの関連も再考し，現在，海外の論文誌に投稿中である。また，II型超離散ハングリー戸田方程式の行列表示や保存量，漸近挙動などの解析により，min-plus代数上のHessenberg行列の固有値を計算できることを明らかにした。さらに，I型超離散ハングリーロトカ・ボルテラ系とII型超離散ハングリー戸田方程式が対象としている行列の固有値同士の関係も明らかにしている。これらの成果は日本応用数理学会2022年度年会にて発表している。一方，交通流モデルと解釈できるエレメンタリーセルオートマトンのルール184は超離散バーガース方程式で表現できることが知られている。コール・ホップ変換を通して関連するランダムウォークを相関付きランダムウォークに拡張することで新たな交通流モデルの導出に成功しており，研究成果をまとめた論文がJournal of Difference Equations and Applications誌に掲載されている。また，本研究課題の主要なテーマであるmax-plus代数に関する入門的な教科書として知られる洋書「max-plus at work」の翻訳を行い，2022年12月に「max-plus代数とその応用」として出版されている。

The eigenvalues are calculated by the qd method and the dLV method, and the discrete integratable system is calculated by the well-known discrete equations and the discrete integratable system is calculated by the high-precision eigenvalues. In the previous research, the hyperdiscrete equations were obtained from hyperdiscrete equations and hyperdiscrete systems. The hyperdiscrete equations were obtained from hyperdiscrete systems. In 2022, the results of the above-mentioned I-type hyperdiscrete equations were reexamined. Now, the overseas papers are being submitted. Type II hyperdiscrete equations are expressed in terms of preserving quantities, asymptotic motion, and resolution, and the eigenvalues of Hessenberg arrays on min-plus algebras are calculated. In this paper, the type I hyperdiscrete equations are compared with the type II hyperdiscrete equations. The results were presented at the 2022 Annual Meeting of the Japan Applied Mathematics Society. On the other hand, the traffic flow is expressed in terms of hyperdiscrete equations. The results of this study were published in the Journal of Difference Equations and Applications. The main topic of this study is the translation of the textbook "max-plus at work", which was published in December 2022.

项目成果

相関付きランダムウォークから導かれる超離散バーガースセルオートマトン

从相关随机游走导出的超离散 Burgers 元胞自动机

• 发表时间: 2021
• 作者: 渡邉 扇之介;福田 亜希子;瀬川 悦生
• 通讯作者: 瀬川 悦生

Computation of min-plus eigenvalues via ultradiscrete integrable systems

通过超离散可积系统计算最小加特征值

• 发表时间: 2019
• 作者: Akiko Fukuda;Sennosuke Watanabe;Masafumi Kan
• 通讯作者: Masafumi Kan

Max-plusウォーク ～超離散版量子ウォークの構築～

Max-plus walk ~超离散量子行走的构建~

• 发表时间: 2019
• 作者: 渡邉 扇之介;福田 亜希子;瀬川 悦生;佐藤 巌
• 通讯作者: 佐藤 巌

Traffic flow models with two kinds of vehicles in terms of the vector-valued cellular automata and their fuzzification

两种车辆的向量值元胞自动机交通流模型及其模糊化

• 发表时间: 2022
• 期刊: AIP Conference Proceedings
• 作者: Yuki Nishida;Sennosuke Watanabe;Akiko Fukuda and Yoshihide Watanabe
• 通讯作者: Akiko Fukuda and Yoshihide Watanabe

超離散可積分系と min-plus 代数上の固有値計算

超离散可积系统的特征值计算和最小加代数

• 发表时间: 2021
• 作者: 齋藤元気;福田 亜希子;渡邉扇之介;福田 亜希子
• 通讯作者: 福田 亜希子