On plant growth and form

September 28, 2013

How quickly does the number of leaves on this plant increase, and why?

The photo above is of a Schlumbergera truncata (or “Christmas cactus”), which my mother (from whom I got the parent plant) calls “Woman’s tongue”. The latter might be seen as a rather sexist definition (pointy and forked..) but I guess it’s an old heritage, from when the world was younger..

Anyway, how fast do the leaves increase in number, and what drives the general form of the plant?
Say we have initially N branches, each that can generate one to three leaves (branching factor p), more or less at random.
If the branching factor were constant and identical for all branches, after one generation we would see 2N to 4N leaves; after two, 3N to 16N, or, for the j-th branch: L_j = \sum\limits_i{l_{i\,j}}.
The number of leaves l_i at each level i is seen to be \Theta(l_{i-1}) where the bound constants are \min(p) and \max(p).

In the real world, a branch has spatial extent, with each leaf occupying a volume, with no intersections or overlaps in \mathbb{R}^3. Moreover, the leaves seek and thrive in sunlight (phototropism), which conditions their orientation and size.
Therefore we could represent a plant as a vector field, with “streamlines” (nutrient direction) and “polarization” (orientation to sunlight).
Gravity, through the self-weight loading of the branches and capillary diffusion of nutrients, obviously plays a part.
We can sketch the processes at play in the following, informal manner. First some notation: for leaf k of level i, the leaf size s_{i\,k}, orientation \alpha_{i\,k}, sunlight exposure (intensity flux) \phi_{i\,k}, viability (function of exposure and distance from the root) v_{i,k}, repulsion potential (function of size and distance to nearest leaf neighbors) \rho_{i\,k}, branch node stiffness \sigma_{i\,k}, which increases as the leaf matures.
Moreover we can define the branch vitality v_b as the sum over all the parent leaves (viability upstream).
s \rightarrow \phi , \rho, \sigma (leaf size influences exposure, repulsion and stiffness)
\phi, v_b, \sigma \rightarrow s, v, \alpha (exposure, viability and stiffness influence leaf size, viability and leaf angle)
\rho \rightarrow \phi (repulsion influences exposure through position: model requires collision and ray-tracing, which require considerable computational effort)
\alpha_{i-1\,k} \rightarrow \alpha_{i\,k}
\alpha \rightarrow \phi, but also
\phi \rightarrow \alpha
As each leaf matures, it becomes larger in size, stiffer and possibly its exposure efficiency reaches a plateau.

Recursive algorithms

September 14, 2013

A recursive algorithm calls itself with a subset of the initial data until its base case is reached (e.g. data cannot be split further).

The canonical example is the factorial operation: x! = x (x-1) (x-2) \cdots 2 .
A straightforward Python function that implements this idea follows:

def fact(x):
    if x <= 1:
        return 1
    else:
        return x*fact(x-1)

In practice, recursion actually can speed up the execution of divide-and-conquer (DNQ) algorithms (i.e. in which the initial problem is sequentially split in more manageable sub-problems), as discussed in the next section.

Analysis: the Master Theorem
An asymptotic estimate of the running time T of a recursive DNQ algorithm with deterministically equal size subproblems is given by the following formula: \displaystyle T(n) \leq a T(\frac{n}{b}) + O(n^d), where n is the data size, a \geq 1 and b >  1 are the number of recursive calls per level (i.e. the branching factor of the recursion tree) and the associated reduction in input size, and O(n^d) describes the computational effort associated with preprocessing (i.e. all that is done before the recursions begin).
One can then identify three cases (for simplicity, n is assumed to be a power of b):

  • If a = b^d then T(n) = O(n^d \log n)
  • If a < b^d then T(n) = O(n^d)
  • If a > b^d then T(n) = O(n^{\log_b a})
  • Open source lab tools

    Scientific instrumentation tends to be expensive: the long r&d&calibration cycles necessary to produce a precise and reliable tool have a direct impact on prices. However, there is a growing number of initiatives that aim to distribute or sell low-cost, “open” tools/techniques, e.g. http://www.openbiotech.com, http://publiclab.org.

    Will openness foster science education and proliferation, specifically in places that cannot afford branded machinery? Is low-cost an observer-independent synonym for low-quality? where quality might mean any combination of reproducibility, availability of debug/maintainance support, etc.

  • The order of things ; what college rankings really tell us – M. Gladwell

    Not exactly news, but this piece from the New Yorker explores how various – arbitrary – choices of metrics used to rank higher education institutions (e.g. graduation rate, tuition etc.) lead to very different results.

    This would not be of much consequence, if these charts were not routinely touted as authoritative by the school deans themselves, and used in all media to bias the perception of “excellence”.

  • NSA: Possibly breaking US laws, but still bound by laws of computational complexity – S. Aaronson

    Scott Aaronson argues that the most widely used “attacks” on citizens’ privacy are the most straightforward (“side-channel”, e.g. lobbying either the standardization committees to put forward weak encryption protocols or commercial software vendors to plant backdoors in their network services) and do not involve disproving mathematically-proven techniques. Social engineering, old as security itself.

    Bruce Schneier, a prominent security expert, gives a few practical tips to have a better illusion of online privacy.

