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 is the general import for green scientific programming (GSP) of the plant models?
How do we connect GSP with the confluence of fields?
What is the relevance of computational complexity theory to this discussion?
Broadly, our object is now an algorithm, and we are analyzing it. Also of interest, in this context, is the “analysis of algorithms,” in the narrow sense, that is used in computer science: only as the … complexity of the algorithm, in terms of the resources that it uses, as a function of the characteristics of the model parameters.
Stochastic extensions?
What is the conclusion, and how does it relate to the initial question of what programmers can do to help the environment?
In the previous article, I looked with some broad strokes into the area of scientific programming for environmental applications, or “green scientific programming,” and suggested that we piggyback on the efforts of mathematicians who are looking into environmental applications of mathematics, or green mathematics.
Today I will look at what may come to be viewed as a classic application of green mathematics, Qinglan Xia’s network-based model of a growing tree leaf, from the point of view of the general lessons it may show us about green scientific programming, and where it fits in with the other fields at its crossroad. For an informal technical introduction to this model, see Prospects for a Green Mathematics.
Aside from its specific characteristics, what I find exciting about this area is that several fields come together here, and you get an opportunity to learn from people with a diverse variety of experience. Before considering “green” scientific programming in this social regard, let’s consider scientific programming itself in this regard.
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, which includes natural science, mathematics, programming, and analysis of algorithms.
Natural science comes into play, in the assessment of how plants actually develop. This led to a simplified model, taking the form of an algorithm, which is a kind of mathematical process. This is a model of one of nature’s algorithms. 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.
Natural science 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.
To flesh out the programming, mathematics and algorithm analysis of the matter, let’s describe a hypothetical case study.
To illustrate these ideas, consider a hypothetical model of plant development, which runs in discrete time, and takes place on a discrete grid. The “plant” consists of some squares in the grid. It is initialized to some collection of root cells, which we’ll stipulate will make a connected horizontal segment–the base of the plant. There is a deterministic algorithm giving the rules about how new cells get added on each iteration. The complete evolution of the plant is therefore a function of the length of its base.
Since cells never get deleted, 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 evaluate them, either through reasoning or experiment.
Now an algorithm leads a double life, for it is both a theoretical object, and a description of the empirical behavior of a machine that “runs” the algorithm. So statements about algorithms have both a theoretical and an empirical interpretation, and therefore can be approached both analytically and empirically, with equal validity and precision. Depending on the case, however, one of these may be more productive of results. To illustrate these , let’s consider same sample hypotheses.
Hypothesis 1. 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 runs the growth algorithm for all root lengths less than 10. After a small number of iterations, it is guarantee to either stabilize or have grown beyond ten cells.
Hypothesis 2. For all root lengths, the plant grows without bound. This is still equivalent to an empirical statement about the behavior of a computing machine: 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. But this statement is only semi-decidable by experimental methods: an experiment can prove it false, by stopping at a fixpoint. To prove the statement by means of an experiment, we would have to perform an infinite number of experiments, each running for an infinite amount of time.
(Halting problem)
Hypothesis 3. 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 possible approach.
We can also examine the computational complexity of the plant development process. 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.
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.