論 文 の 内 容 の 要 旨
論文題目 Computing Valuations of Determinants via Combinatorial
Optimization: Applications to Differential Equations
（組合せ最適化による行列式の付値計算：微分方程式への応用）
氏 名 大城 泰平
ABSTRACT
Degrees of determinants of polynomial matrices often appear as an algebraic
formulation of weighted combinatorial optimization problems. For example,
weighted Edmonds' problem (WEP), which is to compute the degree of the determinant
of a polynomial matrix having symbols, reduces to the weighted bipartite matching
problem and the weighted linear matroid intersection and parity problems depending
on symbols' pattern. Conversely, the degree of the determinant of an arbitrary
polynomial matrix serves as a lower bound on the maximum weight of a perfect
matching in the associated edge-weighted bipartite graph. Based on this relation,
the combinatorial relaxation algorithm of Murota (1995) computes the degree of
the determinant of a polynomial matrix by iteratively solving the weighted
bipartite matching problem.
The above property on degrees of determinants extends to valuations of
determinants of matrices over valuation fields, or more generally, to valuations
of the Dieudonné determinants of matrices over valuation skew fields. In
combinatorial optimization, valuations of the Dieudonné determinants arise from
a noncommutative version of WEP (nc-WEP). An algebraic abstraction of linear
differential and difference equations gives rise to skew polynomials, which are
a noncommutative generalization of polynomials. Valuations of Dieudonné
determinants of skew polynomial matrices provide information on dimensions of
solution spaces of linear differential and difference equations.
The combinatorial relaxation is of importance to preprocessing of
differential-algebraic equations (DAEs). In numerical analysis of DAEs,
consistent initialization and index reduction are necessary preprocessing prior
to the numerical integration. Popular preprocessing methods of Pantelides (1988),
Mattsson–Söderlind (1993), and Pryce (2001) are based on the assignment problem
on a bipartite graph that represents variable occurrences in equations. The
structural methods, however, fail for some DAEs due to inherent numerical or
symbolic cancellations. The combinatorial relaxation provides a framework of
modifying a DAE into another DAE to which the structural methods are applicable,
whereas modification method used in the framework should be appropriately chosen
according to the target DAEs.
In the first half of this thesis, we propose two algorithms for computing
valuations of the Dieudonné determinants of matrices over valuation skew fields.
The algorithms are extensions of the combinatorial relaxation of Murota and the
matrix expansion by Moriyama—Murota (2013), both of which are based on
combinatorial optimization. We show that the skew polynomials arise as the most
general algebraic structure to which these algorithms admit natural extensions.
Applications are presented for the nc-WEP and analysis of linear differential and
difference equations.
The last half of this thesis is devoted to DAEs' modification methods based
on the combinatorial relaxation. This thesis presents three methods for modifying
DAEs into other DAEs to which the preprocessing methods can be applied. One method
is for linear DAEs whose coefficient matrices are mixed matrices, which are
matrices having symbols representing physical quantities. We develop an efficient
algorithm that relies on graph and matroid algorithms but not on symbolic
computation. Other two deal with general nonlinear DAEs with the aid of symbolic
computation engines to manipulate nonlinear formulas. In addition to theoretical
guarantees, we conduct numerical experiments on real instances to present
practical efficiency.
VIEW FULL TEXT:
