Showing changes from revision #2 to #3:
Added | Removed | Changed
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.
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, here the is veins one of answer a leaf are modeled as a network of pipes for transporting fluids to what programmers can do to help the planet: cells, help and a growth mechanism is presented, which explains how the mathematicians shape who 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 pursuing generated, “green and, mathematics” with a suitable choice of parameters, they can take on a form similar to leaf types such as Maple and its Mulberry. applications!
Here we see a great intersection between fields, which includes natural science, mathematics, programming, and analysis of algorithms.
Let’s Natural start science with comes Xia’s model, to see how programming can fit into play, in the picture. assessment Here, the veins of a how leaf plants are actually modeled develop. as This a led network of pipes for transporting fluids to the cells, and a growth simplified mechanism model, is taking 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 of to an leaf types such as Maple and Mulberry.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.
Here Natural we science see motivated a Xia’s great model intersection of between plant fields, development. including Xia’s natural model science, includes mathematics, certain programming, parameters representing the thickness of the veins, and analysis the cost of algorithms. 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.
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 consider that a we have some hypothetical model of plant development, which runs in discrete time, and takes place on a discrete grid. At The any point in time, the “plant” consists of some squares in the grid grid. – each occupied square is one cell of the plant. It is initialized to some collection of root cells, and which the we’ll algorithm stipulate – will make a system connected horizontal segment–the base of the plant. There is a deterministic algorithm giving the rules that about defines how a process – specifies which new cells get added on each iteration. Let’s The suppose complete the evolution root cells must make a connected horizontal segment, which is the base of the plant. plant We assume that the algorithm is deterministic, therefore so that its complete evolution is a function of the length of the its root. base.
Assume Since that cells never get deleted. deleted, Then either 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 evaluate the them, truth or falsity of these hypotheses, either through reasoning or experiment.
Now an algorithm has leads an a interesting double character: life, for it is both a theoretical object, and a description of the empirical behavior of a machine that “runs” the algorithm. Statements So statements about algorithms therefore have both a theoretical interpretation, and an empirical one. interpretation, Statements and about therefore 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. To illustrate these, let’s consider same sample hypotheses.
Now Hypothesis any 1. statement For about all an root algorithm lengths, is both a purely mathematical statement and an empirical statement about the behavior plant of will reach size at least 10 squares. We could solve this problem by analyzing the program, or empirically, using a computing program machine. that So runs we may be able to tackle questions about the growth algorithm using for theoretical all root lengths less than 10. After a small number of iterations, it is guarantee to either stabilize or empirical have methods. grown beyond ten cells.
Consider Hypothesis for 2. example For the claim that for all root lengths, the plant will grows reach without size bound. at This least is 10 still squares. equivalent We to could an solve empirical this statement problem about by analyzing the program, behavior or of empirically, using a program computing that machine: tests no matter what the hypothesis inputs for shape all root lengths less than 10. Each test is performed to by a running machine which performs a single iteration, the growth output algorithm. will After be a small proper number superset of iterations, the input. But this statement is only semi-decidable by experimental methods: an experiment can prove it will false, by stopping at a fixpoint. To prove the statement by means of an experiment, we would have either stabilized to a perform size an less infinite than number 10, of or experiments, grown each larger running than for 10 an cells. infinite amount of time.
Now (Halting consider problem) 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. Itis 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, Hypothesis consider 3. the For 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 possible approach.
Another We type can also examine the computational complexity of analysis the concerns 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 thecomputational 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.