離散最適化技法による行列束のロバスト数値計算とシステム解析への応用

使用离散优化技术对矩阵束进行鲁棒数值计算并应用于系统分析

• 批准号: 17760065
• 负责人: 岩田 覚
• 金额: $ 1.6万
• 依托单位: Kyoto University (2006-2007)The University of Tokyo (2005)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2005
• 资助国家: 日本
• 起止时间: 2005 至 2007
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17760065/
• 关键词: 行列束; Kronecker標準形; アルゴリズム; 組合せ緩和法; 微分代数方程式; 大規模システム; ロバスト計算; 組合せ最適化; 大規模疎行列

行列束のKronecker標準形は,微分代数方程式で記述される動的システムの解析において本質的な役割を果たしている.しかし,標準形の摂動に対する感度が非常に高く,計算誤差の発生しうる数値計算によって正確な標準形を得ることには困難を伴う.本研究課題では,計算誤差が発生し得ない組合せ的計算を利用することによって数値計算の負担を減らして,できるだけ正確な標準形を安定に計算する手法を確立することを目的としている.従来の研究の結果,Kronecker標準形の構造指数のうち,冪零指数に関して,2部グラフ上の最大重みマッチングを利用した組合せ緩和法が確立されている.本研究課題は,組合せ緩和法に基づいて行指数・列指数を計算するアルゴリズムの設計と計算機上での実現を目的としている.昨年度までの研究成果より,周期的な構造を有する2部グラフ上の最大マッチングを計算することによって,行指数・列指数の推定値が得られることが明らかとなった.本年度は,引き続き,組合せ緩和法の設計に取り組み,世界標準的なソフトであるGUPTRIで採用されているアルゴリズムよりも効率的な新たなアルゴリズムを得た.しかし,計算精度に関しては,GUPTRIの方が優れているため,現時点では,組合せ的な推定値とGUPTRIとを併用するのが,最も適切な計算法であるとの結論に達した.また,微分代数方程式の指数減少法への応用研究を行い,電気回路の数値解析手法として知られる混合解析の枠組みにおいて,最小指数を達成する微分代数方程式を導出する効率的なアルゴリズムを開発した.

矩阵捆绑包的Kronecker标准形式在分析由差分代数方程描述的动态系统中起着至关重要的作用。但是，标准形式对扰动的敏感性非常高，很难通过可能导致计算误差的数值计算获得准确的标准形式。该研究主题旨在通过利用无法产生计算错误的组合计算来减少数值计算的负担，并建立一种稳定计算标准形式尽可能准确的方法。已经针对Kronecker标准形式的组合零索引建立了先前的研究结果，目的是设计基于组合弛豫方法来计算行和柱索引的算法。直到去年的研究结果表明，可以通过计算具有周期性结构的两部分图上的最大匹配来获得对行和柱指数的估计。今年，我们继续致力于设计一种组合放松方法，并获得了一种比世界标准软件GUPTRI采用的算法更有效的新算法。但是，由于Guptri在计算准确性方面表现出色，因此我们得出的结论是，最合适的计算方法是与Guptri使用组合估计值。我们还对差分代数方程的指数还原方法进行了申请研究，并开发了一种有效的算法，该算法得出了差异代数方程，该方程在混合分析的框架中实现了最小指数，称为电气电路的数值分析方法。

项目成果

Computing the Inertia from Sign Patterns

根据符号模式计算惯性

• 发表时间: 2007
• 期刊: Mathematical Programming 110
• 作者: N.Kakimura;S.Iwata
• 通讯作者: S.Iwata

Submodular function minimization

• DOI: 10.1007/s10107-006-0084-2
• 发表时间: 2008-03-01
• 期刊: MATHEMATICAL PROGRAMMING
• 影响因子: 2.7
• 作者: Iwata, Satoru

A Strongly Polynomial Cut Canceling Algorithm for Minimum Cost Submodular Flow

最小成本子模流的强多项式割取消算法

• 发表时间: 2005
• 期刊: SIAM Journal on Discrete Mathematics 19
• 作者: S.Iwata;S.T.McCormick;M.Shigeno
• 通讯作者: M.Shigeno

Combinatorial Analysis on Singular Matrix Pencils

奇异矩阵铅笔的组合分析

• 发表时间: 2007
• 期刊: SIAM J. Matrix Analysis and Applications 29
• 作者: 呂中杰;田中皓一;西田政弘;Y. Shindo;Y. Shindo;Y.Shindo;Y.Shindo;S.Fang;Y.Shindo;Y.Shindo;S.Fang;F.Narita;F.Narita;F.Narita;Y. Shindo;F.Narita;F.Narita;Y.Shindo;F. Narita;S. Iwata and R. Shimizu
• 通讯作者: S. Iwata and R. Shimizu

RLC回路の混合解析における冪零指数の構造的特徴付け

RLC 电路混合分析中零功率指数的结构表征

• 发表时间: 2007
• 作者: J.F.Geelen;S.Iwata;高松瑞代 岩田覚
• 通讯作者: 高松瑞代 岩田覚