Construction and benchmarking of adaptive parameterized linear multistep methods

Abstract

A recent publication introduced a new way to define all k-step linear multistep methods of order k and k+1, in a parametric form that builds in variable step-size. In this framework it is possible to continuously change method and step-size, making it possible to create better behaving adaptive numerical solvers. In this thesis general numerical solvers based on this framework have been implemented, utilizing variable step-size and variable order, based on control theory and digital filters. To test and analyze the solvers, libraries of test problems, methods and filters have been implemented. In the analysis, the solvers were also compared to commercial (Matlab) solvers. The conclusion of this investigation is that the solvers show potential to become competitive in the field.

Popular Abstract

Many important problems in engineering and science need to be solved using computers. Unlike people, computers do not make mistakes, and they are much faster at certain tasks. However, computers have a big weakness: they do not know what to do without being instructed. These instructions are created by people designing algorithms, and constructing software. Our thesis project involves implementing and testing an algorithm designed to solve a particular type of mathematical equations.

To simply explain how the solver works, we use the following example:
You are dropping a stone from your roof. According to physics, the stone will accelerate constantly 9.82 ms$^{-2}$ by gravity towards the ground. If you know at what height the stone was dropped, you are able to calculate where the stone will be a second later. This new approximated position can then be used to calculate where the stone will be two seconds and so forth. This is exactly what our software --- which we call a numerical solver --- does.

The time passed between each calculation of the position of the stone in the previous example, is called a time-step, and generally, the longer a time-step is, the less precise will the next position approximation be. Herein lies a problem: We would like as few calculations as possible, but at the same time as accurate a solution as possible. By taking longer steps, we do not need as many calculations, but at the same time, longer steps means less accuracy.

A numerical solver can be compared to a car. Assume a self-driving car only able to use one speed. This speed is chosen in the beginning of your car ride and can not be changed during the same ride, only in the beginning of the next. The speed might be adequate in some situations, on some roads, but in others it might be too fast or too slow, which means that you have to choose the speed carefully in the beginning of your ride. This is analogous to a numerical solver only able to use one step-size throughout the same calculation.

Instead we let the car use different speeds during the ride. However, it is only allowed to half the speed or double the speed at every change. This would lead to a pretty ``bumpy'' ride. Most numerical solvers today use this kind of regulation to change the step-size.

Since the roads we drive on might change character a lot very fast, we would instead like the car to continuously be able to change the speed, such that we always manage to stay on the road and at the same time do not need to spend all day in the car. In the corresponding way, a mathematical problem can change character very fast. In our solver we let the step-size change continuously, removing this bad ``bumpy'' behavior.

The solver can not only vary the length of the time-step, but also change the underlying numerical method during the calculation of a particular problem. The difference between these methods is what we call order. Higher order methods often allow us to take longer time-steps, while still getting the same amount of precision as a lower order method would get using a shorter time-step. This means getting the same precision for less work. The order can be compared to the gears in a car. Depending on the surface of the road, the slope, and other factors, we want to use the correct gear to be able to drive as efficiently as possible. The problem with using the highest order method all the time, which may seem like the best way to go, is that all problems are not alike, just like all roads are not alike. One method working well with one problem, may not work as well with another. Also, the character of a problem may change during the calculation in such a way that a method that was working well two seconds ago, is no longer a good choice.

Our thesis has focused on these two control systems, that is, a system controlling the step-size during the calculation, and a system controlling the method/order during the calculation. The software we have built, is using a certain type of numerical methods called linear multistep methods, and the control systems mentioned, are based on control theory, which is a branch of science and mathematics, used to build systems controlling everything from thermostats to jets, and of course, cars. The software package was tested after the implementation, and it turns out that it has the potential of becoming better than the corresponding packages used today, that do not use control theory.

• author: Olander, Josefine and Jonsson Glans, Erik
• supervisor: Carmen Arévalo; Gustaf Söderlind
• organization: Mathematics (Faculty of Engineering)
• course: FMN820 20161
• year: 2016
• type: H2 - Master's Degree (Two Years)
• subject: Mathematics and Statistics; Technology and Engineering
• keywords: Linear multistep method, matlab software, variable step-size, variable order, numerical solver of ODEs
• publication/series: Master's Theses in Mathematical Sciences
• report number: LUTFNA-3039-2016
• ISSN: 1404-6342
• other publication id: 2016:E49
• language: English
• id: 8894921
• date added to LUP: 2016-11-25 09:50:01
• date last changed: 2016-11-25 09:50:01