Blog - Green scientific programming (Rev #9)

This page is a blog article in progress, written by David Tanzer. To see discussions of this article while it was being written, visit the Azimuth Forum.

Please remember that blog articles need HTML, not Markdown.

*guest post by David Tanzer*

What can programmers to do help the planet? In our search for ways to address this question, we can also consider the similar question, which has already been posed by John Baez at Azimuth: What can mathematicians do to help the planet?

That has led them to the pursuit of what could be identified as green mathematics, which includes topics in network theory that may be central to our understanding of life, the biosphere, and its potential modes of survival.

A good example of this kind of mathematics is Qinglan Xia’s network model of a growing plant leaf. It is essentially an network-based algorithm for plant development, which is based on simplified yet plausible physical assumptions. The model also presents evidence for a broader claim, which is that network theory is capable of illuminating the actual workings of nature.

So, here is one answer to what programmers can do to help the planet: help the mathematicians who are pursuing “green mathematics” and its applications!

Let’s start with Xia’s model, to see how programming can fit into the picture. Here, the veins of a leaf are modeled as a network of pipes for transporting fluids to the cells, and a growth mechanism is presented, which explains how the shape of the network determines its pattern of growth at each point in time. When this process is simulated on a computer, nice pictures of leaves are generated, and, with a suitable choice of parameters, they can take on a form similar to leaf types such as Maple and Mulberry.

Here we see a great intersection between fields, including natural science, mathematics, programming, and analysis of algorithms.

Natural science comes into play, in the assessment of how plants may actually develop. This led to a simplified model, which is constructed as an *algorithm* – a hypothesis about one of nature’s algorithms. Now an algorithm is a kind of mathematical process. It is realized, and brought to fruition – giving images of the leaves – by programming. Next, we can form hypotheses about the behavior of this algorithm – for instance, that the leaf will not grow beyond a certain size. This is a testable hypothesis, and the experiments are performed through programming. The analysis of algorithms also comes into play when we ask questions about the model and its computational complexity.

To flesh out the programming, mathematics and algorithm analysis of the matter, let’s describe a hypothetical case study.

To illustrate these ideas, suppose that we have some hypothetical model of plant development, which runs in discrete time, and takes place on a discrete grid. At any point in time, the “plant” consists of some squares in the grid – each occupied square is one cell of the plant. It is initialized to some collection of root cells, and the algorithm – a system of deterministic rules that defines a process – specifies which new cells get added on each iteration. Let’s suppose the root cells must make a connected horizontal segment, which is the base of the plant. We assume that the algorithm is deterministic, so that its complete evolution is a function of the length of the root.

Assume that cells never get deleted. Then either: the leaf stabilizes at a fixpoint, or it grows without bound.

Now we want to analyze the behavior of this algorithm; to form hypotheses about it, and to determine the truth or falsity of these hypotheses, either through reasoning or experiment.

Now an algorithm has an interesting double character: it is both a theoretical object, and a description of the empirical behavior of a machine that “runs” the algorithm. Statements about algorithms therefore have both a theoretical interpretation, and an empirical one. Statements about algorithms, therefore, can be approached both analytically and empirically, both with equal validity and precision. Depending on the case, however, one of these may be more productive of results.

Now any statement about an algorithm is both a purely mathematical statement and an empirical statement about the behavior of a computing machine. So we may be able to tackle questions about the algorithm using theoretical or empirical methods.

Consider for example the claim that for all root lengths, the plant will reach size at least 10 squares. We could solve this problem by analyzing the program, or empirically, using a program that tests the hypothesis for all root lengths less than 10. Each test is performed by running the growth algorithm. After a small number of iterations, it will have either stabilized to a size less than 10, or grown larger than 10 cells.

Now consider the claim that for all root lengths, the plant grows without bound. This is still equivalent to an empirical statement about the behavior of a computing machine, but now the statement is only falsifiable, but not decidable. It *is* an empirical statement, which can be concretized as follows: no matter what the inputs shape is to a machine which performs a single iteration, the output will be a proper superset of the input.

Finally, consider the statement that for all root lengths, the plant grows to a fixpoint. This is neither provable nor disprovable by empirical methods, and so theoretical analysis is the only viable approach.

Another type of analysis concerns the *computational complexity* of the algorithm. This pertains to the amount of resources consumed by the algorithm. For instance, for a given root configuration, consider the size of the leaf – or memory usage – as a function of time. Or consider the function which maps the root length to either infinity, if the plant grows without bound, or to the number of iterations that it takes to reach the terminal configuration. This is a measure of the *time complexity* of the algorithm. Here, we could measure time in terms of the number of steps that it would take for a uniprocessor to reach the terminal configuration, but that would be an unnatural measure. Rather, we are using nature’s computational model, which here consists of an unlimited pool of parallel processes (at the cells). The *space complexity* of the algorithm could be measured by the function which maps the root length to the size of the completed leaf (or infinity).

Note also, as we know from computer science, in general we are interested not in the minute details of these complexity functions, but in their asymptotic behavior – i.e., is the running time linear in the size of the input, or quadratic, or what have you.

So, to recap, we’ve just seen how programming, mathematics, and the analysis of algorithms come into play in this kind of study. But let’s not forget about natural science, which motivated Xia’s model of plant development. Xia’s model includes certain parameters representing the thickness of the veins, and the cost of transporting plant fluids through bends in the veins. The growth model is justified – albeit in an abstract and simplified way – on the basis of physical considerations.

A further enrichment of this picture is obtained by adding stochastic mechanisms – i.e. randomness – to the model, and using *statistics* to characterize the behavior of a plant development algorithm. Randomness gets introduced into a deterministic program whenever it uses random variables. E.g., flip a coin to determine whether or not to append a new cell directly above every cell that is on the “ceiling” of the plant.

In a stochastic model of plant development, we may ask, for example, about the expected height of the completed plant, as a function of the root length. Once again, programming provides a means for experimentally answering such questions. A master program runs many trials of the randomized algorithm, measures the heights of the plants, and computes the average. In fact, as things become more complex (stochastic), analysis becomes harder and harder to perform, and methods of scientific programming come more and more to the foreground as primary techniques.

I hope that this entree’ has given you a sense of some exciting possibilities in the realm of what could be called *green scientific programming.* It is a fertile context, with facets involving natural science, mathematics, programming, and the analysis of algorithms. There is a great opportunity here for collaboration between programmers, mathematicians and scientists. Here, you can learn “on the job” from people in a wide range of fields.

The Azimuth Project is an interdisciplinary community that aims to contribute, among other things, to the development of green mathematics and green scientific programming. If you are interested in exploring any of these ideas further, I encourage you to take a further step, which goes beyond the transient realm of blog discussions. Come join us at the Azimuth Forum, which is the permanent site where we hash out ideas for research, and where we develop and review these blog articles.

category: blog