Easy Octave Algorithm 3

Easy Octave Algorithm 3

$$\def\Order{\text{Order}}\def\First{\text{First}} \def\Last{\text{Last}}\def\L{\text{L}} \def\R{\text{R}}\def\Prod{\text{Prod}} \def\t{\text{$\bf t$}}\def\pmax{\text{p\_max}}$$

This page contains an Octave version of Algorithm 3, on page 64 of the B-series book. This function is intended to run equally well on Matlab, SciLab, as well as Octave.

The purpose of the algorithm is to obtain information about trees up to order \pmax of

\begin{align*} \Order(i) &= |\t_i|,\\ \First(p) &= \text{the least $i$ such that } |\t_i|=p\\ \Last(p) &= \text{the greatest $i$ such that } |\t_i|=p\\ \L(i),\R(i) &= \text{if $\L(i)=j$, $\R(i)=k$, then }\t_j* \t_k = \t_i,\\ \Prod(j,k) &= i \text{ such that }\t_j* \t_k = \t_i, \end{align*}

The ambiguity of $L(i)$ and $R(i)$ is resolved as described in the text.

Octave function definition

function [Order, First, Last, L, R, Prod] = algo3(pmax)
  First(1) = 1
  Last(1) = 1
  Order(1) = 1
  n = 1
  for p = 2:pmax
    First(p)= n+1
    for r =1:Last(p-1)
      for l = First(p-Order(r)):Last(p-Order(r))
        if (l==1 | r<=R(l))
          n = n+1
          Prod(l,r)= n
          L(n) = l
          R(n) = r
          Order(n) = p
        else
          Prod(l,r) = Prod(Prod(L(l),r),R(l))
        end
      end
    end
    Last(p) = n
  end
end

$\to$ B series book
$\to$ Homepage