Index Reduction for Differential-algebraic Equations with Mixed Matrices
Index Reduction for Differential-algebraic Equations with Mixed Matrices
复制标题
混合矩阵微分代数方程的指数约简
DOI：
10.1145/3341499
复制
发表时间：
2019
影响因子：
2.5
通讯作者：
Takamatsu Mizuyo
中科院分区：
文献类型：
--
作者：
Iwata Satoru;Oki Taihei;Takamatsu Mizuyo
微分代数方程（DAE）被广泛用于动态系统的建模。数值求解微分方程的难度是通过微分指数来衡量的。为了高精度地模拟动力系统，将高指标DAE转换为低指标DAE是很重要的。大多数现有的动力系统仿真软件包都配备了Mattsson和Söderlind给出的指数约简算法。不幸的是，如果存在数值抵消，这种算法就会失败，这些数值抵消通常是由结构方程中的精确常数引起的。为了将这些精确常数与代表物理量的通用参数区分开来，Murota和Iri引入了混合矩阵的概念，作为系统分析结构方法中忠实模型描述的数学工具。对于用混合矩阵描述的DAE，利用拟阵理论已经提出了一种计算指标的有效算法，本文针对系数矩阵为混合矩阵的线性DAE，提出了一种指标约简算法，包含物理量作为参数的线性DAE。我们的算法检测精确常数之间的数值抵消，并将DAE转换成一个等效的DAE，其中Mattsson-Söderlind的索引减少算法是适用的。我们的算法是基于组合松弛方法，这是一个框架来解决线性代数问题，通过迭代松弛成一个有效的可解的组合优化问题。该算法不依赖于符号操作，但在图和拟阵的快速组合算法。我们的算法被证明是工作的任何线性DAE的系数矩阵是混合矩阵。此外，我们提供了一个改进的算法的假设下，基于动力系统的维数分析。通过数值实验，它被证实，我们的算法运行足够快的大规模DAE和输出DAE的系数的物理意义是很容易解释。我们的算法也可以适用于非线性DAE的非线性项作为参数。
Differential-algebraic equations (DAEs) are widely used for the modeling of dynamical systems. The difficulty in numerically solving a DAE is measured by its differentiation index. For highly accurate simulation of dynamical systems, it is important to convert high-index DAEs into low-index DAEs. Most of the existing simulation software packages for dynamical systems are equipped with an index-reduction algorithm given by Mattsson and Söderlind. Unfortunately, this algorithm fails if there are numerical cancellations.These numerical cancellations are often caused by accurate constants in structural equations. Distinguishing those accurate constants from generic parameters that represent physical quantities, Murota and Iri introduced the notion of a mixed matrix as a mathematical tool for faithful model description in a structural approach to systems analysis. For DAEs described with the use of mixed matrices, efficient algorithms to compute the index have been developed by exploiting matroid theory.This article presents an index-reduction algorithm for linear DAEs whose coefficient matrices are mixed matrices, i.e., linear DAEs containing physical quantities as parameters. Our algorithm detects numerical cancellations between accurate constants and transforms a DAE into an equivalent DAE to which Mattsson–Söderlind’s index-reduction algorithm is applicable. Our algorithm is based on the combinatorial relaxation approach, which is a framework to solve a linear algebraic problem by iteratively relaxing it into an efficiently solvable combinatorial optimization problem. The algorithm does not rely on symbolic manipulations but on fast combinatorial algorithms on graphs and matroids. Our algorithm is proved to work for any linear DAEs whose coefficient matrices are mixed matrices. Furthermore, we provide an improved algorithm under an assumption based on dimensional analysis of dynamical systems. Through numerical experiments, it is confirmed that our algorithms run sufficiently fast for large-scale DAEs and output DAEs such that physical meanings of coefficients are easy to interpret. Our algorithms can also be applied to nonlinear DAEs by regarding nonlinear terms as parameters.