#StackBounty: #data-structures #dynamic-programming Encoding a tree

Bounty: 50

Let $A$ be an $m times n$ matrix. Let $F(A,S(t),t)$ be a program function, where $t$ is an integer counter beginning at $0$ and stopping at some $k leq m,$ and such that $S(0)$ is empty. The function first iterates $t=1$ and then operates on $A$ in such a way that indices for a subset of columns of $A$ are stored in $S(1).$ For each index $k in S(1),$ the program recursively calls itself and collects another subset of columns of $A$ that depend on which $k in S(1)$ is under examination. How should $S$ be constructed to record the indices of each branch $k$ of $S(1)$ so that the indices in further recursive calls remain connected and in order with their respective parent indices?

I have not programmed in years, so I apologize if the question is poorly worded, and would welcome any editing or correction if clarification is needed.

In short, I need to set up some kind of data structure $S$ for indices of $A$ that can be described as a set of trees; the pseudocode I have written intends to traverse branches of these trees, operating on the columns corresponding to the stored indices.

My problem is that I do not know what data structure to use to store the indices properly. I thought of creating an array for each branch that follows each possible line of recursive calls of my program, but it becomes hard to think of even how to label these arrays, as I do not know beforehand how many I need nor how many recursive calls my program will make prior to termination. My only other thought was to use a language like MATLAB that could create an adjacency matrix for each tree belonging to each index $k$ collected in the first function call, but I am not quite sure how I could program this.

Any help would be appreciated!

EDIT: Here is the pseudocode for the function:

The function receives a matrix $A$ and a vector $b.$ The matrix is assumed to have more columns than rows, so that solutions will be underdetermined (and therefore infinite over real and complex fields, and likely large for finite fields), assuming the system has a solution to begin with.

My job is to find all minimal support solutions, or solutions to the system that have the most 0’s as entries.

Of course (as part of my dissertation shows, oddly for the first time in published literature over every finite field, though it has been shown for binary and for real/complex already) the problem is NP-Hard, making the program my advisor and I devised hopelessly exponential – but it is what it is; my advisor wanted me to sort of start something that might continue in the spirit of the SAT solvers out there, I guess, since algorithms that seek minimal support solutions over finite fields are (at the time of this post) comparatively few.

===================

FUNCTION $MinSup([A|b],r)$

Matrix $A$, vector $b$ (as an augmented system), “depth” $r$

initialize $A=A_0,$ $b=b_0,$ $r=1$

ASSUPTION: Ax=b has at least one solution, $m=numrows(A) < n=numcolumns(A)$, and A is row-independent.

RETURNS: Support for the set of minimal support vectors $X$ to the system $Ax=b.$

PSEUDOCODE (sorry, SE is forcing weird formatting I cannot fix)

  1. Form augmented system $[A|b].$ (EDIT: No longer needed as the program receives an augmented system from the start)

  2. Use row operations on $[A|b]$ until column b has a 1 on top and 0’s on the bottom (doing row exchanges to get a nonzero top if necessary).

  3. Look for any rows that have all zeros from rows $r$ through m (and a nonzero top). Record these indices in $S.$

    1. If S is not empty, then for each $k in S,$ if $r=1$ RETURN the set $x_k=(a_k)^{-1}e_k$ and $x_j=0$ otherwise (solutions are weight one). If $r neq 1,$ for each $k in S$ BACKSOLVE column $k$ and RETURN each smallest resulting minimal support solution (the matrices $A$ sent to the function when $r>1$ will have $r-1$ columns of the identity matrix already).

Else

  1. For all columns that have a nonzero top row entry, record the indices of each column in $S.$ Iterate $r=r+1.$ If $r=m$ then RETURN all $n$ choose $m$ solutions as your minimal support set.

  2. ELSE For each index $k in S,$ BACKSOLVE column $k$ (we need to use row $r-1$ at this point to pivot for each of these, and of course store the augmented system somewhere in case we need to return to this level). There should be a copy of (a multiple of) column $k$ as the “new $b.$” Send this updated augmented system and index $A’, b’,r$ to another call of $MinSup([A|b],r).$

========

There will probably be a small parent program that can cull through multiple responses for the MinSup calls. Essentially, I keep calling until I “hit the jackpot,” or the deepest iteration $r$ for which my row-exchanged update to $b$ on that particular call identifies a perfect multiple for rows $r$ and below (has all zeros from row $r+1$ to $m$).

As anyone can see, this is obviously a combinatorial nightmare, but it is what it is and I have to program it – and given that my advisor is now one year past retirement, and knows nothing but Mathematica, I’ll have to program it on that somehow. It is ugly, but it is what it is.


Get this bounty!!!