research-article

Computing the Structural Index

Authors:

I. S. Duff,

C. W. GearAuthors Info & Claims

SIAM Journal on Algebraic Discrete Methods, Volume 7, Issue 4

Pages 594 - 603

https://doi.org/10.1137/0607066

Published: 01 October 1986 Publication History

Abstract

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.

References

[1]

C. W. Gear, L. R. Petzold, ODE methods for the solution of differential/algebraic systems, SIAM J. Numer. Anal., 21 (1984), 716–728

Digital Library

Google Scholar

[2]

K. Brenan, Masters Thesis, Stability and convergence of difference approximations for higher index differential/ algebraic equations with applications to trajectory Control, Ph.D. dissertation, Math. Dept., UCLA, Los Angeles, CA, 1983

Google Scholar

[3]

Stephen L. Campbell, The numerical solution of higher index linear time varying singular systems of differential equations, SIAM J. Sci. Statist. Comput., 6 (1985), 334–348

Digital Library

Google Scholar

[4]

P. Lotstedt, L. R. Petzold, The numerical solution of nonlinear differential equations arising with algebraic constraints, Sandia Report, SAND83-8877, Livermore, CA, 1983, Nov.

Google Scholar

[5]

I. S. Duff, On algorithms for obtaining a maximum transversal, ACM Trans. Math. Soft., 7 (1981), 315–330

Digital Library

Google Scholar

[6]

Richard F. Sincovec, Albert M. Erisman, Elizabeth L. Yip, Michael A. Epton, Analysis of descriptor systems using numerical algorithms, IEEE Trans. Automat. Control, 26 (1981), 139–147

Crossref

Google Scholar

[7]

T. F. Coleman, A. Pothen, The sparse null space basis problem, Report, TR 84-598, Dept. Comput. Sci., Cornell Univ., Ithaca, NY, 1984, July

Google Scholar

Cited By

View all

Pryce J(2022)A Simple Structural Analysis Method for DAEsBIT10.1023/A:102199862479941:2(364-394)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1023/A%3A1021998624799
Estévez Schwarz DLamour R(2018)A new approach for computing consistent initial values and Taylor coefficients for DAEs using projector-based constrained optimizationNumerical Algorithms10.1007/s11075-017-0379-978:2(355-377)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s11075-017-0379-9
Pryce JNedialkov NTan G(2015)DAESA—A Matlab Tool for Structural Analysis of Differential-Algebraic EquationsACM Transactions on Mathematical Software10.1145/268966441:2(1-20)Online publication date: 4-Feb-2015
https://dl.acm.org/doi/10.1145/2689664
Show More Cited By

Recommendations

An Efficient Structural Index for Graph-Structured Data
ICIS '08: Proceedings of the Seventh IEEE/ACIS International Conference on Computer and Information Science (icis 2008)

To speed up queries over XML and semi-structured data, a number of structural indexes have been proposed. The structural index is usually a labeled directed graph defined by partitioning nodes in the XML datagraph in to equivalence classes and storing ...
Comparison between the zeroth-order Randić index and the sum-connectivity index

The zeroth-order Randić index and the sum-connectivity index are very popular topological indices in mathematical chemistry. These two indices are based on vertex degrees of graphs and attracted a lot of attention in recent years. Recently Li and Li (...
An Efficient Structural Index for Branching Path Queries
WAIM '08: Proceedings of the 2008 The Ninth International Conference on Web-Age Information Management

Structural index, which acts as a schema, plays an important role in query optimization over XML and semi-structured data. On the basis of the Inter-Relevant Successive Trees (IRST), we extend IRST to the XML data graph, introduce the new equivalence ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Algebraic and Discrete Methods

SIAM Journal on Algebraic and Discrete Methods Volume 7, Issue 4

Oct 1986

140 pages

ISSN:0196-5212

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 October 1986

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Pryce J(2022)A Simple Structural Analysis Method for DAEsBIT10.1023/A:102199862479941:2(364-394)Online publication date: 11-Mar-2022
https://dl.acm.org/doi/10.1023/A%3A1021998624799
Estévez Schwarz DLamour R(2018)A new approach for computing consistent initial values and Taylor coefficients for DAEs using projector-based constrained optimizationNumerical Algorithms10.1007/s11075-017-0379-978:2(355-377)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.1007/s11075-017-0379-9
Pryce JNedialkov NTan G(2015)DAESA—A Matlab Tool for Structural Analysis of Differential-Algebraic EquationsACM Transactions on Mathematical Software10.1145/268966441:2(1-20)Online publication date: 4-Feb-2015
https://dl.acm.org/doi/10.1145/2689664
Lacroix MRidha Mahjoub AMartin S(2011)Combinatorial optimization model and MIP formulation for the structural analysis of conditional differential-algebraic systemsComputers and Industrial Engineering10.1016/j.cie.2010.12.00261:2(422-429)Online publication date: 1-Sep-2011
https://dl.acm.org/doi/10.1016/j.cie.2010.12.002
Lamour RMonett D(2011)A new algorithm for index determination in DAEs using algorithmic differentiationNumerical Algorithms10.1007/s11075-011-9455-858:2(261-292)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1007/s11075-011-9455-8
Iwata SShimizu R(2005)Combinatorial analysis of generic matrix pencilsProceedings of the 11th international conference on Integer Programming and Combinatorial Optimization10.1007/11496915_25(335-348)Online publication date: 8-Jun-2005
https://dl.acm.org/doi/10.1007/11496915_25
Reissig GMartinson WBarton P(2000)Differential--Algebraic Equations of Index 1 May Have an Arbitrarily High Structural IndexSIAM Journal on Scientific Computing10.1137/S106482759935385321:6(1987-1990)Online publication date: 1-Jan-2000
https://dl.acm.org/doi/10.1137/S1064827599353853
Raha SPetzold L(2000)Constraint Partitioning for Stability in Path-Constrained Dynamic Optimization ProblemsSIAM Journal on Scientific Computing10.1137/S106482750037239022:6(2051-2074)Online publication date: 1-Jun-2000
https://dl.acm.org/doi/10.1137/S1064827500372390
Iwata STarjan RWarnow T(1999)Computing the maximum degree of minors in matrix pencils via combinatorial relaxationProceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms10.5555/314500.314868(476-483)Online publication date: 1-Jan-1999
https://dl.acm.org/doi/10.5555/314500.314868
Iwata SMurota KSakuta I(1996)Primal-Dual Combinatorial Relaxation Algorithms for the Maximum Degree of SubdeterminantsSIAM Journal on Scientific Computing10.1137/091706417:4(993-1012)Online publication date: 1-Jul-1996
https://dl.acm.org/doi/10.1137/0917064
Show More Cited By

Abstract

References

Cited By

Recommendations

An Efficient Structural Index for Graph-Structured Data

Comparison between the zeroth-order Randić index and the sum-connectivity index

An Efficient Structural Index for Branching Path Queries

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations