Computing the structural index
Computing the structural index
复制标题
计算结构指数
DOI：
--
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
C. Gear
中科院分区：
文献类型：
--
作者：
I. Duff;C. Gear
许多差分/代数方程（DAE）的索引取决于系统的结构，即雅各布人的非零条目的模式。本文认为，如果其索引不超过两个，则可以通过向后分化方法来解决DAE的重要子类。因此，希望确定指数是否超过两个。在本文中，我们提出了一种算法，该算法仅基于结构确定索引是一个，两个或更高的算法。该算法在其执行时间内可能是指数级的：我们不知道是否有可能获得渐近算法的算法。但是，在许多实际问题中，该算法将在多项式时间内执行。
The index of many differential/algebraic equations (DAEs) is determined by the structure of the system, that is, by the pattern of nonzero entries in the Jacobians. This paper considers an important subclass of DAEs which can be solved by backward differentiation methods if their index does not exceed two. For this reason, it is desirable to determine whether the index exceeds two or not. In this paper we present an algorithm that determines if the index is one, two, or greater, based only on the structure. The algorithm can be exponential in its execution time: we do not know whether it is possible to get an asymptotically faster algorithm. However, in many practical problems, this algorithm will execute in polynomial time.