# Håkan Lennerstad, research

Welcome to my research home page! Här är den på svenska (Swedish).

I’m Håkan Lennerstad, professor in mathematics at the BTH. My background is Master of Science in physics and Ph. D. in mathematics, both at Chalmers University of Technology, Gothenburg, Sweden. I’ve been at the BTH since 1992.

The papers can be found in the BTH research data base: www.bth.se/fou . If not, send me an email and I will add a link.

The research can be described rather consistently as the following projects.

In parenthesis: (number of papers, year of most recent publication).

1. Comparing performance of parallel computer organization alternatives (15, 2014)

2. Multiprocessor fault tolerance (6, 2005)

3. Schedulability criterions for multiprocessor servers (4, 2015)

4. Preemption dependent multiprocessor performance (1, 2008)

5. Number theory (3, 2017)

6. Coding theory (6, 2014)

7. Partial differential equations (3, 1992)

8. Mathematics education (22, 2014)

9. Skill and technology

10. Quantum physics (1, 2017)

11. Graph theory (2, 2017)

Articles and books written in Swedish appear in the Swedish site only.

## Project 1. Comparing performance of parallel computer organizations

Project 1: Comparing performance of parallel computer organizations

The performance of two scheduling alternatives (often parallel computer organizations) are compared, one more flexible and one less flexible. For example dynamic and static allocations of a parallel program on a multiprocessor.

We assume optimal allocations in both cases, which are known to be NP-complete problems. Nevertheless, it turned out to be possible to calculate explicit formulas for the maximal ratio of the two completion times for worst case programs. Most scenarios concern parallel processing, but we have also results for scenarios about memory modules, computer communication and cache memories.

The problem scenarios are very natural from an engineering point of view, most of them due to my main co-author Lars Lundberg.

*Mathematics content*

The scenarios are all at the border of computer science and combinatorics – the problems can be considered in either formulation. In most of them 0,1-matrices are central as objects of optimization, representing a multiprocessor with scheduled processes.

*Selected papers with comments*

The following is the first and most referenced paper, based on a clear-cut formulation:

An optimal execution time estimate of static versus dynamic allocation in multiprocessor systems, with Lars Lundberg, SIAM J. Comput., 24(4): 751-764, 1995.

This paper contains the previous scenario only as a special case, thus involving more variables.

Optimal Combinatorial Functions Comparing Multiprocess Allocation Performance in Multiprocessor Systems, with Lars Lundberg, SIAM J. Comput. 29(6): 1816-1838, 2000.

A monograph containing most of the results of the project up to 2003:

Research monograph: Optimal Scheduling Combinatorics, (211 pages) with Lars Lundberg, Electronic Notes in Discrete Mathematics, Vol. 14, Elsevier, May 2003.

The computational complexity of a certain speed scheduling primal-dual algorithm for open shop scheduling is considered below. It turns out that locally, close to the optimum, it is not only polynomial time but even linear time. However only if the number of tasks and the number of processors is not equal, by some reason.

Local Linear Time Convergence of Primal-Dual Energy Minimization Algorithm for Parallel Processing, ISPDC 2014: 135-139, 2014.

The following paper is the only one where the cost of reallocation of a process is not zero. Then the granularity of a program becomes important.

Comparing the Optimal Performance of Parallel Architectures, with Kamilla Klonowska, Lars Lundberg, Magnus Broberg, Comput. J. 47(5): 527-544, 2004.

## Project 2. Multiprocessor fault tolerance and load balancing

If one or more computers in a computer cluster break down, corresponding processes need to be rescheduled to other computers. This can be done in a load balancing way by using a so called Golumb ruler as a reallocation scheme.

*Mathematics content*

The combinatorial concept of Golumb rulers are central for this kind of problem.

*Selected papers with comments*

We invented a variant in one of the papers: the modulo ruler, allowing even denser packing of numbers.

Using modulo rulers for optimal recovery schemes in fault tolerant distributed computing, with Lars Lundberg, Kamilla Klonowska, Charlie Svahnberg, Proceedings of the 10th International Symposium PRDC 2004, Papeete, Tahiti, pp. 133-142, 2004.

The following paper concerns hash tables rather than load balancing, again with Golumb rulers.

Using Optimal Golomb Rulers for Minimizing Collisions in Closed Hashing, with Lars Lundberg, Kamilla Klonowska, Göran Gustafsson, ASIAN 2004: 157-168.

