Polynomial cost for solving IVP for high-index DAE
Abstract
We show that the cost of solving initial value problems for high-index differential algebraic equations is polynomial in the number of digits of accuracy requested. The algorithm analyzed is built on a Taylor series method developed by Pryce for solving a general class of differential algebraic equations. The problem may be fully implicit, of arbitrarily high fixed index and contain derivatives of any order. We give estimates of the residual which are needed to design practical error control algorithms for differential algebraic equations. We show that adaptive meshes are always more efficient than non-adaptive meshes. Finally, we construct sufficiently smooth interpolants of the discrete solution.
References
[1]
E. L. Allgower and K. Georg, Introduction to Numerical Continuation Methods, SIAM, Philadelphia, 2003.
[2]
U. Ascher and L. Petzold, Computer Methods for ODE and DAE, SIAM, Philadelphia, 1998.
[3]
R. Barrio, Performance of the Taylor series methods for ODEs/DAEs, Appl. Math. Comput., 163(2) (2005), pp. 525–545.
[4]
R. Barrio, F. Blesa, and M. Lara, VSVO formulation of the Taylor method for the numerical solution of ODEs, Comput. Math. Appl., 50(1–2) (2005), pp. 93–111.
[5]
A. Ben-Israel and T. N. E. Greville, Generalized Inverses, Theory and Applications, Wiley-Interscience, New York, 1974.
[6]
J. C. Butcher, The Numerical Analysis of Ordinary Differential Equations, John Wiley & Sons Ltd., Chichester, 1987.
[7]
É. Cartan, Les systémes différentiels extérieurs et leur applications géométriques, Hermann, Paris, 1945.
[8]
R. M. Corless, Error backward, Chaotic Numerics, AMS Contemporary Mathematics Series, 172 (1994), pp. 31–62.
[9]
R. M. Corless, An elementary solution of a minimax problem arising in algorithms for automatic mesh selection, SIGSAM Bull.: Commun. Comput. Algebra, 34(4) (2001), pp. 7–15.
[10]
R. M. Corless, A new view of the computational complexity of IVP for ODE, Numer. Algorithms, 31 (2002), pp. 115–124.
[11]
G. Corliss and Y. F. Chang, Solving ordinary differential equations using Taylor series, ACM Trans. Math. Softw., 8(2) (1982), pp. 114–144.
[12]
A. Douglis and L. Nirenberg, Interior estimates for elliptic systems of partial differential equations, Commun. Pure Appl. Math., 8 (1955), pp. 503–538.
[13]
W. H. Enright, A new error control for initial value solvers, Appl. Math. Comput., 31 (1989), pp. 288–301.
[14]
W. H. Enright, K. R. Jackson, S. P. Norsett, and P. G. Thomsen, Interpolants for Runge–Kutta formulas, ACM Trans. Math. Softw., 12(3) (1986), pp. 193–218.
[15]
I. Gladwell, L. F. Shampine, L. S. Baca, and R. W. Brankin, Practical aspects of interpolation in Runge–Kutta codes, SIAM J. Sci. Stat. Comput., 8(3) (1987), pp. 322–341.
[16]
A. Griewank, Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, Frontiers in Applied Mathematics, SIAM, Philadelphia, PA, 2000.
[17]
E. Hairer, S. P. Nørsett, and G. Wanner, Solving Ordinary Differential Equations I, Comput. Math., vol. 8, Springer, Berlin, 1987.
[18]
E. Hairer and G. Wanner, Solving Ordinary Differential Equations II, Comput. Math., vol. 14, Springer, Berlin, 1991.
[19]
J. Hoefkens, M. Berz, and K. Makino, Efficient high-order methods for ODEs and DAEs, in: G. F. Corliss et al., eds., Automatic Differentiation: From Simulation to Optimization, Springer, New York, 2001, 343–350.
[20]
J. van der Hoeven, Fast evaluation of holonomic functions, Theor. Comput. Sci., 210 (1999), pp. 199–215.
[21]
S. Ilie, Computational complexity of numerical solutions of initial value problems for differential algebraic equations, PhD thesis, University of Western Ontario, 2005.
[22]
S. Ilie, R. M. Corless, and G. Reid, Numerical solutions of index-1 differential algebraic equations can be computed in polynomial time, Numer. Algorithms, 41(2) (2006), pp. 161–171.
[23]
S. Ilie, G. Söderlind, and R. M. Corless, Adaptivity and computational complexity in the numerical solution of ODEs, J. Complexity (in press).
[24]
K. R. Jackson and N. Nedialkov, Some recent advances in validated methods for IVPs for ODEs, Appl. Numer. Math., 42(1) (2002), pp. 269–284.
[25]
M. Janet, Leçons sur les systèmes d’équations aux dérivées partielles, Gauthier-Villars, Paris, 1929.
[26]
R. E. Moore, Interval Analysis, Prentice Hall, Englewood Cliffs, New York, 1966.
[27]
N. S. Nedialkov, private communication.
[28]
N. S. Nedialkov and J. D. Pryce, Solving differential-algebraic equations by Taylor series (I): computing Taylor coefficients, BIT, 45(3) (2005), pp. 561–591.
[29]
C. Pantelides, The consistent initialization of differential-algebraic systems, SIAM J. Sci. Stat. Comput., 9(2) (1988), pp. 213–231.
[30]
J. D. Pryce, Solving high-index DAEs by Taylor series, Numer. Algorithms, 19 (1998), pp. 195–211.
[31]
J. D. Pryce, A simple structural analysis method for DAEs, BIT, 41(2) (2001), pp. 364–394.
[32]
J. D. Pryce, private communication.
[33]
L. B. Rall, Automatic Differentiation: Techniques and Applications, Springer, Berlin, 1981.
[34]
C. Riquier, Les systémes d’équations aux dérivées partielles, Gautier-Villars, Paris, 1910.
[35]
G. Söderlind, Automatic control and adaptive time-stepping, Numer. Algorithms, 31 (2002), pp. 281–310.
[36]
A. G. Werschulz, The Computational Complexity of Differential and Integral Equations, Oxford Science, Oxford, 1991.
[37]
W. Wu and G. Reid, Symbolic-numeric computation of implicit Riquier bases for PDE, Proc. of ISSAC 2007, ACM (2007), pp. 377–386.
[38]
W. Wu, G. Reid, and S. Ilie, Implicit Riquier bases for PDAE and their discretizations, (submitted).
Recommendations
An Hermite-Obreschkoff method for stiff high-index DAE
AbstractWe have developed an implicit Hermite-Obreschkoff method for the numerical solution of stiff high-index differential-algebraic equations (DAEs). On each integration step, this method requires the computation of Taylor coefficients and their ...
On implicit Euler for high-order high-index DAEs
The Implicit Euler method is seldom used to solve differential-algebraic equations (DAEs) of differential index r ≥ 3, since the method in general fails to converge in the first r - 2 steps after a change of stepsize. However, if the differential ...
Solving differential-algebraic equations by Taylor series (II): Computing the System Jacobian
AbstractThe authors have developed a Taylor series method for solving numerically an initial-value problem differential-algebraic equation (DAE) that can be of high index, high order, nonlinear, and fully implicit, BIT, 45 (2005), pp. 561–592. Numerical ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2008 Springer Science + Business Media B.V.
Publisher
BIT Computer Science and Numerical Mathematics
United States
Publication History
Published: 01 March 2008
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in