Recursive Sequence Tree Problem (Original Research in the Field of Comp. Sci)

Question

This question appears also in https://cstheory.stackexchange.com/questions/17953/recursive-sequence-tree-problem-original-research-in-the-field-of-comp-sci. I was told that cross-posting in this particular situation could be approved, since the question can be viewed from many angles.

I am a researcher in the field of computer science. In my research I have the following problem, which I have been thinking for quite a while now.

I think the problem is best explained through an example, so first assume this kind of a tree structure:

                 1, 2, 3, 4, 5, 6, 7, 8
                /                      \
    6, 8, 10, 12                       -4, -4, -4, -4
   /            \                      /             \ 
 16, 20       -4, -4                -8, -8,         0, 0
 /    \       /    \                /     \        /    \
36    -4    -8      0             -16      0      0      0

The root of the tree is always some sequence $s = (s_0, ..., s_{N-1})$ where $N = 2^p$ for some $p \in \mathbb{N}, p>2$. Please note that I am looking for a general solution to this, not just for sequences of the form $1, 2, ..., 2^p$. As you can see, the tree is defined in a recursive manner: the left node is given by

$left(k)=root(k)+root(\frac{N}{2}+k), \quad 0 \leq k \leq \frac{N}{2}$

and the right node by

$right(k)=root(k)-root(\frac{N}{2}+k), \quad 0 \leq k \leq \frac{N}{2}$

So, for example, (6 = 1+5, 8 = 2+6, 10 = 3+7, 12 = 4+8) and (-4 = 1-5, -4 = 2-6, -4 = 3-7, -4 = 4-7) would give the second level of the tree.

I am only interested in the lowest level of the tree, i.e., the sequence (36, -4, -8, 0, -16, 0, 0, 0). If I compute the tree recursively, the computational complexity will be $O(N log N)$. That is a little slow for the purpose of the algorithm. Is it possible to calculate the last level in linear time?

If a linear-time algorithm is possible, and you find it, I will add you as an author to the paper the algorithm will appear in. The problem constitutes about 1/10 of the idea/content in the paper.

If a linear-time algorithm is not possible, I will probably need to reconsider other parts of the paper, and leave this out entirely. In such a case I can still acknowledge your efforts in the acknowledgements. (Or, if the solution is a contribution from many people, I could credit the whole math SE community.)

Answer 1

As others have pointed out, the transformation you're asking for is called the Hadamard transform (it essentially works like a discrete Fourier transform). While the "trivial" matrix multiplication takes $O(n^2)$ time, the structure of the matrix allows the computation to be done in $O(n\log n)$ time. However, it's less than like that this can be speeded up further, because that might imply a faster bound for the FFT, which is a major open problem.

Answer 2

The $n$th (counting from $1$) term of the lowest level of the tree with root $1..2^p$ is:

$n=1$: $ \ \ \ \ \ \ \ 2^{k-1}(2^k+1) $
which is the $2^k$th triangular number, because when the left branch is followed the sum of all the numbers at each node met remains constant.

$n=2^i+1$: $\ \ \ \ \ \ \ 2^{k+i-1} $
The first time a right branch is taken, the constant sequence $-2^{n-1}...-2^{n-1}$ occurs, and always following the left branch after that doubles each term.

$0$
for other $n$ because taking the right branch once gives a constant sequence, and a sequence of zeroes the next time the right branch is taken.

Answer 3

For the case where $p=3$ and an arbitrary sequence $(s_{1},...,s_{8})$ I constructed the matrix: $M=\begin{bmatrix} 1& 1& 1& 1& 1& 1& 1& 1\\ 1&-1& 1&-1& 1&-1& 1&-1\\ 1& 1&-1&-1& 1& 1&-1&-1\\ 1&-1&-1& 1& 1&-1&-1& 1\\ 1& 1& 1& 1&-1&-1&-1&-1\\ 1&-1& 1&-1&-1& 1&-1& 1\\ 1& 1&-1&-1&-1&-1& 1& 1\\ 1&-1&-1& 1&-1& 1& 1&-1\\ \end{bmatrix}$ Such that the $i^{th}$ leaf: $L_{i}=\sum^{N}_{j=1}s_{j}M[i,j]$

Stupidly implemented (assuming that $M$ can be built for free!) this would take $O(n^{2})$ time. Of course in computing these sums work can be saved: for example

$L_{1}=\sum^{N}_{i=1}s_{i}$ and $L_{\frac{N}{2}+1}=\sum^{\frac{N}{2}}_{i=1}s_{i}-\sum^{N}_{i=\frac{N} {2}+1}s_{i}$

If we compute the two summations in $L_{\frac{N}{2}+1}$ separately we can combine them into two solutions, $L_{1}$ and $L_{\frac{N}{2}+1}$, in constant time. However it is my intuition that a divide-and-conquer strategy modeled on such techniques would fail to improve on your already observed bound of $O(N log(N))$.

I believe that if there is no exploitable structure to the root sequence then the recursive definition you propose is asymptotically optimal. (I'll look into a way to prove this assertion.)

Answer 4

This is more of a comment, but it's too big for the comment block. An interesting note on Kaya's matrix $\mathbf{M}$: I believe that it can be defined recursively for any value of $p$. (I should note here that this is my belief. I have yet to prove it...)

That is, let $\mathbf{M}_p$ be the matrix for the value of $p$ (here, let's remove the bound on $p\gt2$).

Let $\mathbf{M}_1 = \begin{pmatrix}1 & 1 \\ 1 & -1\end{pmatrix}$.

Then $\mathbf{M}_n = \begin{pmatrix} \mathbf{M}_{n-1} & \mathbf{M}_{n-1} \\ \mathbf{M}_{n-1} & -\mathbf{M}_{n-1}\end{pmatrix}$.

Ah Ha! Thanks to some searches based off of Suresh Venkat's answer, I found that this matrix is called the Walsh Matrix. Multiplying this matrix by a column vector of your first sequence provides a column vector of the bottom sequence.

As a side note, this makes an almost fractal-like pattern when colored. :)
The above is for $p=4$.

EDIT: I'm almost sure I've seen a graphic similar to the one above before. If someone recognizes something similar, that would be great...