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代数とその応用」として出版されている。

qd方法和dLV方法计算特征值的递推公式与众所周知的离散可积系统的离散Toda方程和离散Lotka-Volterra系统一致，这是之间关系的一个有趣的例子高精度特征值计算算法和离散可积系统是已知的。在之前的研究中，我们已经证明了超离散Toda方程和超离散Lotka-Volterra系统，以及它们的扩展，I型超离散Hungry Lotka-Volterra系统和I-型超离散Hungry Lotka-Volterra系统。式超离散Hungry Toda方程，被阐明可以将其解释为负代数上的特征值计算算法。 2022年，我们将首先将I型超离散Hungry Toda方程相关的结果编译成论文，重新考虑与排序算法的关系，目前正在提交给海外期刊。此外，我们证明了通过分析II型超离散Hungry Toda方程的矩阵表示、守恒量和渐近行为，可以计算最小加代数上的Hessenberg矩阵的特征值。此外，还阐明了I型超离散Hungry-Lotka-Volterra系统所覆盖的矩阵特征值与II型超离散Hungry-Toda方程之间的关系。这些结果将在日本应用数学学会 2022 年年会上公布。另一方面，众所周知，基本元胞自动机184的规则可以解释为交通流模型，可以用超离散Burgers方程来表达。我们通过呼叫跳变换将相关随机游走扩展到相关随机游走，成功推导了一种新的交通流模型，并在《Journal of Difference Equations and Applications There is》上发表了一篇总结研究成果的论文。此外，我们还将翻译作为本研究项目主题的Max-Plus代数入门教材外文书籍《Max-Plus at Work》，并将出版《Max-Plus代数及其应用程序”于 2022 年 12 月发布。

项目成果

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

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

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

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

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

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

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

Computation of min-plus eigenvalues via ultradiscrete integrable systems

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

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

Fuzzy cellular automata with complete number-conserving rule as traffic-flow models with bottleneck

具有完全数守恒规则的模糊元胞自动机作为具有瓶颈的交通流模型

• DOI: 10.14495/jsiaml.14.143
• 发表时间: 2022
• 期刊: JSIAM Letters
• 影响因子: 0.4
• 作者: Nishida Yuki;Watanabe Sennosuke;Fukuda Akiko;Yanagisawa Daichi
• 通讯作者: Yanagisawa Daichi