The Azimuth Project Blog - Green scientific programming (Rev #8)

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. (See the article on green mathematics for more details.)

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!

Case study

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.

We see here a great intersection between fields. There are elements here of natural science, mathematics, programming, and analysis of algorithms.

Natural science comes into play, in the assessment of how plants may actually develop. The lead to a simplified model, which is constructed as an algorithm – a hypothesis about one of nature’s algorithms – which is a kind of mathematical process. It is realized, and brought to fruition – giving images of the leaves – precisely 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 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 specifies which new cells get added on each iteration. For simplicity, suppose that 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 any statement about an algorithm is both a purely mathematical statement and an empirical statement about the behavior of a computing machine. So we have some latitude about whether 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 hence 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 in this case consists of an unlimited pool of parallel processors (computations are taking place throughout all of space). 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.

As a parting thought, let’s consider a further enrichment of this picture, which 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 some of the variables that it uses are 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 what is the expected height of the completed plant, as a function of the root length. Once again, programming provides a key tool 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.

Conclusion

I hope that this entree’ has given you a sense of 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. Our main efforts so far have concentrated on network theory, the programming of stochastic models related to environmental topics, and now, an ongoing effort into the prediction of El Niño events from temperature data (possibly using climate network theory). Since we are an inclusive, volunteer organization, there is also room for us to start up new projects, including work on the network plant growth model that I mentioned here.

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 visit the Azimuth Forum, which is the permanent site where we hash out ideas for research, and where we develop and review these blog articles. We need producers as well as consumers of blog articles – and this could mean you! To participate in these discussions, just sign up for a membership. People normally begin by creating a thread introducing themselves and explaining their interests. We have no qualifications based on profession or what have you, other than a sincere desire to learn about and contribute to the understanding of the world’s environmental problems.

category: blog