If we choose allocation so that a computer crash never prolongs the completion time by more than r %, how much does this precaution prolong the completion time in case of no crash, as a function of r? This problem is solved without Golumb rulers:

Optimal Computer Crasch Performance Precaution, with E. Laksman, L. Lundberg, Discrete Mathematics & Theoretical Computer Science, Vol 14, No 1, 2012.

## Project 3. Schedulability criterions for multiprocessor servers

Here we consider a server that receives arbitrary task sets. A basic problem is to devise a measure that a server can use to accept an incoming task that guarantees that all accepted tasks can meet their deadlines. There are two cases, aperiodic task sets and periodic task sets. Here the latter case is considerably more difficult because of the extra constrains due to the periodicity. In each of the two cases we have considered two subcases: deadline priority and slack priority. Slack priority give slightly better results, but is (therefore?) more complicated to analyze.

*Mathematics content*

The functions involved are only ratios, but the min-max-argumentation to single out worst-case task sets in the set of arbitrary task sets is not particularly trivial.

*Selected paper with comments*

The following paper considers virtual processing.

Utilization-based Schedulability Test of Real-time Systems on Virtual Multiprocessors, SRMPDS’15, Beijing, China, 2015, with Lars Lundberg and Christine Niyizamviyitira.

We are still working on the fourth and the hardest case: slack and periodic. Coming!

## Project 4. Preemption dependent multiprocessor performance

Here we consider parallel programs with independent processes. A preemption allows improved performance by interrupting execution of a process and reassuming it on another processor. If the optimal completion time of a parallel program P on a multiprocessor with two processors and i preemptions is denoted by Ti(P), the famous 4/3-conjecture claims that T0(P)/T1(P) ≤ 4/3 for all programs P, thus optimally comparing 1 preemption to 0 preemptions. This conjecture was settled 1993 by Coffman and Garey (Journal of the ACM, Vol. 40, No. 5, November 1993, pp. 991-1018). The present work extends this result to n processors, optimally comparing i preemptions to j preemptions, for any positive integers n, i and j.

*Mathematical content*

Again, the main problem consists in characterizing worst case parallel programs by discarding sets of harmless programs. In this case the Stern-Brocot tree plays a central role in the final result.

The Maximum Gain of Increasing the Number of Preemptions in Multiprocessor Scheduling, with Lars Lundberg and Kamilla Klonowska, Acta Inf., 46(4): 285-295, 2009.

## Project 5. Number theory

This project is an offspring of Project 4, however not (yet) applied in computer science or elsewhere.

*Papers with comments*

The first paper considers a basic dividing problem and simultaneously different levels of approximations of a rational number by decomposing it with mediant addition. It is based on the Stern-Brocot tree, and involves a new search algorithm for this tree.

Decomposing rational numbers, with Lars Lundberg, Acta Arithm., 145(3): 213-220, 2010.

It turns out that the search algorithm of the previous paper can be exploited to define the Stern-Brocot tree not only for pairs of integers, but for n-tuples. The following paper establishes the main properties of this extension.

The n-dimensional Stern-Brocot tree, Research Report No. 2012:04.

The n-dimensional Stern-Brocot tree, accepted for publication in Inte. Jou. of Number Theory.

## Project 6. Coding theory

This research started 1997 as a cooperation with Magnus Nilsson, associate professor at the Linné University, Sweden, and Efraim Laksman joined later. The minimum Euclidean distance is a fundamental quantity for the error-correction capability of a block code with phase shift keying. In this research we derive upper bounds on the minimum Euclidean distance as an explicit function of three parameters: alphabet size, word length and the number of code words. The bound is optimal for many parameter values. Previously, only bounds that are asymptotic in at least one parameter were known.

*Mathematical content
*The bounds are deduced by introducing different so called inner distance measures or metrics, which provide better bounds for the minimum Euclidean distance.

*Selected papers with comments*

The first paper contains a specific inner distance measure that is not Euclidean, improving the bound for the minimum Euclidean distance.

An upper bound on the minimum Euclidean distance for block coded phase shift keying, with Magnus Nilsson, IEEE Trans. of Inf. Th., 46(2),: 656-662 2000.

This paper considers a general inner distance measure, and fine-tuning its parameters provides sharper bounds.

Improving Bounds of the Minimal Euclidean Distance for Block Codes by Inner Metric Optimization, with Magnus Nilsson and Efraim Laksman, Jou. of Disc. Math., Vol 310(22), 3267-3275, 2010.

