Integration in first-order arithmetic

Jan has finished an implementation of a primitive function operation on first-order polynomials with interval coefficients. This is one of the main components of the Picard operators that are the basis for the hybrid interval ODE solver that is under development. The main difficulty was in the choice of degree reduction algorithm, which maps the nonlinear terms generated buy integration back to first-order form. The next component Jan will target is the containment relation, which is used to detect when iterated application of the Picard operator may be terminated.

Language support for dynamic models

This week Adam continued reading Languages and Tools for Hybrid Systems Design by Carloni, Passerone, Pinto, and  Sangiovanni-Vincentelli. Among the languages covered by the survey is Shift, which differs from the other languages in the survey in that it supports models whose structure can change during a simulation. Two modern modeling languages which support this type of dynamic models are Acumen and Yampa. Acumen supports this feature in a manner similar to Shift, through the creation, movement and destruction of its natural objects. In Yampa, you can implement a similarly dynamic model by defining it in terms of switching combinators, one of which was discussed in an earlier post. It is still not clear to Adam to what degree languages which support dynamic collections of data need to support dynamic reconfiguration of the model itself. This question is interesting because the latter tends to lead to programs which are difficult to understand.

Keeping things straight

During his work on an interval hybrid ODE solver Jan has so far been using constant function approximations. The benefit of using such a simple approximation is that the implementation of the various operations that constitute the solver algorithm has been comparatively simple. A major drawback however has been that they trivialize some otherwise nontrivial operations. An example is function composition, which in the constant case simply discards the inner function, but in the non constant case has many potential stumbling blocks. To test the design of the solver Jan has started implementing affine functions, i.e. functions on the form:

(affine function) f(x1,…,xn) = f0 + f1*x1 + … + fn*xn

One could argue that such functions give the simplest nontrivial case of a function and are therefore ideally suited as numerical base for the next iteration of the solver. The simplicity of affine functions leads to challenges already in the implementation of composition, where the resulting mixed terms have to be mapped to some linear or constant term. The primitive function operation also produces nonlinear terms, which have to be reduced for the result to be representable as an affine function. The choice of reduction algorithm is important as degree reduction is often the main source of information loss in the resulting arithmetic. A suitable implementation of degree reduction is currently the focus of Jan's work.

Reading about reading

While looking for information on how to prepare himself for his pending literature review of parallel programming models, Adam came across a nice guide by Missy Harvey which also contains several links to useful literature on the topic. Another resource Adam found was a pocket guide on Efficient Reading of Papers in Science and Technology. Most of the practices it describes are common sense, but others (write a short summary of a paper just after finishing reading it) were new to him and seem like a great idea.

Guards and constant enclosures

During the past weeks Jan has been working towards an implementation of a hybrid ODE solver for problems with interval initial conditions. The solver is based on using functions as the base numeric type. To get a working prototype as quickly as possible Jan has been implementing the first version using constant functions but has noticed that they do not force him to address some complexities that only arise when dealing with non-constant function representations. One example is the problem of determining when a guard holds for the solution over a given interval. For a constant function it is not possible to separate cases when the guard holds everywhere from those when it holds only at some points in the interval. Jan is currently finishing the implementation of event detection, after which he will start implementing a simple version of non-constant function enclosures that will make it possible to test the solver properly.

How to review a research paper

Walid wanted to find a reference for how much is a reasonable amount of time to budget for reading a paper in an area familiar to the reader.  A reasonable rough guess seems to be one work day.  Of course, the exact amount depends on a lot of factors.  In the process, he stumbled across a nice discussion of how to write a good review for a research paper.

O static where art thou?

During his work on an interval hybrid ODE solver Jan has been wrestling with the issue of static methods in Scala. In previous work on parametric numerics Veronica and Jan relied on heavy use of implicits to have functions available without the necessity of calling them on an object. This approach has been successful, but results in base classes that contain implicit objects and methods that serve as carriers of the static methods, making the code less readable. Perhaps a more serious drawback is that these structures make the code less malleable, as they obstruct explorational coding, such as that done while writing prototypes for various design alternatives. The main reason for the complicated nature of the solution to static methods is that they are carried by companion objects to classes. As opposed to classes these do not take type parameters, which introduces the need for more involved solutions. One way forward would be to avoid static methods altogether, and use parametrised methods carried by objects of parametrised classes that exist for this purpose alone.This option is no worse than using static methods through qualified imports, but constructing the carrier object instead of importing a module. Another possibility is to program with concrete classes only, this way their companion objects provide the methods that operate on objects of the class. For the moment Jan has chosen the latter option as a matter of practicality, while working on the logic of the event detection  algorithm itself.