Last but not least, XKCD’s analysis is ever so accurate:

(embedded from http://xkcd.com/1269/ )

Area were an Italian progressive rock band, until the premature death of their frontman, Demetrio Stratos.
I find the sheer creativity and sense of freedom conveyed by their sound to be so refreshing.

Below, one of their albums. Enjoy!

The first assignment for Algorithms 1 is an estimation for the percolation threshold in an n-by-n array of sites; the system is said to percolate whenever there exists an uninterrupted series of connections between the top “edge” and the bottom one.

We need a fast lookup for the neighborhood of any given site; the neighbors() method checks whether a site is in the middle or on the sides or corners of the grid:

def neighbors(ii, n):
    "returns list of neighbors of ii in n-by-n grid"
    l = []
    if mod(ii, n) > 0:
        l.append(ii-1)
    if mod(ii-n+1, n) > 0 or ii == 0:
        l.append(ii + 1)
    if ii > n-1:
        l.append(ii - n)
    if ii < n*(n-1):
        l.append(ii + n)
    return l

I use two lists: L is a pointer array as in the previous post and O contains the state tags (‘#’ for closed, ‘.’ for open site). There are two extra sites, serving as roots for the top, resp. bottom sites.

def percolation_frac(L, O, sites):
    for ii, isite in enumerate(sites):
        O[isite] = '.'
        if isite < n:
            L[isite] = ridxTop
        elif n*(n-1) < isite <= N:
            L[isite] = ridxBot
        neighb = neighbors(isite, n)
        for inb in neighb:
            if O[inb]=='.':
                L = wqupc2(L, isite, inb)                
        if L[-1]==L[-2]: 
            """ percolation: 
            top and bottom virtual sites 
            belong to same component
            """
            pf = float(ii) / N
            return pf

As there is no analytical means of predicting when the percolation phase transition is going to occur, we just run the experiment in Monte Carlo mode (many times with randomized initialization), and average the per-run percolation threshold estimate.
Theory tells us that in a square lattice, this value lies around 0.5927 .
My implementation bumps into a few false positives, possibly due to the order in which the union operation is performed, thereby skewing the average more toward 0.6something. Need to look into this.

Union-find Algorithms

August 25, 2013

Started following Coursera-Princeton’s Algorithms 1.
Being a non-computer scientist, I started missing these theoretical foundations in some of my recent scientific work, so this course might fill a few gaps.
Too bad they don’t offer any completion certificate (as other Coursera courses do), therefore I won’t be submitting the programming exercises (Java, btw).
Instead, I’ll work on the assignments in Python, to my heart’s content.

We start from the very top: n objects belonging to m \leq n disjoint sets (“connected components”, in graph terms).
Often one wishes to query whether two items belong to the same set and, in case, merge two sets.
If sets are represented as trees, a common tree root node indicates that two given items belong to the same set.

Tree root-find with recursion
Data structure: L is a pointer list, a list of integers which can be traversed recursively to find the root (i.e. root of element i is L[ ... L[ i ] ... ] ):

def root(L,ii):
    "ridx = tree root of element ii"
    "rd = depth of ii"
    ridx = ii
    rd = 0
    if L[ii] != ii:
        ridx, rd = root(L, L[ii])
        rd += 1    
    return ridx, rd

The branch() method outputs the list of nodes connecting ii to its root:

def branch(L,ii):
    "return branch from ii to root as list"
    Lout=[ii]
    if L[ii] != ii:
        Lout = Lout + branch(L, L[ii]) 
    return Lout

There is an interesting discussion about recursion in Python and its real implications here, the take-home message being simply that one should not implement iterative procedures (‘loops’) as recursion.

Quick-Union
This algorithm needs the items to be arranged in a set of trees (a ‘forest’), so that the set query is simplified to an identity test of the respective tree roots.
Using the code above, this simply reads:

def qu(L, ii1, ii2):
    "attach subtree of ii2 to root of ii1"
    ridx1, rd1 = root(L, ii1)
    ridx2, rd2 = root(L, ii2)
    L[ridx1] = ridx2
    return L

A shortcoming of this approach is that trees tend to get tall and skinny, so k searches in them, in the worst case, require O(k n) operations.

Weighted Quick-Union
The complexity of a search on Union-Find trees can be kept manageable by weighting, i.e. one subtree in WQU is attached to the second’s root if the former’s size is smaller.
A more precise notion of size is in order: e.g. the total number of elements in the subtree or the subtree depth.
If we settle for the latter definition (union-by-depth),

def wqu(L, ii1, ii2):
    "weighted quick union"
    "attach subtree of ii2 to subtree of ii1,"
    "if the root distance of former is smaller"
    ridx1, rd1 = root(L, ii1)
    ridx2, rd2 = root(L, ii2)
    if rd1 <= rd2:
        L[ridx1] = ridx2
    else:
        L[ridx2] = ridx1
    return L  

This balancing helps to keep the complexity of a search on L at n+k\log_2(n) (where \log_2(n) is the average number of subtree size doublings).

Weighted Quick-Union with Path Compression
An optimization on WQU is given by “path compression”: at union time, all the parents of the node to be attached are set to be the root node of the larger tree.
A (single-pass) WQUPC code reads:

def wqupc2(L, ii1, ii2):
    "WQU with path compression"
    B1 = branch(L, ii1)
    B2 = branch(L, ii2)
    rd1 = len(B1)
    rd2 = len(B2)
    ridx1 = B1[-1]
    ridx2 = B2[-1]
    if rd1 <= rd2:
        for ii in B1:
            L[ii] = ridx2
    else:
        for ii in B2:
            L[ii] = ridx1
    return L   

While doing what it says on the label, the code above uses two recursive calls to find the branch roots (with the known memory and depth size limitations of recursion), storage of the branches and a loop along the smaller of the two branches.
A smarter implementation is clearly necessary for large-scale applications.
If the search tree can be “flattened out” maximally, the complexity of a union search can be further reduced so as to approach (but never reach) the size n of the data items.
That is, k union-find operations on n objects organized in a flattened tree need less than c \left( n + k \log^*_2(n) \right) array accesses, where \log^*() is the iterated log function (Hopcroft-Ullman, Tarjan).
BTW, the iterated logarithm is defined as the number of times \log() has to be applied in order to obtain \leq 1, and is an extremely slowly growing function (e.g. \log^*(2^{2^{16}})\sim 5).

Results and conclusions
We list the theoretical worst-case computational burden, along with typical figures for the average branch depth of the trees generated with each algorithm (obtained with sets of n=1000 integers, after 10^5 random union operations):

  • Quick-union
    Complexity of k searches on n items: O(k n)
    Average branch depth range: 124 – 133
  • Weighted quick-union
    Complexity of k searches on n items: O( n + k log2(n) )
    Average branch depth range: 5.3 – 8.3
  • Weighted quick-union with path compression
    Complexity of k searches on n items: O( n + k log*2(n) )
    Average branch depth: 2.01 (variations at the third decimal)

Path compression clearly minimizes the overhead associated with finding the set label of large collections of items.
Simple code leading to very deep mathematics and enabling huge-scale computation .. my appetite, on the other hand, is growing quickly.

A few days ago, mid-July, a fish die-off took place in the Venice lagoon [IT].

The authorities [IT] isolated the high oxygen level in water as the culprit, in turn due to an abnormally large seaweed growth (which has been attributed in part to the anomalous climate pattern since the spring: hot and rainy).
It is believed that certain non-indigenous algal varieties, brought to the lagoon on the hulls of cargo ships are thriving in the local ecosystem (yet another game of blame-the-immigrant?).
I meant to educate myself on the details for a while now but never found the time.

Seaweed or not, the environmental shock is propagating up the food chain.
Seagulls are already looking miserable, and very few are flying, some noticed.

From a very utilitarian and human-centric point of view, the locals don’t feed on seagull meat, and Venice as a whole has a rather open food system (most of it is imported, as there is precious little agriculture on a couple of the lagoon islands, certainly not enough to support the whole population) but these facts leave me pondering.

However other species might be relying on the ones presently in danger, as predator-prey systems [EN] are in a feedback relationship (a concept which our customer-supermarket culture has alienated us from).

I certainly hope we are not witnessing the start of a local environmental collapse.
The Venice lagoon is a unique pool of biodiversity, and its extinction would mean yet another shame on humankind’s record.

Instead of recalling why this seemingly innocuous chubby Rastafarian is and has been one of the spearheads of contemporary debate about future for .. three decades now, let’s focus on this monologue of his recently recorded by EDGE.

Lanier debates that the widespread usage of networking has reduced the individual to a trade object of corporations and markets, rather than empowered a new middle class that “creates value out of their minds and hearts”.

The promise of the early Internet, to horizontally connect individuals in a heterogeneous global but ultimately personalized trading ground, transformed in a brutal ecosystem where there is no strategy, no planning, only instantaneous profit-oriented logic.
In this heavily peaked pyramid, players that are unable to perform real-time, ubiquitous information gathering and decision making are simply left out, as a necessary byproduct of an “early adopter” effect: the first takes all.
(Can this be considered a consequence of finite resources/finite “context size” and/or of small-world network characteristics? Just my personal note, will think about this)

He also points at possible interpretations of up-and-coming technological developments and their use in counteracting this “trend” to restore the production of value to the individual user, which is, he argues, the only way for civilization not to end as either “Matrix or Marx” (avoidable catchy quote).

Enjoy this hour-long thought-provoking rollercoaster blah blah, it will crack your mind open like a veritable crowbar!

[blip.tv http://blip.tv/play/hLJxgs77WAA%5D
http://edge.org/conversation/the-local-global-flip

TL;DR

Open Source Ecology

August 23, 2011

To recognize that human civilization needs to re-learn to live IN the ecosystem, and not OFF it.

This is the philosophical manifesto and the life project of Marcin Jakubowski and a growing crew of concerned inventors, builders, makers; to exploit centuries of technological advances and package them as open-source hardware tools for community building, with locality and sustainability as core values.

More concretely, quoting from the Working Assumptions of the Open Source Ecology wiki,

Civilization are shaped by their resource base. The resource base is what gives people power. By controlling others through an economic or social hierarchy, we can control resources, and thus gain power. Resource conflicts occur because people have not yet learned to manage resources without stealing. Society has not transcended the brute struggle for survival. We remain on the bottom steps of Maslow’s pyramid. Transcending resource conflicts by creating abundance, first for hundreds, then for thousands of people, is now possible if knowledge flows openly and advanced technology is applied to produce goods.

and

Education, media, and social engineering programs have subjugated human integrity to passive consumerism, with its related problems (resource conflicts, loss of freedom such as wage slavery). The only way out of this is creating a framework within which humans can prosper: provision of true education, learning of practical skills, stewardship of land, advanced technology for the people, and open access to economically significant know-how.

See Marcin make his point about transcending artificial scarcity:

Catching up

August 23, 2011

As I see now, I’ve been a very irresponsible blogger, leaving what was intended to be my latest online brainchild in the dust of oblivion for more than two years.
Not that I feel that guilty about this: I didn’t have anything worthy to share with the amorphous and faceless internet crowd.
Call it a very refined sense of self-censorship, as opposed to the easy trigger of too many compulsive self-elected online opinionists.

This post serves then to mark the end of an era of my life and the beginning of a new one: after obtaining my M.Sc.EE from DTU Fotonik (DK), I will move on to starting a Ph.D. in the Netherlands.

I’ll keep you (sort of) posted,