Generalizing in word length, to asymmetric codes, and to other noise than Gaussian:

Generalized Upper Bounds on the Minimum Distance of PSK Block Codes, with E. Laksman, M. Nilsson, IMA Jou. Maths. Control & Info, Jan. 20, 2014.

## Project 7. Partial differential equations

This project concerns boundary value problems for the Laplace’s equation in non-smooth domains – Lipschitz domains and Lipschitz crack domains. My doctoral thesis describes the two-dimensional case, when the solvability with Lp-data can actually be described with an Ap-condition on the measure that is defined by the derivative of the conformal mapping. This leads to weighted Lp-spaces.

The Dirichlet problem in Lipschitz crack domains, Department of mathematics, CTH, 1986.

Ph.D. thesis: Duality of the Neumann and Dirichlet problems for the Laplace equation in non-smooth domains, CTH, 1989.

Localized Galerkin estimates for boundary integral equations on Lipschitz domains, with V. Adolfsson, M. Goldberg, B. Jawerth, SIAM J. on Math. An., 23(5): 1356 – 1374, 1992.

## Project 8: Mathematics education

This project consists of different strands of ideas, many written in Swedish, summarized by the comments to the papers below.

*Selected papers with comments*

In logical graph form an argumentation is more geometric and possible to overview. A reader can easily choose way to study it. The reason is that unlike time, the logic of a proof or argumentation is not linear. It is more like a map of roads in a village (mathematically: a graph). During a seminar one must adapt to the linearity of time, which authors of books also do, and then fixes the way a reader should study it. In a logical graph an argumentation is represented more according to the structure of argumentations.

Logical graphs – how to map mathematics, Zentralblatt für Didaktik der Matematik (International Reviews on Mathematical Education) 96/3, 1996.

What would happen if you wrote a textbook during a course and let student’s comments affect it? Here is the result of a project in that direction.

An Evolutionary Text Book – Evolving by Student Activity, Jou. of On-line Math. vol. 7, 2007.

The formal language of mathematics – Mathematish – is a language on its own whose properties in many respects are very different from the properties of English. Unspoken language issues may all the time come in the way of mathematics learning.

Mathematish – a Tacit Knowledge of Mathematics, with Lars Mouwitz, proceedings of MADIF4, Malmö, Sweden, 2004.

In a mathematics classroom three very different kinds of knowledge are relevant: the formal non-empirical knowledge of mathematics, empirical knowledge of mathematics education, and practical (largely tacit) knowledge of teachers’ competence. They are extremely different in nature, but must coexist to provide mathematics education with good quality.

Spectrums of knowledge types – mathematics, mathematics education and praxis knowledge, proceedings of MADIF6, Stockholm, Sweden, 2008.

Papers and books written in Swedish, which in Project 8 are the majority, can be found on the Swedish site.

## Project 9. Skill and technology

All papers here are in Swedish, so they appear om the Swedish site. Except the one mentioned in the previous project:

Spectrums of knowledge types – mathematics, mathematics education and praxis knowledge, proceedings of MADIF6, Stockholm, Sweden, 2008.

## Project 10. Quantum physics

Mattias Eriksson formulated a problem of the total statistical weight for all Rydberg levels for an ion in a plasma. This total statistical weight is the total number of possible quantum states, which is a sum over four different quantum numbers. In this sum, the main quantum number and the orbital- and angular momentum quantum numbers (L and S) for the ground state are parameters in the sum. It turned out that this sum over four quantum numbers can be explicitly summed, and the result is surprisingly simple: a factor times (2L + 1)(2S + 1).

A new formula for the statistical weight for a sequence of Rydberg levels in an atom or ion, med Mattias Eriksson, Journal of Physics: Conf. Series 869 (2017):012010.

## Project 11. Graph theory

To understand flows in networks, for example road networks and internet networks, fundamental graph theory questions arise. With Henrik Fredriksson and Mattias Dahl the concept of dependence between pairs of edges have been formulated, a concept that shows directly how flows on edges in a graph depend on each other. It depends strongly on the topology of the network/graph and is rather different than the concept of adjacency.

A dependency framework for links in a network, with Henrik Fredriksson and Mattias Dahl.

One may also ask: how can the nodes in a graph be numbered from 1 to n (the number of nodes) so that the difference between two labels is as similar as possible to the distance between the nodes in the graph? Clear answers (and more strict formulations) can be given:

List graphs and distance-consistent node labelings, submitted to Electronic Journal of Graph Theory and Applications.