From: Petr Kuzmic Subject: Re: What algorithm uses DDASSL? Date: Fri, 18 Aug 2000 10:02:19 -0500 Newsgroups: sci.math.num-analysis Summary: [missing] David Schaich wrote: [...] > > says it all. > > The source code is extremely well documented. > > Thank you for that link! > > I just wonder, why I can not find the name of L. Petzold and/ > or DDASSL in any of my numeric math books. Is DDASSL so old? Or > forgotten? Well, my take on this is that DDASSL is a little too specialized to be found in textbooks. It's not just the question of stiff / nonstiff ODE systems, which is usually covered in books and review articles. DDASSL goes beyond the stiff / nonstiff problem, because it is [D]ifferential-[A]lgebraic [S]ystem [S]olver, so the technical and mathematical problems multiply (I think Petzold's main line of research is into stability of mixed differential / algebraic systems; haven't looked for a few years though). As far as DDASSL being old, that depends on one's perspective. I believe the Technical Report describing DDASSL was published in 1983 or so. Does this mean it is obsolete? Herr Professor Gauss published his work several years before Napoleon had the brilliant idea to conquer Moscow, but we still use least-squares regression today. By the way, in 1991 Petzold received the first ever Wilkinson Award for DDASSL: . I don't know if DDASSL is "forgotten". I certainly remember it [;)]. HTH, -- Petr _____________________________________________________________________ P e t r K u z m i c, Ph.D. mailto:pkuzmic@biokin.com BioKin Ltd. * Software and Consulting http://www.biokin.com ============================================================================== From: David Schaich Subject: Re: What algorithm uses DDASSL? Date: Fri, 18 Aug 2000 17:58:27 +0200 Newsgroups: sci.math.num-analysis Petr Kuzmic wrote: > Well, my take on this is that DDASSL is a little too specialized to be > found in textbooks. > It's not just the question of stiff / nonstiff ODE systems, which is > usually covered in books and review articles. DDASSL goes beyond the > stiff / nonstiff problem, because it is [D]ifferential-[A]lgebraic > [S]ystem [S]olver, so the technical and mathematical problems multiply > (I think Petzold's main line of research is into stability of mixed > differential / algebraic systems; haven't looked for a few years > though). OK, this brings me back to my original question: Of course, it is a very sophisticated solver. My question aimed at: What approach, e.g. Gear, Rosenbrock, etc, forms the basis for "the backward differentiation formulas of orders one through five to solve a system" (citation dassl-webpage) ? Or is it an original approach from ground up? (which I do not believe) > As far as DDASSL being old, that depends on one's perspective. I > believe the Technical Report describing DDASSL was published in 1983 or > so. Does this mean it is obsolete? Herr Professor Gauss published his > work several years before Napoleon had the brilliant idea to conquer > Moscow, but we still use least-squares regression today. By the way, in > 1991 Petzold received the first ever Wilkinson Award for DDASSL: > . I did not mean that serious, the point is, I used this algorithm for quite a while (it worked well!) and never knew, how it works. And while looking in my numeric books, I could not find it. That leat to my question. Greetings, David PS: I just looked in my old ACSL-manual - and there is a short description of it! ... The basic idea for solving the DAE system using numerical ODE methods originating with Gear, is to replace the derivative in equation by a difference approximation and then solve the resulting system for the solution an the current time by using Newton's method. Replacing the derivative by the first order backward difference, we obtain the explicit Euler formula: F( y_{n+1} , (y_{n+1}y_{n})/h_{n+1} , t_{n+1}) = 0 with h_{n+1} = t_{n+1} - t_{n} The nonlinear system is then solved for y_{n+1} using a variant of Newton's method. DASSL uses a fixed leading coefficient implementation of the BDF formula which can approximate the derivative to higher accuracy at higher orders. ... ============================================================================== From: Radu Serban Subject: Re: What algorithm uses DDASSL? Date: Fri, 18 Aug 2000 09:27:26 -0700 Newsgroups: sci.math.num-analysis David Schaich wrote: > Petr Kuzmic wrote: > > Well, my take on this is that DDASSL is a little too specialized to be > > found in textbooks. > > It's not just the question of stiff / nonstiff ODE systems, which is > > usually covered in books and review articles. DDASSL goes beyond the > > stiff / nonstiff problem, because it is [D]ifferential-[A]lgebraic > > [S]ystem [S]olver, so the technical and mathematical problems multiply > > (I think Petzold's main line of research is into stability of mixed > > differential / algebraic systems; haven't looked for a few years > > though). > > OK, this brings me back to my original question: Of course, it is a > very sophisticated solver. My question aimed at: What approach, e.g. > Gear, Rosenbrock, etc, forms the basis for > "the backward differentiation formulas of > orders one through five to solve a system" (citation dassl-webpage) ? > > Or is it an original approach from ground up? (which I do not believe) > > > As far as DDASSL being old, that depends on one's perspective. I > > believe the Technical Report describing DDASSL was published in 1983 or > > so. Does this mean it is obsolete? Herr Professor Gauss published his > > work several years before Napoleon had the brilliant idea to conquer > > Moscow, but we still use least-squares regression today. By the way, in > > 1991 Petzold received the first ever Wilkinson Award for DDASSL: > > . > > I did not mean that serious, the point is, I used this algorithm for quite > a while (it worked well!) and never knew, how it works. And while looking > in my numeric books, I could not find it. That leat to my question. > > Greetings, > > David > > PS: > I just looked in my old ACSL-manual - and there is a short description > of it! > ... The basic idea for solving the DAE system using numerical ODE methods > originating with Gear, is to replace the derivative in equation by a > difference approximation and then solve the resulting system for the > solution an the current time by using Newton's method. Replacing the > derivative by the first order backward difference, we obtain the explicit > Euler formula: > F( y_{n+1} , (y_{n+1}y_{n})/h_{n+1} , t_{n+1}) = 0 > > with h_{n+1} = t_{n+1} - t_{n} > > The nonlinear system is then solved for y_{n+1} using a variant of Newton's > method. DASSL uses a fixed leading coefficient implementation of the > BDF formula which can approximate the derivative to higher accuracy > at higher orders. ... The best place for a description of DASSL is the book: "Numerical Solution of Initial-Value Problems in Differential-Algebraic Equations," K.E. Brenan, S.L. Campbell, and L.R. Petzold, Siam, Philadelphia, 1996 ISBN 0-89871-353-6 Linda is now at UCSB: http://www.engineering.ucsb.edu/me/dept_site/people/faculty_pages/petzold/index.html http://www.engineering.ucsb.edu/~cse/ You can download from there the new DAE solver DASPK. --Radu -- Radu Serban Department of Mechanical Engineering University of California Santa Barbara, Ca 93106 Phone: (805) 893-5728 Fax: (805) 893-5435 radu@engineering.ucsb.edu http://www.engineering.ucsb.edu/~radu ============================================================================== From: Petr Kuzmic Subject: Re: What algorithm uses DDASSL? Date: Fri, 18 Aug 2000 11:27:29 -0500 Newsgroups: sci.math.num-analysis David Schaich wrote: > OK, this brings me back to my original question: Of course, it is a > very sophisticated solver. My question aimed at: What approach, e.g. > Gear, Rosenbrock, etc, forms the basis for > "the backward differentiation formulas of > orders one through five to solve a system" (citation dassl-webpage) ? > > Or is it an original approach from ground up? (which I do not believe) I am not an expert in numerical mathematics, just an amateur using numerical methods to solve problems in my application area ([bio]chemical kinetics and such). However, in trying to understand what DDASSL does (some years ago I had the very same question that you have now!) I went to the library and looked around, and I noticed that Petzold had to solve a lot of original problems. So yes, it would appear that some of the components of DDASSL had to be invented (more or less) "from ground up". Here is some papers you can look at to see what I mean. DIFFERENTIAL-ALGEBRAIC EQUATIONS ARE NOT ODES PETZOLD L SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING 3: (3) 367-384 1982 Cited References: 13 Times Cited: 143 AUTOMATIC SELECTION OF METHODS FOR SOLVING STIFF AND NONSTIFF SYSTEMS OF ORDINARY DIFFERENTIAL-EQUATIONS PETZOLD L SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING 4: (1) 136-148 1983 Cited References: 11 Times Cited: 104 NUMERICAL-SOLUTION OF NONLINEAR DIFFERENTIAL-EQUATIONS WITH ALGEBRAIC CONSTRAINTS .1. CONVERGENCE RESULTS FOR BACKWARD DIFFERENTIATION FORMULAS LOTSTEDT P, PETZOLD L MATHEMATICS OF COMPUTATION 46: (174) 491-516 APR 1986 Cited References: 27 Times Cited: 55 NUMERICAL-SOLUTION OF NONLINEAR DIFFERENTIAL-EQUATIONS WITH ALGEBRAIC CONSTRAINTS .2. PRACTICAL IMPLICATIONS PETZOLD L, LOTSTEDT P SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING 7: (3) 720-733 JUL 1986 Cited References: 21 Times Cited: 38 Hope that helps, - Petr _____________________________________________________________________ P e t r K u z m i c, Ph.D. mailto:pkuzmic@biokin.com BioKin Ltd. * Software and Consulting http://www.biokin.com ============================================================================== From: martin.kahlert@keksy.muc.infineon.com (Martin Kahlert) Subject: Re: Difference implicit/explicit integrators? Date: 18 Aug 2000 15:07:13 GMT Newsgroups: sci.math.num-analysis In article <399D3F60.84847651@mailszrz.zrz.tu-berlin.de>, David Schaich writes: > > ... or to be more precise: Why are implicit algorithms better > with stiff systems? Look at this ODE: y' = -a*y, y(0) = 1, a>0 using n steps to calculate y(1): explicit Euler: y_{k+1} = y_k - a/n * y_k ==> y_{k+1} = (1-a/n)*y_k ==> y_k = (1-a/n)^k ==> y_n = y(1) = (1-a/n)^n implicit Euler: y_{k+1} = y_k - a/n * y_{k+1} ==> y_{k+1} = y_k / (1+a/n) ==> y_k = 1/(1+a/n)^k ==> y_n = y(1) = 1/(1+a/n)^n Both approximations tend to exp(-a) *for n to infinity* Now assume a is rather big (around 10^6), look at the behaviour of y(k) for n = 100 and compare that with the exact solution exp(-a*k/n) Be carefull: implicit schemes usually are much more time consuming than explicit ones, but have very good stability properties. Sometimes they are not neccessary and you can cope with the fast explicit schemes. Hope that helps, Martin. -- The early bird gets the worm. If you want something else for breakfast, get up later. ============================================================================== From: Lars Johansson Subject: Re: What algorithm uses DDASSL? Date: 19 Aug 2000 10:43:55 GMT Newsgroups: sci.math.num-analysis There is also a book brenan, Campbell, Petzold, "Numerical solution of initial-value problems in differential-algebraic equations", North-Holland 1989, reprinted by SIAM 1996. -- Lars To reply remove X in email address. ============================================================================== From: Petr Kuzmic Subject: Re: Comparison DDASSL to Alternative Diff. Equation of 2. degree Date: Sat, 19 Aug 2000 08:53:34 -0500 Newsgroups: de.sci.mathematik,sci.math.num-analysis "Jan C. Hoffmann" wrote: > > I'd written a straight forward algorithm for solving differential equations > and I'd like a comparison to DDASSL if possible. Is there a significant > improvement? You can easily find out by downloading DDASSL from the Netlib repository If you don't have a Fortran compiler, you can use the 'F2C' translator and compile DDASSL in "C". Works like a charm. HTH, -- Petr _____________________________________________________________________ P e t r K u z m i c, Ph.D. mailto:pkuzmic@biokin.com BioKin Ltd. * Software and Consulting http://www.biokin.com ============================================================================== From: Tom Hoffend Subject: Re: What algorithm uses DDASSL? Date: 23 Aug 2000 18:27:05 GMT Newsgroups: sci.math.num-analysis Petr Kuzmic wrote: > As far as DDASSL being old, that depends on one's perspective. I > believe the Technical Report describing DDASSL was published in 1983 or > so. Does this mean it is obsolete? Herr Professor Gauss published his > work several years before Napoleon had the brilliant idea to conquer > Moscow, but we still use least-squares regression today. By the way, in > 1991 Petzold received the first ever Wilkinson Award for DDASSL: > . DASKP (Differential Algebraic Systems Krylov Preconditioned) supercedes DASSL. It can be run in a DASSL-like mode with direct solve of the linear systems generated from the implicit method (dense of banded matrices) or in a mode that uses preconditioned iterative solution methods which are great for large sparse systems. The DASSL-like mode is better than the original DASSL because it can be used to find a self-consistent initial condition for your system of DAE's. The distribution of DASPK, available at http://www.engineering.ucsb.edu/~cse/ , includes a banded preconditioner, a standard sort of preconditioner based on incomplete LU factorization, and a preconditioner designed for reaction-diffusion equations. I personally prefer the ILU preconditioner. I have found that DASPK works quite well for heat flow problems in multiple dimensions with moving heat sources, multiple materials and various kinetic models of thermal decomposition of the materials. The distribution comes with an example code illustrating how to solve a simple heat flow problem in two dimensions. TRH -- Thomas R. Hoffend Jr., Ph.D. EMAIL: trhoffend@mmm.com 3M Company 3M Center Bldg. 201-1C-18 My opinions are my own and not St. Paul, MN 55144-1000 those of 3M Company.