Since explicit methods face stability issues, why is it that implicit methods are rarely used for time dependent hyperbolic problems?
Brian Straalen is correct: one has to understand what are the important scales of your problem. It doesn't matter what the application (physical problem) is as long as you know what processes are contributing the largest eigenvalues of the Jacobian matrix of your partial differential equations. So what I am about to describe is valid for any kind of problem but I will assume (for simplicity) that we are talking about fluid flow problems. Since I am mostly a fluids guy I will answer it this way: for low mach number flows (the speed of sound is faster than the velocity field which we call "subsonic") you will want to use either explicit methods or what are known as implicit-explicit (or IMEX) methods. In an IMEX methods, we linearize the problem about the speed of sound terms and then solve the linear implicit problem to avoid the time-step restriction of the fast acoustic waves while the slow advective terms are handled fully explicitly and fully nonlinearly. Now, if your flow field is high mach number flow (i.e., supersonic) then IMEX methods will not help you at all. So, the only option is to use: 1) explicit methods (with small time-steps of course) or 2) fully-implicit methods. Laurent Gosse is correct that most of methods do indeed impact the solution often times in an adverse way. For example, some IMEX and fully-implicit methods will have trouble with conservation (multi-step methods that rely on the solution being entirely accurate at each iterative solver solution) but others (such as Runge-Kutta methods which conserve linear invariants) will not. However, in IMEX methods (and also for fully-implicit methods) stability is achieved with large time-steps by essentially slowing down the fast processes. There has been some research done on exponential time-integrators which do not have this problem. Also, there are some explicit methods that, algorithmically, appear like iterative methods (as in implicit methods) and use very large time-steps but do not diffuse the solution in any way. These methods are known as extrapolation methods and well-known variants include the original method known as Gragg extrapolation and the more famous variant called Bulirsch-Stoer.
In summary, Implicit methods are used all the time but they do require additional machinery such as an iterative solver to solve the linear matrix-vector problem (this is true even for fully-implicit methods where Newton's method is used to linearize the problem and then an iterative solver is used to solve this. Sometimes they are combined and these are known as Newton-Krylov methods). In addition to an iterative solver, one also needs a preconditioners in order to accelerate the convergence of the iterative method. My group works on these very topics and you can find more info on my website: http://faculty.nps.edu/fxgirald/Homepage/Publications.html
Our studies show that IMEX methods based on Runge-Kutta (RK) are superior to those based on multi-step methods (e.g., backward difference formulas, Adams-Moulton methods, etc.). These methods can also be derived for fully-implicit methods. Implicit methods based on RK methods also have some additional properties that make them exceptional: 1) they can be constructed with a low-order embedded method (for error control) and 2) come with dense output (which means that one can actually construct a polynomial of the solution in time so that you know the solution at any point in the time-step with the same order of accuracy as that of the method.
This is a very good question. We all know that implicit methods HAVE to allow larger time-steps but what needs to be discussed is which method gives us a faster wallclock time to solution (for a given level of accuracy). For low mach number flows, we have shown that IMEX methods win. For high mach number flows, IMEX methods cannot compete and so we have to go to explicit or fully-implicit methods.
Simply because they diffuse a lot the steep gradients, they are not conservative except at steady-state and fronts don't move at the correct speed. You need to have the scheme's stencil which contains the cone of dependence of the PDE in order for it to behave well.
See however, LeVeque's Large time-step method:
http://epubs.siam.org/doi/abs/10.1137/0722063
We use implicit as well as semi-implicit or Implicit-Explicit schemes quite often in our work.
If the important dynamics of your system are at a time scale that is less than or equal to the timestep you can use for a stable explicit scheme, then you use an explicit scheme. It will be the most efficient method. It the relevant dynamics is much slower than your stable explicit timestep then you would consider using an implicit method to get your answer faster by taking larger timesteps (at the cost of more work-per-timestep). At some point one approach is more efficient than the other.
For instance, if your Mach number is low then you would consider using an implicit method, since the timestep to be stable is limited by diffusion effects, but evolving a flow system at the diffusive timescale requires a LOT of timesteps. Conversely at high Mach number the advective timescale dominates and fully explicit schemes dominate.
If you have a mixture of important timescales then the best solution is often to handle some parts explicitly and some parts implicitly.
It comes down to knowing what you are trying to model. Also, just because someone has implemented an explicit method doesn't mean it was a good idea. They just happen to be very easy to implement.
Brian Straalen is correct: one has to understand what are the important scales of your problem. It doesn't matter what the application (physical problem) is as long as you know what processes are contributing the largest eigenvalues of the Jacobian matrix of your partial differential equations. So what I am about to describe is valid for any kind of problem but I will assume (for simplicity) that we are talking about fluid flow problems. Since I am mostly a fluids guy I will answer it this way: for low mach number flows (the speed of sound is faster than the velocity field which we call "subsonic") you will want to use either explicit methods or what are known as implicit-explicit (or IMEX) methods. In an IMEX methods, we linearize the problem about the speed of sound terms and then solve the linear implicit problem to avoid the time-step restriction of the fast acoustic waves while the slow advective terms are handled fully explicitly and fully nonlinearly. Now, if your flow field is high mach number flow (i.e., supersonic) then IMEX methods will not help you at all. So, the only option is to use: 1) explicit methods (with small time-steps of course) or 2) fully-implicit methods. Laurent Gosse is correct that most of methods do indeed impact the solution often times in an adverse way. For example, some IMEX and fully-implicit methods will have trouble with conservation (multi-step methods that rely on the solution being entirely accurate at each iterative solver solution) but others (such as Runge-Kutta methods which conserve linear invariants) will not. However, in IMEX methods (and also for fully-implicit methods) stability is achieved with large time-steps by essentially slowing down the fast processes. There has been some research done on exponential time-integrators which do not have this problem. Also, there are some explicit methods that, algorithmically, appear like iterative methods (as in implicit methods) and use very large time-steps but do not diffuse the solution in any way. These methods are known as extrapolation methods and well-known variants include the original method known as Gragg extrapolation and the more famous variant called Bulirsch-Stoer.
In summary, Implicit methods are used all the time but they do require additional machinery such as an iterative solver to solve the linear matrix-vector problem (this is true even for fully-implicit methods where Newton's method is used to linearize the problem and then an iterative solver is used to solve this. Sometimes they are combined and these are known as Newton-Krylov methods). In addition to an iterative solver, one also needs a preconditioners in order to accelerate the convergence of the iterative method. My group works on these very topics and you can find more info on my website: http://faculty.nps.edu/fxgirald/Homepage/Publications.html
Our studies show that IMEX methods based on Runge-Kutta (RK) are superior to those based on multi-step methods (e.g., backward difference formulas, Adams-Moulton methods, etc.). These methods can also be derived for fully-implicit methods. Implicit methods based on RK methods also have some additional properties that make them exceptional: 1) they can be constructed with a low-order embedded method (for error control) and 2) come with dense output (which means that one can actually construct a polynomial of the solution in time so that you know the solution at any point in the time-step with the same order of accuracy as that of the method.
This is a very good question. We all know that implicit methods HAVE to allow larger time-steps but what needs to be discussed is which method gives us a faster wallclock time to solution (for a given level of accuracy). For low mach number flows, we have shown that IMEX methods win. For high mach number flows, IMEX methods cannot compete and so we have to go to explicit or fully-implicit methods.
Because the time-step restriction is usually not severe for hyperbolic PDEs. For instance, for the wave equation the CFL condition dictates dt ~ h. Thus, the explicit time-step required for stability is typically not much smaller than what you desire for accuracy anyway, so it would make little sense to use an expensive iterative method.
The stability issues is due to linear explicit methods. According to the Godunov theorem to achieve high order stable(monotone or TVD) schemes it is required to use nonlinear (explicit) finite difference or finite volume schemes, e.g. WENO schemes.
1) treating the non-linera term in implicit way leads to a non-linear system that must be solved (linearization or other procedures).
2) Other than the right answers provided by people, a further comment is also in the mathematical character of hyperbolic equations... implicit methods require to set some BCs at the updated time level, but you cannot set them at characteristic lines where the solution is propagated. Using upwinded discretization you have to set the correct stencil orientation at new time level when, however, you still do not have the solution (and the sign of the wave propagation). Therefore, implicit methods require some specific care.
The CFL condition that bounds the explicit time step refers to the fastest eigenvalue of your system. If this is the physics you are interested in (e.g. pressure waves) or if the physics you are interested in lives on a similar scale (fast moving shocks), then the stability restriction due to the CFL condition is not problematic at all and you are fine with an explicit method.
Only when your physics are on a much different scale, then the CFL condition is an issue and implicit is the solution. As others have said, low Mach number flows are a classical example, where the fastest wave corresponds to a fast moving acoustic wave and you are typically interested in the slow moving flow. Stiff source terms from chemical reactions are another example.
And as Brian said, there's a more mundane reason why people don't use implicit that much: They are undeniably more difficult to implement and require knowledge about solving nonlinear and linear systems that is very different from knowledge about space discretization schemes. Then people do it wrong, don't use time adaptivity or any other sort of error control, use only the implicit Euler method instead of higher order methods and when they then see bad solutions they blame it on the implicit method, not on their misuse.
Also note: For nonhyperbolic systems like Navier-Stokes, the situation is very different, because there you have the boundary layer, leading to very fine cells and therefore easily a stability restriction that is a 1000 times worse than for an Euler grid.
I concur with Martin Almquist. Fundamentally, hyperbolic equation is not stiff, while the heat equation is. The stability restriction for hyperbolic PDE allows dt = O(h) for explicit methods (dt = O(h^2) for heat equation). For accuracy considerations, you would choose dt = O(h) anyway so there is no incentive to use implicit method for hyperbolic equations.
With implicit methods, usually you need to solve coupled equations in each time step what can be very expensive in large scale problems.
To understand the interaction of space and time discretisation I prefer the approach summarised by R. Vichnevetsky in "Stability charts in the numerical approximation of partial differential equations: a review" 1979. As a first approximation you would consider the linear part of the PDE operator (like in a Taylor series). Then you can see what kind of eigenvalues the space-discretised system would have. It turns out, that for a linear hyperbolic case and a centered scheme (which does not add artificial dissipation at all), the eigenvalues would be pure imaginary or "oscillatory". Accordingly, in cases where the hyperbolic part dominates, the imaginary part of the eigenvalues of the discretised system are large and the solution exhibits high-frequency components. An implicit scheme is usually stable (or strongly stable) along the imaginary axis, which means that it does add artificial damping for problems which do not have damping at all, and the effect of the damping tends to get stronger along the imaginary axis. This is what makes an implicit time stepping stable (it basically damps oscillations). In general this not good or bad - the judgement depends on the problem. If you are interested (or the physical phenomenon is governed by) the high-frequency components, then this behaviour is bad, as it alters the system and renders the discrete case meaningless to the physics of the problem. If, on the other hand, the fast fluctuations are not important to the solution, then this behaviour is good and desired.
In all cases mentioned above where the error is governed by a sort of CFL condition, the artificial damping of the implicit schemes is "bad", as high frequency components matter. Implicit-Explicit (IMEX) schemes try to overcome this problem by separating the effects which can be treated efficiently by implicit schemes from those which can not. An implicit scheme is then applied to those parts of the problem, where the damping does not have a bad effect (or is even desired, like in diffusion processes). This is what is referred to in some of the answers above.
Summary: implicit schemes are not used in case where they treat the phenomenon which is simulated in a wrong manner. This is the case when high-frequency components matter. For many hyperbolic problems high-frequency components matter and this is why implicit schemes have a bad cost/quality ratio. Thus, they are rarely used in hyperbolic problems.
Please see the book of N.N. Yanenko (The method of fractional steps), explicit methods for hyperbolic problems are basically not feasible when the stability time step is far smaller than the time step of the physical scales u want to resolve. Following Godunov higher order schemes must be non-linear as long monotonicity is a demand. Therefore it is not easy to construct higher order, monotone, conservative implicit schemes that are consistent (in terms of Lax), stable and tough convergent.
This is an interesting discussion since the contributions are by people working in different fields. Clearly different rules apply for the different areas. My main
work is on circuit solver type problems like SPICE. The circuit input which is solved by the Modified Nodal Analysis approach which can represent any type of system. Hence, we are not able to characterize the system to be solved. In the beginning, explicit integration methods were used. However, stability problems forced the use of
implicit methods only. Also, the methods are required to be A-Stable. This usually excludes higher order methods. The previous note by Evgeniy mentions the damping of oscillatory solutions which we usually call "numerical damping". It has to be small enough.
Usually, a variable time step is used for the general approach. The Gear II or BD2 method is used a lot. Other similar methods are used. The back Euler or BD1 method has a lot of numerical damping unless the time step is chosen
to be very small. However, the solvers are often designed to switch between different methods in this class. These solvers also need to to be able to solve nonlinear problems. This is usually done with Newton's method. So, it is clear that this is a much different environment than if we solve a specific class of problems with clearly defined properties,
In addition to previous comments I'd like to add that when solving hyperbolic advection equation with implicit scheme the dependance domain of the numerical solution is the whole spatial domain (as for parabolic equation). At the same time the dependance domain of the continuous advection equation is limited in space. So there is inherent contradiction between properties of numerical solution by implicit scheme and properties of the solution of the original equation. Therefore it is much more difficult to develop highly accurate monotonic (non-oscillating) implicit schemes for advection equation then the highly accurate non-oscillaing explicit schemes.
Hi,
In my opinion, for true time-dependent problems with strong dynamics, to get enough accuracy, you should use Courant numbers of order O(1). For iterative implicit methods you may propagate the information accurately enough, but in some sense, each implicit iterate involves a O(1) Courant number, so there is no really benefit to go to implcit methods. It depends of what you want to get accurately. It only material wave are of interest (forgetting the pressures waves), then can use an implicit solver to solve the sound waves, and use a "CFL 1" explicit time advance scheme for the advection part. There are some references in this spirit for multimaterial compressible flow problems.
Years ago I was involved in a comparison of the Maccormack scheme to various implicit methods. This particular application made it's way from 3D models in the aerospace industry to 2D applications in surface water modeling. While I could see the clear advantage in computational savings in 3D, I just couldn't see why there was such a significant advantage in 2D. As it turned out, the advantage was fortuitous, rather than mathematical. The flip-flop spatial differences damped out higher frequency waves that were of no interest; whereas, the implicit schemes were controlled by these phenomena and required much smaller time steps.
I think that many features can be clarified using the simple 1D Burgers equation ....
You cna write
un+1 - un = - Int [tn,tn+1] d (u^2/2 )/dx dt
you can treat implicitly in some way the RHS but you have to discretize it in space assuming a correct stencil (domain of dependence).
This is an interesting discussion since the contributions are by people working in different fields. Clearly different rules apply for the different areas.
However, the solvers are often designed to switch between different methods in this class. These solvers also need to to be able to solve nonlinear problems. This is usually done with Newton's method. So, it is clear that this is a much different environment than if we solve a specific class of problems with clearly defined properties.
For spatio-temporal dynamics, irrespective of PDE type, IMEX is to be shunned at all cost. The reasons are given in the following:
A critical assessment of simulations for transitional and turbulent flows - Sengupta, T.K.; In proc. of IUTAM Symp. "Advances in Computation, Modeling and Control of Transitional and Turbulent Flows." (Editors: Profs. T. K. Sengupta, S. K. Lele, K. R. Sreenivasan and P. A. Davidson) World Scientific Publishing Company, Singapore, pp 491-532 (2015)
I have explained it in vivid details with examples from fluid mechanics.
The problem is on the numerical aspects. Simply speaking, people cannot afford implicit based methods to do the time marching for time-dependent flows, where the implicit methods usually require time-consuming inner iterations to maintain the time accuracy (say >=2nd order in time) for correctly computing time-dependent physics.
It depends on what you want to do. If you want to capture wave propagation phenomena explicit methods are more accurate and, since it is necessary to use Co < 1 anyway, stability is not a problem.
Of course explicit methods are far superior in terms of dispersion error for space-time dependent problem. But the major problem is with IMEX methods at the boundary nodes between explicit and implicit zones, where error packets are created which moves upstream - the ubiquitous q- waves. We have published enough for anyone interested to read. Unfortunately, there are vested interest groups! Honesty in research is gone!
I would like to add a few comments to supplement previous answers. Basically, there is nothing wrong in using implicit methods for solving certain types of hyperbolic PDE problems, particularly where the solution does not exhibit steep gradients. However, they do generally consume more computational resource than explicit methods. The main difficulty with hyperbolic problems occurs when discontinuities or steep gradients are present in the solution, which can result in unacceptable dispersion and or dissipation. In this situation, TVD (total variation diminishing) methods are preferred along with TVD Runge-Kutta type integrators. This approach, using flux limiter or WENO methods, for example, provides a good way of minimising dispersion and dissipation. Unfortunately, there is no general 'best' method and each problem has to be solved using the most appropriate approach. The Internet will provide much information on TVD methods, but I can provide a list of references if it would help.
Thanks Graham! I did not know that Runge-Kutta methods are implicit!! It is very reassuring to know that there are indeed issues of dispersion with implicit methods. Incidentally, extreme form of dispersion error gives rise to q-waves.
I have the impression that one should test first the physical properties of the system. In the present case it would be probably useful to test whether the Langmuir paradigm is suitable to describe the physical-chemical properties of the system.
Implicit time step methods may give you a result where the eigenvalues are no longer real and distincts. A classical example is the two fluid model which is already mapped the fix to become well pose. Explicit time step methods demand, at all time , that the system satisfy the hyperbolicity. Also, explicit time step methods are easier to employ parallel processing.
To Mr. Rosa: What you propose is suitable for multisystems. However, in many enzymatic activity the system is always hyperbolic (if I remember well how it functions !). We could, nevertheless, imagine that in a multisystem (enzymatic, for example) we may have to deal with hyperbolic and non-hyperbolic activities, at about the same time (perhaps !).
I would like to add that the natural procedure for solution of a purely hyperbolic problem is the method of characteristics. With the right choice of coordinates, the original system of hyperbolic first-order equations can be replaced by a system in terms of characteristics coordinates. If all hyperbolic problems could be easily treatable in term of characteristics, accuracy and stability would not be issues but unfortunately the computational cost, in most practical cases of interest in science and engineering, is just prohibitive. Because typical (practical) discretization approaches do not solve the problem in terms of characteristic coordinates, they are so to speak "unnatural" and have to deal with the various numerical issues discussed in the answers above. Therefore, to answer the original question posed by Chinedu Nwaigwue, available explicit and implicit discretization approaches which typically do not track the solution in terms of characteristics will have very similar shortcomings in terms of accuracy and behavior, with dispersion being one of the biggest problems in terms of accuracy of the solution. A reasonably well-calibrated explicit method for the problem at hand is usually so much cheaper than the corresponding implicit method and possibly as accurate. There is motivation to use an implicit method only when the problem can be solved better in term of tracking the evolution of physical phenomena which need to be resolved. For an introduction to the method of characteristics, I suggest to consult the classic textbook "Numerical Methods for Partial Differential Equation" by William Ames.
Hi Umberto,
I disagree with you since the treatment of source terms in characteristics methods is quite problematic. Especially, when local (Eulerian) source terms are of concern. Otherwise the error of splitting can also be a problem when integrating source terms in combination with Lagrangian methods (e.g. LeVeque). Moreover, in terms of efficiency, one big problem are time varying characteristics. Clearly characteristic methods have their good points and well defined applications, where they work well but unfortunately, as it is always in the real world, no general conclusions can be draw for characteristic methods being superior to Eulerian once.
Cheers
Aron
Explicit methods is better suited for HPDE due to the fact that solution at time (n+1) depends only on values at time n while in implicit ones the solution at time (n+1) is function of the "combination of values" at time n and n+1, therefore not inherently evolutionary as the hyperbolic equations usually request.
Hi Roberto! Finally you gave a sensible answer. We have published many papers to show what you said. Solving Navier-Stokes equation by implicit method for convection term is sheer disaster!
Hi Tapan,
can u please show me some reference to the publication u mentioned. I cannot agree on what u r saying in terms of hyperbolic problems in general, maybe it is particular to the method u r using. Just like to mention again that the question is the time scale of interest and this needs to be properly resolved no matter implicit or explicit. See also the book of N.N. Yanenko, where is clearly outlined that explicit methods for hyperbolic problem are inadequate since the stability time scale may be much smaller than the physical time scale of interest.
Cheers
Aron
Aron Roland : A reference for your kind attention, where implicit method did not work:
Role of time integration in computing transitional flows caused by wall excitation, T.K. Sengupta, V. K. Sathyanarayana, M. Sriramkrishnan and A. Mulloth, J. Sci Comput, vol. 65(1), pp 224–248 (2015)
And here are some explicit methods where we could solve Navier-Stokes equation by explicit method:
Onset of turbulence from the receptivity stage of fluid flows - T. K. Sengupta and S. Bhaumik Physical Review Letters, vol. 107(15), 154501 (2011)
Precursor of transition to turbulence: Spatiotemporal wave front - Swagata Bhaumik and Tapan K Sengupta, Phys. Rev. E, 89(4), 043018 (2014)
Impulse response and spatio-temporal wave-packets: The common feature of rogue waves, tsunami and transition to turbulence - S. Bhaumik, T.K. Sengupta, Physics of Fluids, vol. 29, pp 124103 (2017)
The reason that some method works and some do not, can be EXACTLY found out by analysis! It is not black magic!
I missed the logic about Yanenko's observation: In your physical problem you need to resolve some time scale, and if you choose a smaller time scale then the results are inadequate. Your logic is troubling! Or is it your interpretation?
No, Tapan,
what I am saying is that the stability time step may be far much smaller than the time scale of the physical problem itself. Imagine u want to look at tidal flow of a river (example of N.N. Yanenko in his book 1972) than the time step of the explicit method (let's do some math. E.g. DX = 1m and depth = 10m so DT = 0.1s) is far much smaller than the changes in the flow-field itself. I hope u can understand my logics now, beside that the time accuracy depends on the order of the time stepping method and I am quite happy with the implicit solver in OpenFoam when using for PipeFlow simulations. Article On the development of OpenFOAM solvers based on explicit and...
My opinion is that the first discussion about issues in using implicit methods for hyperbolic problems should be in a very simple model where we can discover the problems. A linear first order equation gives the exact solution f(x,t)=f(x-u*t,0). The solution in any point at time t does not depend at all on the other values at time t but only at t=0. Therefore, the real problem in implicit methods is the fact that we need to discretize a spatial derivative at time t, this way other values are involved. In a numerical sense, we are adding a spatial interpolation at time t. Only in few specific cases such interpolation does not alter the solution.
Try to understand this in term of the implicit first order method
f(i,n+1) + u*dt*(f(i,n+1)-f(i-1,n+1))/h= f(i,n)
or
f(i,n+1) + u*dt*(f(i+1,n+1)-f(i,n+1))/h= f(i,n)
You can see the stability condition but also the dt for which you can get an exact solution. The value f(i,n) is the only that propagates from time t=0 and it must transfer the information to time t.
I disagree with the statements that implicit methods are 'not inherently evolutionary'. This is simply not true. The 'failures' of implicit methods are usually the result of abusing of their robustness to employ time steps that are not acceptable for accuracy. Implicit methods make sense ONLY for problems with multiple time scales (tidal flow of a river, as mentioned in the discussion, is a classical example, weather forecasting is another) in which one is willing to sacrifice accuracy of the 'fast' part of the solution for efficiency reasons, while the 'slow' part is correctly approximated. Obviously, if one pushes this too much and uses a time step such that also the 'slow' evolution is not properly resolved (this happens e.g. when trying to simulate turbulent flow with implicit methods at large Courant numbers) inaccurate results are obtained. However, this has a clear mathematical explanation, due to the way in which the in-built numerical diffusion of implicit methods is acting, rather than being the result of some fundamental inaccuracy of implicit methods. Implicit methods of a given order are entirely equivalent to explicit methods of the same order in terms of accuracy, if the SAME (small) time step is used. For long time steps, this is not true any more, but in some (multiscale in time) problems you accept to lose accuracy on a part of the solution. One cannot understand the effectiveness of implicit methods by just looking at scalar advection, which only has a single time scale. What is needed is a hyperbolic system with different time scales, say for example shallow water equations with rotation.The good news is that by employing multirate approaches (find here
Article A conservative implicit multirate method for hyperbolic problems
an example of recent work in this direction) one seems to be able to get the best of both worlds.
Most of researchers only consider the method for spatial discretization. They do not care about the time discretization. Explicit scheme is very simple to test and code. The implicit discretization the code is more complicated. I think this is the reason.
Absolutely right Jianming Liu! Most researchers do not even know how to analyze spatial and temporal discretization together. If they did, then they would have found what is called as dispersion error. We have been writing papers since 2004 highlighting this. There is too much inertia to follow a new lead (now it about 15 years old!). A proper error analysis (not following the wrong von Neumann analysis!) will reveal that implicit method blows up, as can be tested by solving even 1D convection equation- as suggested by Fillipo. As you would know the exact solution, there is escaping other than acknowledging the truth! The fact is that mathematicians are not ready yet to face the truth.
The above statement is wrong, why should a 1st order implicit method blow up? 1st it is A-Stable and 2nd is unconditionally stable even with source terms if properly linearized. See the book of Patanker ... e.g.
Hello Aron,
Are we off the block too soon? Before making the claim, please check out what has been suggested. As you are so sure of your prediction of stability, then you should take large CFL number in solving 1D convection equation without any source term. Don't take any trivial initial condition. May be you can try a ramp and solve a Cauchy problem. When you are done, please share your experiences. We will be eager to know of your success.
Happy computing!
in general implicit approaches are more accurate and unconditional stable.
Muhannad, cite references or proofs! Making tall claims serves no one. After all it is science! It is not a belief system!
Tapan I strongly agree with you :-).
I would better say that science is a very particular belief system one in which there is no person that could be trusted only due to his position as a "minister"on the system organization.
Dear Prof. Bonaventura
the meaning that I set to the synthetic expression "....not inherently evolutionary..' is the following: one has to put much effort to make an implicit method to perform as well as an explicit one when dealing with puerly hyperbolic problem.
It is surely a qualitative statement.
The following expression "....fundamental inaccuracy of implicit methods...." is yours not mine.
Dear all,
Tapan has repeated several times that the key is in understanding the behavior of the global discretization, that is the implicit time integration plus the adopted spatial discretization. We are not discussing about implicit solution of ODE but the case of hyperbolic PDE wherein the spatial discretization has relevance in the determingin the global truncation error of the scheme. We can use the von Neumann analysis, or determinining the locus of eigenvalues by means of the Gershgorin theorem or any other thing provided that we discuss of a time-space discretization. And a look to the local truncation error expression can also add some insight.
Discussions about the numerical stability of implicit methods is hystorical in numerical analysis. One of oldest and most debated one is the Crank-Nicolson scheme, see for example:
https://watermark.silverchair.com/9-1-110.pdf?token=AQECAHi208BE49Ooan9kkhW_Ercy7Dm3ZL_9Cf3qfKAc485ysgAAAhwwggIYBgkqhkiG9w0BBwagggIJMIICBQIBADCCAf4GCSqGSIb3DQEHATAeBglghkgBZQMEAS4wEQQMSrHPpp_eau-CXs8XAgEQgIIBz7nI6RnuLLHWdG_lpnxm3Dgrs9b8qc8AUUjJy0tC6qOJQ9KeZdfs9wEufUXsVg9WE4ZfgFUSbAbU0SlfRBlje5w-FqU47VfMRpwZ3HiC5dzgPtkUDfIT63dTPrJgo7bUR0eQlND32AtVJ0X9g-AIfaLSNAofAk9RU7oEVSRje3x5PFbwpTSdKtA_gbWW1EAMOQAYRQmUzD44mT4aXCiGu1_XD8lxpkuK51yKB3yBsBeJSL6QkkORFqdAJmKBJT8qY5vLRC3gXGaZ11VY2QnR_h4a0Caq_x0OIMm095s-0x_S3q4c1Md36GYK3qpwdMKBDvzV4Emk5D0QOjcfzdAG_n1oym1RzKtDDyst-pcMJ5DFfMo5mfCmttfOHfjYWdNbsEg_uTxGTiWP0n86nT-oPfeYFUX2JORFk6ibewrTJaECJJ_knWr67vTGiTb_5VP18pq_P8lAtAsarLlIfE1G-W1RnZpT0itwjCcngBY_jRC_PHxLzeEJDO1tejQgSiAzReOvcIvMp2zc5fTEZTbf2Kf5Od1Z-7MvUbfbnXWriy1GAdAsXGfYN06JASw7Fj6PIiMuvNO9euB8BB8uMgPKZz2D1bGNkVeBqR_p09Dnuzo
Implicit methods are definitely more complex to code. They provide equivalent accuracy solutions, when used with equivalent size time steps, to their explicit counterparts. Obviously, using them with the same time step as the explicit methods is nonsense in problems when you want to resolve correctly the fastest time scale, or in which you have only one time scale. That's why broadly speaking it is true that 'nobody' is using them for hyperbolic problems. However, in some hyperbolic problems like low Mach number compressible flow, there is a definite advantage in using these more complicated methods and applying them with a time step that is much larger than the CFL condition based on the speed of sound would allow (just an example, the same happens in other contexts) but still smaller than the CFL=1 time step based on the flow velocity. This is widely exploited in numerical weather prediction, coastal flow modelling and other areas. This advantage is hard to recognize if one only looks at problems with a single time scale, for which definitely implicit methods are not recommended. It is true that space and time discretizations are related for all PDE problems (also for parabolic ones!) but in my opinion the issue of efficiency of implicit schemes is unrelated to this and can be discussed almost entirely in terms of the properties of the time discretization only. Indeed, one can show the same advantages already for ODE systems with multiple time scales.
here is one paper where certain issues are discussed ...
10.1109/TAP.2007.913089
If you are interested in the description of wave processes in the body, then explicit methods are needed. If the characteristic times of changes in your processes significantly exceed the characteristic time of propagation of a wave in the body, implicit methods are more beneficial.
I was successful in applying a Gram-Schmidt orthonormalization technique to stabilize my numerical methods to solving Maxwell's equations in 2 dimensions with a time variable (hyperbolic). You May want to look at that technique.
Dear Valery Aptukov
I'd like to say that when "..the characteristic times of changes in your processes significantly exceed the characteristic time of propagation of a wave in the body" we can drop the term proportional to the time derivative in the system of conservation equations that rules the physical phenomenon resorting to a system that probably is closer to an elliptic one.
Dear Roberto Bernetti
No. I did not mean the equations of elliptic type.
For example, an explicit scheme is needed to analyze the wave propagation process during spallation. And, for example, for a plate oscillation process, an implicit scheme can be used.
But, in this and in another case, we consider the equation of a hyperbolic type.
The differences are in the characteristic times (frequencies) of the phenomena.
All the best