Numerical simulation has established a position as a vital technique in the analysis of physical phenomena. Physical phenomena that arise in the real world are modeled by large-scale systems, whose simulation becomes possible with the recent development of computers. A further issue in numerical simulation is accuracy improvement.

In numerical simulation, we generate a mathematical model for the target phenomenon, and then apply numerical solution methods to it. In order to improve accuracy of numerical simulation, a great deal of research has been made on numerical solution methods. However, accuracy depends not only on "how to solve" but also on "what to solve." The same physical phenomenon admits a variety of mathematical models. Even if they are mathematically equivalent, they may differ in the ease of numerical solutions. Thus, it is important to adopt an "optimal mathematical model" in view of accuracy of numerical solutions. By applying efficient numerical solution methods to this optimal model, we anticipate achieving high accuracy in numerical simulation.

The aim of this thesis is to establish a systematic way of deriving an optimal model in circuit simulation. Lumped circuits in the time domain are described by differential-algebraic equations (DAEs), which consist of algebraic equations and differential operations. In the theory of DAEs, the inherent numerical difficulty of a DAE is measured by the index. The greater the index is, the more difficult it is to solve the DAE. In order to improve accuracy of numerical solution, we present algorithms for finding a DAE formulation with minimum index in the hybrid analysis, which is a circuit analysis method having a wide variety of variable selections. We further prove that the index of the DAE is determined only by the network structure of a circuit, that is, the index remains the same if we change physical characteristic values. This shows robustness of the obtained mathematical model, which is an important property for modeling.

The key tool in the analysis of DAEs is the degrees of subdeterminants in a polynomial matrix, which are known to form a valuated matroid. The polynomial matrix we deal with has two kinds of nonzero coefficients: fixed constants that account for conservation laws and independent parameters that represent physical characteristics. Such a matrix has been introduced as a mixed polynomial matrix. Our analysis on mixed polynomial matrices leads to improvement in efficiency of the index minimization/determination algorithms.

The viewpoint of matroids is helpful in grasping structure of the problem and capturing the essence. This enables us to make full use of structural information of the problem. Moreover, the effective application of matroid theory leads to efficient algorithms, which makes it possible to deal with large-scale systems.

In large-scale systems analysis, selecting a smart mathematical model plays a more and more significant role. This thesis shows the utility of matroid theory in the optimal DAE modeling.

大規模集積回路に代表される複雑な大規模システムの設計において、数値シミュレーションの重要性は言を俟たない。高精度の数値シミュレーションを実現するためには、高性能数値解法を開発するだけでなく、現象を的確に捉えたモデルを作る必要がある。対象となるシステムが複雑で大規模なものになればなるほど、モデル化の巧拙が精度に及ぼす影響は、ますます大きくなる傾向にある。それゆえに、多種多様な可能性の中から最適なモデルを導出するための体系的な研究が求められている。

本論文は、回路シミュレーションにおいて、現在広く利用されている修正節点解析で導出される微分代数方程式よりも、古典的な混合解析で導出される微分代数方程式の方が数値的な解き難さの指標である指数が悪くならないことを示すとともに、最小指数の最適混合解析を導出する効率的なアルゴリズムを提案するものである。特に、マトロイド理論や組合せ最適化手法を駆使して、効率的なアルゴリズムを設計している点が、本論文の特色である。

本論文は、「Optimal Modeling for Circuit Simulation: Applications of Matroid Theory」(回路シミュレーションにおける最適モデリング:マトロイド理論の応用)と題して、9章からなる。

第1章「Introduction」(序論)では、シミュレーションにおけるモデル化の役割から説き起こして、最適モデリングの考え方を述べるとともに、回路解析や動的システムにおけるマトロイド理論の既存の応用研究を概括した後に、本論文の成果を概説している。

第2章「Matrices, Matroids, and Mixed Matrices」(行列、マトロイド、混合行列)では、組合せ的行列理論やマトロイド理論に関する数学的な準備を与えている。特に、行列束のクロネッカー標準形、固定定数と独立パラメータの両方を含む混合行列と、その多項式版に当たる混合多項式行列の解析に利用される付値マトロイドの理論を詳述している。

第3章「Theory of Differential-Algebraic Equations」(微分代数方程式の理論)では、微分代数方程式の数値的な解き難さの指標となる各種の指数を定義した後、回路解析に現れる特徴的な微分方程式のクラスに限定して指数を特徴付ける既存研究を紹介している。

第4章「Index Reduction for Linear DAEs with Constant Coefficients」(定数係数線形微分代数方程式の指数減少法)では、各方程式の中に微分が高々1箇所しか現れない微分代数方程式に対して、指数を1だけ減少させる方法を提案している。この手法を回路方程式に直接適用した場合の数値例も示されている。

第5章「Hybrid Analysis for Linear Time-Invariant Circuits」(線形時不変回路の混合解析)では、線形時不変回路の混合解析の手続きを詳述した後に、最小指数の混合解析を導出する効率的なアルゴリズムを提案している。混合解析には、回路素子を二種類に分割する自由度と参照する全域木を選ぶ自由度があり、分割と全域木を定めると、混合方程式と呼ばれる数値的に解くべき微分代数方程式が導出される。本章では、混合方程式の指数が全域木の選択には依らないことを示すとともに、様々な分割法の中で、最小指数の混合方程式を導出する分割法を見出す効率的なアルゴリズムを与えている。さらに、修正節点方程式と比較して、混合方程式の指数は大きくならないことを証明している。特に、RLC回路に限定した場合、混合方程式の指数が高々1となることも証明されている。これは、指数が2になり得る修正節点解析と比較して、数値計算精度における混合解析の優位性を示唆する結果である。

第6章「Hybrid Analysis for Nonlinear Time-Varying Circuits」(非線形時変回路の混合解析)では、従属電源をも含む非線形時変回路において、混合方程式の指数が1となるために回路の満たす必要十分条件、ならびに0となるために分割の満たす必要十分条件を示している。その結果、非線形時変RLC回路においても、混合方程式の指数が高々1となることが導かれる。非線形時変回路の修正節点解析と混合解析の数値計算例も示されている。

第7章「Degrees of All Cofactors in Mixed Polynomial Matrices」(混合多項式行列の全余因子の次数)では、混合多項式行列において、行列式の次数を計算するのと同程度の時間で、全ての余因子の次数を同時に計算する方法を示している。この手法は、第5章で提案した最小指数混合解析を導出するアルゴリズムを格段に効率化している。

第8章「Kronecker Canonical Forms of Mixed Matrix Pencils」(混合行列束のクロネッカー標準形)では、混合行列の行列束版に当たる混合行列束のクロネッカー標準形において、冪零指数の計算を独立マッチング問題に帰着できることを示している。

最後に、第9章「Conclusion」(結論)では、本論文の成果を纏めると同時に、混合解析に関する諸結果の拡張や行列束のクロネッカー標準形の組合せ的特徴付けなど、今後の研究課題が提起されている。

以上を要するに、本論文の成果は、数値シミュレーションのための最適モデリングという新たな問題意識を提起した独創性の高い研究であり、数理情報学の発展に大きく貢献するものである。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。