We present a unification and generalization of sequentially and hierarchically semi-separable (SSS and HSS) matrices called tree semi-separable (TSS) matrices. Our main result is to show that any dense matrix can be expressed in a TSS format.  Here, the dimensions of the generators are specified by the ranks of the Hankel blocks of the matrix. TSS matrices satisfy a graph-induced rank structure (GIRS) property. It is shown that TSS matrices generalize the algebraic properties of SSS and HSS matrices under addition, products, and inversion. Subsequently, TSS matrices admit linear time matrix-vector multiply, matrix-matrix multiply, matrix-matrix addition, inversion, and solvers.

TSS matrices, HSS matrices, SSS matrices, GIRS, rank-structured matrices

§ INTRODUCTION

Matrices in applied problems of interest often exhibit a structure of low rank in their off-diagonal blocks. These structures have, for instance, been observed in the discretization of integral equations, Schur complements of discretizations of PDEs, Cauchy-like matrices, evaluations of potentials, and companion matrices, amongst others. Many frameworks have been proposed to efficiently represent these low-rank structures so that efficient linear algebra operations could be performed with such matrices. This includes the fast multiple method (FMM) [14], semi-separable and quasi-separable matrices [17, 3, 13], sequentially semi-separable (SSS) matrices [7, 6], hierarchically semi-separable (HSS) matrices [11, 20], $\mathcal{H}$- and $\mathcal{H}^2$-matrices [4, 16, 15], and hierarchically off-diagonal low-rank (HODLR) matrices [1, 2]. These frameworks are all related and have their benefits, pitfalls, and special use cases. An exact analysis of the matter is however beyond the scope of this paper.

This paper is concerned with the structure that arises from the inverse of a (block-)sparse matrix whose adjacency graph is a tree. This will generally be a dense matrix but with a special low-rank structure. In particular, if we look at sums and products of such matrices, they retain these structures, even though they no longer are the inverse of a sparse matrix. None of the aforementioned frameworks or representations can capture these low-rank structures efficiently. In this paper, we present a new class of representations for rank-structured matrices that actually can capture these structures exactly. We call these representations tree semi-separable (TSS) matrices.

Interestingly, TSS matrices simultaneously unify and generalize SSS and HSS matrices. A main technical contribution in our paper is a construction algorithm that obtains a minimal TSS representation for any dense matrix. This algorithm is, in effect, a unification and generalization of the algorithms for doing the same for SSS and HSS matrices. As an important byproduct, we prove the universality theorem (<Ref>). Given an arbitrary matrix, this theorem guarantees the existence of a TSS representation with the dimensions of its generators specified by the ranks of certain sub-blocks of the matrix, i.e., the so-called Hankel blocks. This result will allow us to generalize certain algebraic properties of TSS matrices which are known to already hold for the SSS and HSS cases. We show that TSS matrices satisfy a graph-induced rank structure (GIRS) property (see [8]) and describe the properties of TSS under addition, products, and inversion. Finally, we describe the algorithms for matrix-vector multiply and solution of linear systems.

It is well-known that SSS and HSS matrices are used extensively in practice. TSS matrices are a more flexible drop-in replacement for HSS and SSS matrices. We anticipate that this flexibility can lead to even further improvements in many practical applications. This is however the subject of future work.

The remainder of this paper is outlined as follows. In <Ref>, we give a quick review of SSS and HSS matrices. <Ref> introduces TSS matrices in detail. The algebraic properties of TSS matrices are discussed in <Ref>. In <Ref>, we discuss the construction algorithm, and along with it, the proof of the universality theorem (<Ref>).  <Ref> covers the fast matrix-vector multiply algorithm and the procedure for efficiently solving a linear system involving TSS matrices.

§ A BRIEF RECAP ON SSS AND HSS MATRICES

This section briefly reviews the definitions of SSS and HSS matrices.
We emphasize that we use a rather unconventional, and admittedly, redundant notation in the definitions of both SSS and HSS matrices. However, this is done intentionally to establish a direct link with TSS matrices that will require more detailed notation. <Ref> covers SSS matrices and <Ref> covers HSS matrices. <Ref> briefly summarizes performing algebra with SSS and HSS matrices. For more details on the algorithms themselves, we recommend [6, 7]
for SSS and [20, 11, 18, 19] for HSS. A more tutorial-styled introduction to the subject is given in [10].

§.§ SSS matrices

Sequentially semi-separable (SSS) matrices were first introduced in [12] in a study to generalize systems theory to the time-varying case.  To define SSS matrices, let $m_i,n_i\in \naturals$ for $i\in \left\lbrace 1,\ldots,K\right\rbrace$ and $\weight{(i,i+1)}\in \naturals$ for $i\in \left\lbrace 1,\ldots,K-1\right\rbrace$ and introduce the matrices $\Dmat^i  \in \field^{m_i \times n_i}$ for $i\in \left\lbrace 1,\ldots,K\right\rbrace$,  $\Bmat^i_{i+1} \in \field^{\weight{(i,i+1)} \times n_i }$ for $i\in \left\lbrace 1,\ldots,K-1\right\rbrace$,
$\Umat^i_{i+1,i-1} \in \field^{\weight{(i,i+1)} \times \weight{(i-1,i)}}$ for $i\in \left\lbrace 2,\ldots,K-1\right\rbrace$, $\Cmat^i_{i-1} \in \field^{m_i \times \weight{(i-1,i)}}$ for $i\in \left\lbrace 2,\ldots,K\right\rbrace$, $\Pmat^i_{i-1} \in \field^{\weight{(i,i-1)} \times n_i}$ for $i\in \left\lbrace 2,\ldots,K\right\rbrace$, $\Wmat^i_{i-1,i+1 } \in \field^{\weight{(i,i-1)} \times \weight{(i+1,i)}}$ for $i\in \left\lbrace 2,\ldots,K-1\right\rbrace$, $\Qmat^i_{i+1 } \in \field^{m_i\times \weight{(i+1,i)}}$ for $i\in \left\lbrace 1,\ldots,K\right\rbrace$. Next, define

\begin{equation}
\mat{A}_{ij } := \begin{cases}
\Dmat^{i} & i=j  \\
\Cmat^{i}_{i-1} \Umat^{i-1}_{i,i-2}  \cdots \Umat^{j+1}_{j+2,j} \Bmat^{j}_{j+1}   & i> j \\
\Qmat^{i}_{i+1} \Wmat^{i+1}_{i,i+2}  \cdots \Wmat^{j-1}_{j-2,j} \Pmat^{j}_{j-1}   & i < j
\end{cases}. \label{eq:SSS}
\end{equation}

A sequentially semi-separable (SSS) matrix $\mat{A}\in\field^{M \times N}$, with $M=\sum^K_{i=1} m_i$ and $N=\sum^K_{i=1} n_i$, is the block-partitioned matrix with block entries specified by (<ref>). For example, in the case of $K=4$, an SSS matrix takes on the form

\begin{equation}
\mat{A} = \begin{bmatrix}
\Dmat^1               &          \Qmat^1_2 \Pmat^2_1             &    \Qmat^1_2 \Wmat^2_{1,3} \Pmat^3_2  &    \Qmat^1_2 \Wmat^2_{1,3} \Wmat^3_{3,4} \Pmat^4_3    \\
\Pmat^{2}_1 \Bmat^1_2   &  \Dmat^2  &  \Qmat^2_3 \Pmat^3_{2} & \Qmat^2_3 \Wmat^3_{4,2} \Pmat^4_3  \\
\Cmat^{3}_2 \Umat^{2}_{1,3} \Bmat^1_2          &  \Cmat^{3}_2 \Bmat^2_3         &  \Dmat^3 & \Qmat^3_4 \Pmat^4_3      \\
\Cmat^{4}_2 \Umat^{3}_{4,1} \Umat^{2}_{3,1} \Cmat_1     &  \Bmat^{4}_3 \Umat^{3}_{2,4} \Cmat^2_4  & \Cmat^{4}_3 \Bmat^3_2   & \Dmat^4
\end{bmatrix}.
\label{eq:SSSSn4}
\end{equation}

The entries of the SSS representation (<ref>) can be seen as the result of decomposing $\mat{A}$ as the sum of a causal and anti-causal Linear Time Variant (LTV) system.

§.§ HSS matrices

While SSS matrices have their origins in systems theory, hierarchically semi-separable (HSS) matrices arose independently to simplify the algebra of the fast multipole method (FMM) so that it has favorable properties under inversion. To define HSS matrices, we recursively partition a matrix $\mat{A}\in\field^{M \times N}$ in a hierarchic manner. This process is best described through a binary tree.

Assume that the nodes of the binary tree are indexed by a post-ordered traversal of the tree and let $r$ denote its root node. Furthermore, let $\leftchild(l)$ (respectively, $\rightchild(l)$) denote the left (respectively, right) child of node $l$ in the binary tree. If $l$ is a terminating point of the recursion, or equivalently, a leaf node of the binary tree, we set $\mat{A}^{l} = \Dmat^{l}\in\field^{m_{l} \times n_{l}}$. On the other hand, if $l$ is a non-terminating point of the recursion, we set

\begin{equation}
\mat{A}^{l} = \begin{bmatrix}
\mat{A}^{\leftchild(l)}   & \mathcal{Q}^{\leftchild(l)}_{ l }   \Vmat^{l}_{ \leftchild(l) , \rightchild(l) }  \mathcal{B}^{\rightchild(l) }_{l}  \\
\mathcal{Q}^{\rightchild(l) }_{l}   \Vmat^{l}_{\rightchild(l),\leftchild(l)}  \mathcal{B}^{\leftchild(l)}_{l}  & \mat{A}^{\rightchild(l)}
\end{bmatrix},
\end{equation}

where $\mat{A}^{\leftchild(l)}\in\field^{ m_{\leftchild(l)} \times   n_{\leftchild(l)} }$, $\mat{A}^{\rightchild(l)}\in\field^{m_{\rightchild(l)} \times  n_{\rightchild(l)}}$,
$m_{l} = m_{\leftchild(l)} + m_{\rightchild(l)}$, and $n_{l} = n_{\leftchild(l)} + n_{\rightchild(l)}$. Furthermore, $\mathcal{Q}^{ \leftchild(l)}_{l} = \Qmat^{ \leftchild(l) }_{l} \in \field^{m_{\leftchild(l)} \times \weight{(l, \leftchild(l))}}$ (respectively, $\mathcal{Q}^{ \rightchild(l)}_{l} = \Qmat^{ \rightchild(l) }_{l} \in \field^{m_{\rightchild(l)} \times \weight{(l, \rightchild(l))}}$) if $\leftchild(l)$ (respectively, $\rightchild(l)$) is a leaf node of the binary tree. Otherwise,

\mathcal{Q}^{\leftchild(l)}_{l} = \begin{bmatrix}
\mathcal{Q}^{\leftchild(\leftchild(l))}_{ \leftchild(l) }  \Wmat^{\leftchild(l)}_{ \leftchild(\leftchild(l))  , l }     \\
\mathcal{Q}^{\rightchild(\leftchild(l))}_{\leftchild(l)}   \Wmat^{\leftchild(l)}_{ \rightchild(\leftchild(l)),l}
\end{bmatrix}, \qquad \mathcal{Q}^{\rightchild(l)}_{l} = \begin{bmatrix}
\mathcal{Q}^{\leftchild(\rightchild(l))}_{\rightchild(l) }  \Wmat^{\rightchild(l)}_{\leftchild(\rightchild(l)),l}     \\
\mathcal{Q}^{\rightchild(\rightchild(l))}_{\rightchild(l)}   \Wmat^{\rightchild(l)}_{ \rightchild(\rightchild(l)),l}
\end{bmatrix}.

with $\Wmat^{\leftchild(l)}_{ \leftchild(\leftchild(l)),l} \in \field^{ \weight{(\leftchild(l), \leftchild(\leftchild(l)))} \times \weight{(l, \leftchild(l))}}$, $\Wmat^{\leftchild(l)}_{ \rightchild(\leftchild(l)),l} \in \field^{ \weight{(\leftchild(l), \rightchild(\leftchild(l)))} \times \weight{(l, \leftchild(l))}}$,

$\Wmat^{\rightchild(l)}_{ \rightchild(\leftchild(l)),l} \in \field^{ \weight{(\rightchild(l), \rightchild(\leftchild(l)))} \times \weight{(l, \rightchild(l))}}$, $\Wmat^{\rightchild(l)}_{ \rightchild(\rightchild(l)),l} \in \field^{ \weight{(\rightchild(l), \rightchild(\rightchild(l)))} \times \weight{(l, \rightchild(l))}}$. Similarly, $\mathcal{B}^{ \leftchild(l)}_{l} = \Bmat^{ \leftchild(l) }_{l} \in \field^{ \weight{(\leftchild(l),l)}  \times n_{\leftchild(l)}}$ (respectively, $\mathcal{B}^{ \rightchild(l)}_{l} = \Bmat^{ \rightchild(l) }_{l} \in \field^{ \weight{(\rightchild(l), l)} \times n_{\rightchild(l)} }$) if $\leftchild(l)$ (respectively, $\rightchild(l)$) is a leaf node of the binary tree. Otherwise,

\begin{eqnarray*}
\mathcal{B}^{ \leftchild(l)}_{l}    & = & \begin{bmatrix}
\Umat^{\leftchild(l)}_{l , \leftchild(\leftchild(l)) } \mathcal{B}^{\leftchild(\leftchild(l))}_{\leftchild(l)}   &  \Umat^{ \leftchild(l)   }_{ l , \rightchild(\leftchild(l)) } \mathcal{B}^{\rightchild(\leftchild(l))}_{\leftchild(l)}
\end{bmatrix},  \\
\mathcal{B}^{ \rightchild(l)}_{l}  & = &   \begin{bmatrix}
\Umat^{\rightchild(l)}_{l,\leftchild(\rightchild(l))} \mathcal{B}^{\leftchild(\rightchild(l))}_{\rightchild(l)}    & \Umat^{\rightchild(l)}_{ l , \rightchild(\rightchild(l)) } \mathcal{B}^{\rightchild(\rightchild(l))}_{\rightchild(l)}
\end{bmatrix}
\end{eqnarray*}

with $\Umat^{\leftchild(l)}_{l, \leftchild(\leftchild(l))} \in \field^{ \weight{(\leftchild(l),l)}  \times \weight{( \leftchild(\leftchild(l)),\leftchild(l))} }$, $\Umat^{\leftchild(l)}_{ \rightchild(\leftchild(l)),l} \in \field^{ \weight{(\leftchild(l), l)}  \times  \weight{(\rightchild(\leftchild(l)), \leftchild(l))}  }$,
$\Umat^{\rightchild(l)}_{ \leftchild(\rightchild(l)),l} \in \field^{ \weight{(\rightchild(l), l)}   \times \weight{(\leftchild(\rightchild(l)), \rightchild(l))} }$,  $\Umat^{\rightchild(l)}_{ l, \rightchild(\rightchild(l))} \in \field^{ \weight{(\rightchild(l),l)}  \times \weight{(\rightchild(\rightchild(l)) , \rightchild(l))}  }$. At the root level, we set $\mat{A} = \mat{A}^{r}\in\field^{m_{r} \times n_{r}}$ with $m_{r}=:M$ and $n_{r}=:N$. For example, the matrix

\begin{eqnarray}
\mat{A} & = &  \begin{bmatrix} \Dmat^{1} &
\Qmat^{1}_{3} \Vmat^{3}_{1,2} \Bmat^{2}_{3}  &   \Qmat^1_{5}  \Wmat^3_{1,5} \Vmat^{5}_{3,4} \Bmat^{4}_{5} \\
\Qmat^{1}_{3} \Vmat^{3}_{2,1} \Bmat^{1}_{3}   & \Dmat^{2}  &      \Qmat^2_{5}  \Wmat^3_{1,5} \Vmat^{5}_{3,4} \Bmat^{4}_{5}           \\
\Qmat^4_{5}  \Vmat^5_{4,3} \Umat^{3}_{5,1} \Bmat^{1}_{3}     &    \Qmat^4_{5}  \Vmat^5_{4,3} \Umat^{3}_{5,2} \Bmat^{2}_{3}          &  \Dmat^{4}
\end{bmatrix} \label{eq:HSSexample} \\
& = & \begin{bmatrix}
\mat{A}^{3}   & \mathcal{Q}^{3}_{5}   \Vmat^{5}_{3,4}  \mathcal{B}^{4 }_{5}  \\
\mathcal{Q}^{4}_{5}  \Vmat^{5}_{4,3}  \mathcal{B}^{3}_{5}  & \mat{A}^{4} \end{bmatrix} \nonumber \\
& = &  \mat{A}^5  \nonumber
\end{eqnarray}

is an HSS matrix.

§.§ Algebra with SSS and HSS matrices

SSS and HSS matrices share common algebraic properties. Any dense matrix can be converted into an SSS or HSS matrix. The dimensions of the generators, and thus the efficiency of the representation, are specified by the ranks of the off-diagonal (i.e., so-called Hankel) blocks. Sums and products of SSS (respectively HSS) matrices are again SSS (respectively HSS) but with a doubling in the size of the generators. The inverse of an SSS (respectively HSS) is an SSS (respectively HSS) matrix of the same generator dimensions. SSS (respectively HSS) representations of matrices that have small Hankel block ranks can be multiplied with vectors in linear time. The same holds for the solve operation. For the latter,  one common approach to both representations is a lifting technique that solves the linear system as a larger block-sparse system [5]. All these commonalities do not come from nowhere, since SSS and HSS belong to the same family of a more general class of matrices.

§ TREE SEMI-SEPARABLE (TSS) MATRICES

This section formally introduces TSS matrices. To do so, we first introduce some terminology in <Ref> and <Ref>. The actual definition of TSS matrices is given in <Ref>. Finally, <Ref> describes SSS and HSS as special cases of TSS matrices.

§.§ Tree graphs

Let $\Graph = (\NodeSet,\EdgeSet)$, with node set $\mathbb{V}=\lbrace1,2,\ldots,K\rbrace$, be a connected acyclic undirected graph. Here, for reasons that will be clear later, the edge set $\EdgeSet$ is unconventionally interpreted as a collection ordered pairs of nodes[Instead of unordered pairs!], but with the property that $(i,j)\in \EdgeSet$ if and only if $(j,i)\in \EdgeSet$, i.e., the edges in both directions are included.  Since $\Graph$ is acyclic, every pair of nodes $i,j \in\Graph$ is connected by one, and only one, path[Here we do not allow for self-intersecting paths. A “path” passing from node $i$ to node $j$ by passing through $i$ and going to $k$, to subsequently come back to node $j$, is not considered a valid path!]

of specific length $p$.

The graph $\Graph$ may be viewed as a tree.
Indeed, if $\kNeighbor(i;k)$ denotes the set of $k$-neighbors of node $i\in\mathbb{V}$, i.e., the set of nodes that can be reached by $i$ through traversing a path of length $k$, then a tree $\Graph(r)$ is induced by picking any $r\in \NodeSet$ and setting

_0 = {r },   _1 = (r;1),  _2 = (r;2),  …,  _L = (r;L).

The depth of the tree specified by the partition $\NodeSet = \NodeSet_0 \cup \NodeSet_1 \cup \ldots \cup \NodeSet_{L}$ equals $L$ and is defined as the smallest number with the property $\kNeighbor(r; L+1) = \emptyset$.  The level $l$ at which a node $i\in\NodeSet_l$ resides within the tree is denoted by $\Level(i)$. An edge $(i,j)\in\EdgeSet$ with $\Level(i)=\Level(j)-1$ is called an up-edge. Likewise, if $\Level(i)=\Level(j)+1$ it is called a down-edge

Within the setting of the tree $\Graph(r)$, a node $j\in \NodeSet$ is consider to be child of $i\in \kNeighbor(j) = \kNeighbor(j;1)$ if $i\in\NodeSet_{l}$ and $j\in\NodeSet_{l+1}$. Vice versa, $i$ is the parent of node $j$. The notion of children and parents may be further generalized: $j\in \NodeSet$ is a $k$-child of $i\in\kNeighbor(j;k)$ (and vice versa $i$ is the $k$-parent of node $j$) if $i\in\NodeSet_{l}$ and $j\in\NodeSet_{l+k}$. Two nodes $i,j\in\NodeSet_l$ are siblings ($k$-siblings) if they both share the same parent node $w\in \NodeSet_{l-1}$ ($w\in \NodeSet_{l-k}$).  Naturally, a node will have at most one $k$-parent, but it may have many $k$-children or $k$-siblings.  The parent ($k$-parent) of a node $i\in \NodeSet$ is denoted by $\Parent(i)$ ($\Parent(i;k)$) and this set may be empty (e.g., for the root node). The set of children ($k$-children) of node $i\in \NodeSet$ is denoted by $\Children(i)$ ($\Children(i;k)$). The set of siblings ($k$-siblings) of node $i\in \NodeSet$ is denoted by $\Siblings(i)$ ($\Siblings(i;k)$). The set of descendants of node $i\in \NodeSet$ and including $i$ itself is denoted by

(i):= i ∪(i;1) ∪(i;2) ∪…∪(i;L-(i)).

and we set  $\Descendantscompl(i):= \NodeSet \setminus \Descendants(i)$. A node $i\in\mathbb{V}$ is called a leaf node if its set of descendants is empty. Note that leaf nodes may reside at any level of the tree. The set of leaf nodes of an acyclic fully connected graph is denoted by $\Leaves(\Graph)$.

§.§ Graph-partitioned matrices

We can associate the graph $\Graph=(\NodeSet,\EdgeSet)$ with a block-partitioned matrix. To do this, associate each node with an input of size $n_i\in \naturals$ and an output of size $m_i$. Furthermore, let

M=∑_i∈ m_i,   N=∑_i∈ n_i.

We may then introduce a matrix $\TSS\in \field^{M\times N}$ that is assembled from the system of linear equations

\begin{equation}\label{eq:block_matrix_multiplication}
\vect{b}_{i} = \sum_{j\in \NodeSet} \TSS\nodeid{i,j} \vect{x}_j, \quad i\in\NodeSet.
\end{equation}

That is,

\begin{equation}
\TSS := \begin{blockarray}{ccccc}
& 1 & 2 & \cdots & K \\
\begin{block}{c[cccc]}
1 &  \TSS\nodeid{1,1} & \TSS\nodeid{1,2} & \cdots &\TSS\nodeid{1,K} \\
2 & \TSS\nodeid{2,1} & \TSS\nodeid{2,2} & \cdots &\TSS\nodeid{2,K} \\
\vdots & \vdots & \vdots &  & \vdots \\
K & \TSS\nodeid{K,1} & \TSS\nodeid{K,2} & \cdots &\TSS\nodeid{K,K} \\
\end{block}
\end{blockarray},
\end{equation}

where $\TSS\nodeid{i,j}\in \field^{m_i\times n_j}$ is the matrix associated with the contribution of the input and node $i\in\NodeSet$ to the output at node $j\in\NodeSet$. Given two subsets $\NodeSubset{A} = \lbrace i_1,  \ldots, i_A \rbrace\subset \NodeSet$ and $\NodeSubset{B} = \lbrace j_1, \ldots, j_B \rbrace\subset \NodeSet$ we sub-matrices of $\TSS$ with the notation

A,B = cccc
j_1     ⋯    j_B

i_1       i_1,j_1      ⋯   i_1,j_B

⋮    ⋮          ⋮

i_A     i_A,j_1      ⋯   i_A,j_B

Actual entries of the matrix $\TSS$ or its block-components $\TSS\nodeid{i,j}$ are accessed using a square-bracket notation, i.e., $\TSS[k,l]$ and $\TSS\nodeid{i,j}[k,l]$ refer to the $(k,l)$-th entry of $\TSS$ and $\TSS\nodeid{i,j}$, respectively.

The matrix $\TSS$ alongside with $\Graph$ is referred to as a graph-partitioned matrix. Note that this definition is agnostic to whether $\Graph$ is a tree or not. Nonetheless, in this paper, we will limit ourselves to only acyclic undirected graphs that may also be viewed as trees.

§.§ Definition of TSS matrices

A tree semi-separable (TSS) matrix is a specific construction of a graph-partitioned matrix $\TSS$ associated with a fully connected and acyclic graph $\Graph = (\NodeSet,\EdgeSet)$. To form a TSS matrix from $\Graph$, we equip the graph with weights on the edges of the graph. That is, every edge $(i,j) \in \mathbb{E}$ is associated with a weight $\weight{(i,j)} \in \naturals$.  The set  $\lbrace \weight{e} \rbrace_{e\in \EdgeSet}$ is referred to as the rank-profile on $\Graph$ and intuitively describes a collection of state dimensions of “flow” moving between nodes of the graph.  The following matrices may be introduced along with the elements of the graph(see FIG):

* input-to-output operator $\Dmat^k \in \field^{m_k\times n_k}$ for every node $k\in\NodeSet$,

* input-to-edge operator $\Inp^k_j \in \field^{\weight{(k,j)}\times n_k}$ for every node $k\in \kNeighbor(j)$ with adjoining edge $(k,j)\in \EdgeSet$,

* edge-to-edge operator $\Trans^k_{i,j}\in \field^{\weight{(j,k)}\times \weight{(j,k)}}$ for every pair of adjoining edges $(j,k)\in\EdgeSet$ and $(k,i)\in\EdgeSet$ with $i,j\in \kNeighbor(k)$,

* edge-to-output operator $\Out^k_i \in \field^{m_k \times\weight{(i,k)}}$ for every edge $(i,k)\in\EdgeSet$ with adjoining node $i\in\kNeighbor(k)$.

A TSS matrix is then defined as follows.

Let $\Graph = (\NodeSet,\EdgeSet)$ be a connected acyclic undirected graph. A tree semi-separable (TSS) matrix with input dimensions $\lbrace n_i \rbrace_{i \in \NodeSet}$, output dimensions $\lbrace m_i \rbrace_{i \in \NodeSet}$, and rank-profile $\lbrace \weight{e} \rbrace_{e\in \EdgeSet}$, is a graph-partitioned matrix $\TSS\in\field^{M\times N}$ of size $M=\sum_{i\in \NodeSet} m_i$ by $N=\sum_{i\in \NodeSet} n_i$  whose block-entries are specified by

\begin{equation}
\TSS\nodeid{i,j} = \begin{cases}
\Dmat^i & i=j \\
\Out^i_{p_{\nu-1}} \Trans^{p_{\nu-1}}_{i,p_{\nu-2}}      \cdots \Trans^{p_2}_{p_3,p_1} \Trans^{p_1}_{p_2,j} \Inp^j_{p_1} & i \ne j,
\end{cases}
\end{equation}

with $j=p_0-p_1-\cdots-p_{\nu}=i$ being the unique path from node $j\in\NodeSet$ to node $i\in\NodeSet$.

[circle, draw, fill=black, inner sep=1.5pt] (myNode) at (0,0) ;
[right] at (myNode.north) $k$;

Every node $k\in \NodeSet$ is equipped with an input-to-output operator.

[circle, draw, fill=black, inner sep=1.5pt] (myNode) at (0,0) ;
[right] at (myNode.north) $k$;

[-] (myNode) – ++(330:1.2cm) node[midway, right, pos=1.0] $(k,j)$;

Every node $k\in \kNeighbor(j)$ with adjoining edge $(k,j)\in \EdgeSet$ is equipped with an input-to-edge operator.

[circle, draw, fill=black, inner sep=1.5pt] (myNode) at (0,0.5) ;
[right] at (myNode.north) $k$;

[-] (myNode) – ++(290:1.2cm) node[midway, right, pos=1.0] $(k,j)$;
[-] (myNode) – ++(250:1.2cm) node[midway, left, pos=1.0] $(j,k)$;

Every pair of adjoining edges $(j,k)\in\EdgeSet$ and $(k,i)\in\EdgeSet$ is equipped with an edge-to-edge operator.

[circle, draw, fill=black, inner sep=1.5pt] (myNode) at (0,0) ;
[right] at (myNode.north) $k$;

[-] (myNode) – ++(210:1.2cm) node[midway, left, pos=1.0] $(i,k)$;

Every edge $(i,k)\in\EdgeSet$ with adjoining node $i\in\kNeighbor(k)$ is equiped with an edge-to-output operator.

TSS operators associated with elements of the graph $\Graph$.

Definition <ref> is agnostic to a tree ordering. Once a root node $r\in\NodeSet$ for the graph is picked, we may introduce additional nomenclature for the corresponding tree $\Graph(r)$ to distinguish between different input-to-edge, edge-to-edge, and edge-to-output operators:

* An input-to-edge operator $\Inp^k_j$ is denoted by $\Bmat^k_j$ if $j\in\NodeSet$ is a parent of $k\in\NodeSet$  (i.e., $j=\Parent(k)$), and by $\Pmat^k_j$ if $j\in\NodeSet$ is a child of $k\in\NodeSet$  (i.e., $j\in\Children(k)$).

* An edge-to-edge operator $\Trans^k_{i,j}$ is denoted by $\Umat^k_{i,j}$ if $j\in\NodeSet$ and $i\in\NodeSet$ are respectively a child and parent of $k\in\NodeSet$ (i.e., $j\in\Children(k)$ and $i=\Parent(k)$), by $\Vmat^k_{i,j}$ if $i,j\in\NodeSet$ are siblings of $k\in\NodeSet$ (i.e. $i,j\in\Siblings(k)$), and by $\Wmat^k_{i,j}$ if $j\in\NodeSet$ and $i\in\NodeSet$ are respectively a parent and child of $k\in\NodeSet$ (i.e., $j=\Parent(k)$ and $i\in\Children(k)$).

* An edge-to-output operator $\Out^k_i$ is denoted by $\Cmat^k_i$ if $i\in\NodeSet$ is a child of $k\in\NodeSet$ (i.e., $i\in\Children(k)$), and by $\Qmat^k_i$ if $i\in\NodeSet$ is a parent of $k\in\NodeSet$ (i.e., $i=\Parent(k)$).

The input-to-output, input-to-edge, edge-to-edge, and edge-to-output operators can systematically be organized in so-called spinner tables at every node $k\in\NodeSet$. Let $i_1,i_2,\ldots,i_p\in\Children(k)$ be an enumeration of the set of children and $j=\Parent(k)$  the parent node (see <Ref>). The generating matrices of a TSS representation can be tabulated as

\begin{equation}
S^{k} = \begin{blockarray}{ccccccc}
& i_1 & i_2& \cdots & i_p & j & \Inp   \\
\begin{block}{c[cccccc]}
i_1 & \cdot & \Vmat^{k}_{i_1,i_2}  & \cdots & \Vmat^{k}_{i_1,i_p} &  \Wmat^{k}_{i_1,j}  & \Pmat^{k}_{i_1}   \\
i_2 & \Vmat^{k}_{i_2,i_1}    & \cdot & & \Vmat^{k}_{i_2,i_p}  & \Wmat^{k}_{i_2,i_1}    &  \Pmat^{k}_{i_2}  \\
\vdots &  \vdots    &  & \ddots & \vdots & \vdots    &  \vdots  \\
i_p & \Vmat^{k}_{i_p,i_1}    & \Vmat^{k}_{i_p,i_2}  & \cdots & \cdot & \Wmat^{k}_{i_p,j}    &  \Pmat^{k}_{i_p}  \\
j & \Umat^{k}_{j,i_i}    & \Umat^{k}_{j,i_2} & \cdots & \Umat^{k}_{j,i_p} & \cdot & \Bmat^k_j   \\
\Out & \Cmat^{k}_{i_1} & \Cmat^{k}_{i_2} & \cdots & \Cmat^{k}_{i_p} &  \Qmat^{k}_{j} & \Dmat^k  \\
\end{block}
\end{blockarray}, \qquad k\in\NodeSet.
\end{equation}

This categorization of the generating matrices of a TSS representation and their organization into spinner tables shall be useful later when
we discuss the conversion of a dense matrix to a TSS representation.

For now, to illustrate our definition with an example, consider the following tree

\begin{equation*}
\mathbb{G}_a(4) = \begin{matrix}
\circ_1 & - & \circ_3  & - &  \bm{\circ_4 }\\
&   &    |     &   &         \\
&   &  \circ_2 &   &
\end{matrix},
\end{equation*}

with node $4$ (highlighted in bold) being the root node. The TSS matrix for the corresponding tree $\Graph_a(4)$
has the structure

= ccccc
1     2      3     4

1     ^1       ^1_3 ^3_1,2 ^2_3        ^1_3 ^3_1      ^1_3 ^3_1,4 ^4_3

2     ^2_3 ^3_2,1 ^1_3     ^2      ^2_3 ^3_2     ^2_3 ^3_2,4  ^6_4

3     ^3_1 ^1_3      ^3_2 ^2_3      ^3     ^3_4 ^6_4

4     ^4_3 ^3_4,1 ^1_3     ^4_3 ^3_4,2 ^2_3        ^4_3 ^3_4      ^4

The spinner tables are

S^1 = ccc

3     ·    ^1_3

^1_3      ^1

,    S^2 = ccc

3     ·     ^2_3

^2_3      ^2

,       S^4 = ccc

3    ·         ^4_3

^4_3      ^4

\begin{equation*}
S^{3} = \begin{blockarray}{ccccc}
& 1& 2& \mathbf{4} & \Inp  \\
\begin{block}{c[cccc]}
1 & \cdot & \Vmat^{3}_{1,2}   &  \Wmat^{3}_{1,4}  & \Pmat^{3}_1  \\
2 & \Vmat^{3}_{2,1}    & \cdot & \Wmat^{3}_{2,4}    &  \Pmat^{3}_2  \\
\mathbf{4} & \Umat^{3}_{4,1}    & \Umat^{3}_{4,2}    & \cdot & \Bmat^3_4  \\
\Out & \Cmat^{3}_1 & \Cmat^{3}_2 & \Qmat^{3}_4  & \Dmat^4  \\
\end{block}
\end{blockarray},
\end{equation*}

where the parent nodes of each spinner table are highlighted in bold.

[circle, draw, fill=black, inner sep=1.5pt] (myNode) at (0,0) ;

[right] at (myNode.east) $k$;

[-] (myNode) – ++(90:1.2cm) node[midway, above, pos=1.0] $(k,j)$;
[-] (myNode) – ++(215:2.25cm) node[midway, below, pos=1.0] $(k,i_1)$;
[-] (myNode) – ++(240:1.5cm) node[midway, below, pos=1.0] $(k,i_2)$;
[-] (myNode) – ++(325:2.25cm) node[midway, below, pos=1.0] $(k,i_p)$;

at (.5,-1) …;

Node $k\in\NodeSet$ with its children $i_1,i_2,\ldots,i_p \in \Children(k)$ and parent $j = \Parent(k)$.

§.§ HSS and SSS matrices as special subcases

While SSS and HSS matrices have their origins in disparately different fields. TSS matrices bring them under one roof as it includes SSS matrices and HSS matrices as special subcases. To further elaborate on this, consider line graph

\begin{equation*}
\mathbb{G}_b(4) = \begin{matrix}
\circ_1 & - & \circ_2 & - & \circ_3  & - & \bm{\circ_4} \\
\end{matrix},
\end{equation*}

with node 4 chosen as the root node. The spinner tables associated with $\mathbb{G}_b(4)$ are of the form

S^1 = ccc

2     ·    ^1_2

^1_2      ^1

,   S^2 = cccc
1     3

1     ·     ^2_1,3         ^2_1

3      ^2_3,1            ·    ^2_3

^2_1        ^2_3      ^2

S^3 = cccc
2     4

2     ·     ^3_2,4         ^3_2

4      ^3_4,2            ·    ^2_4

^3_2       ^3_4      ^3

,   S^4 = ccc

3     ·    ^4_3

^4_3      ^4

and generate the SSS matrix shown in (<ref>). In general, all linearly ordered line graphs produce a TSS matrix of the type described in <Ref> if the final node is chosen as the root node.

HSS matrices, on the other hand, are TSS matrices associated with binary trees. For example, consider the post-ordered binary tree

\begin{equation*}
\mathbb{G}_c(5) = \begin{matrix}
\circ_1 & - & \circ_3  & - &  \bm{\circ_{5}} \\
&   &    |     &   &    |     \\
&   &  \circ_2 &   &   \circ_4  \\
\end{matrix}
\end{equation*}

with node $5$ as the root node. Furthermore, suppose that $n_3=m_3=n_5=m_5=0$, i.e., all the non-leaf nodes are “empty nodes” with zero input and output dimensions. The spinner tables of $\mathbb{G}_c(5)$ are

S^1 = ccc

3     ·    ^1_3

^1_3      ^1

,  S^2 = ccc

3     ·     ^2_3

^2_3      ^2

,   S^4 = ccc

5    ·         ^3_5

^3_5      ^3

S^3 = ccccc
1     2     5

1     ·     ^3_1,2      ^3_1,5     ·

2      ^3_2,1      ·     ^3_2,5      ·

5      ^3_5,1       ^3_5,2        ·    ·

·    ·     ·    ·

,   S^5 = ccccc
3     4

3     ·     ^5_3,4       ·

4      ^5_4,3      ·     ·

·    ·     ·

and generate the HSS matrix in (<ref>). In general, all post-ordered binary tree graphs produce a TSS matrix of the type described in <Ref>, provided that all non-leaf nodes are empty nodes of zero dimensions.

In all other cases, the TSS matrices are neither SSS nor HSS. The example of the previous section and the upcoming example in <Ref> belong to this category.

§ ALGEBRAIC PROPERTIES OF TSS MATRICES

This section discusses important algebraic properties of TSS matrices. <Ref> describes the graph-induced rank structure (GIRS) property of TSS matrices. <Ref> introduces the universality theorem, which states that any matrix can be converted into a TSS representation. <Ref> discusses the properties of TSS matrices under addition, products, and inversion.

§.§ Graph-induced rank structure of TSS matrices

Inverses of tridiagonal matrices are examples of dense matrices whose off-diagonal blocks possess low-rank qualities. For graph-partitioned matrices $(\TSS,\Graph)$, this property of off-diagonal low rank can be expressed in a more general framework through the notion of graph-induced rank structure (GIRS). To describe GIRS, we first introduce the concept of a Hankel block. Let $\NodeSubset{A} \subset \NodeSet$ and let $\bar{\NodeSubset{A}} = \NodeSet \setminus \NodeSubset{A}$ denote its complement. We may (block-)permute $\TSS$ such that

Π_1 Π_2 =
A, A      A, A̅

A̅, A      A̅, A̅

We call  $\TSS\nodeid{\bar{\NodeSubset{A}}, \NodeSubset{A}}$ the Hankel block induced by $\NodeSubset{A}$. An edge $(i,j) \in \EdgeSet$ is called a border edge with respect to $\NodeSubset{A}$  if $i\in \NodeSubset{A}$ and $j\in \bar{\NodeSubset{A}}$. The number of border edges, or the edge count, induced by $\NodeSubset{A}$ is denoted $\EdgeCount(\NodeSubset{A})$. The GIRS property is defined as follows.

The pair $(\TSS,\Graph)$ is said to have a graph-induced (low-)rank structure if there exists a sufficiently small constant $c\geq 0$ such that

A̅, A  ≤c (A),     ∀A ⊂.

TSS matrices turn out to satisfy the GIRS-property, provided that the rank-profile $\lbrace r_{e} \rbrace_{e\in \EdgeSet}$ is uniformly bounded by a small constant. To see this, one must exploit the direct correspondence between the path followed from node $j\in\NodeSet$ to $i\in\NodeSet$ in $\Graph$ and the associated matrix expression at block-entry $\TSS\nodeid{i,j}$.

We may prove the following result.
A TSS matrix $\TSS\in\field^{M\times N}$ with rank-profile $\lbrace \weight{e} \rbrace_{e\in \EdgeSet}$ satisfies the GIRS-property for $c=\max_{e\in \EdgeSet} \weight{e}$.

Let $\NodeSubset{A} \subset \NodeSet$ and $\bar{\NodeSubset{A}} = \NodeSet \setminus \NodeSubset{A}$. We must show that the rank of $\TSS\nodeid{\bar{\NodeSubset{A}}, \NodeSubset{A}}$ is bounded by $\EdgeCount\left( \NodeSubset{A} \right) \cdot \max_{e\in \EdgeSet} \weight{e}$. Suppose $i\in \NodeSubset{A}$ and $j\in \bar{\NodeSubset{A}}$. Since $\Graph$ is acyclic, there exists a unique path $\Path(i,j)$. By construction, $\Path(i,j)$ first starts at a node in $\NodeSubset{A}$ to eventually transition into a node in $\bar{\NodeSubset{A}}$. It may be possible that $\Path(i,j)$ leaves and enters $\NodeSubset{A}$ multiple times before it finally enters back into $\bar{\NodeSubset{A}}$ one last time to reach node $j$. Write

$$\Path(i,j) = i-\cdots-s-t-\cdots-v-w-\cdots-j,$$

where $(s,t)\in \EdgeSet$ with $s\in \NodeSubset{A}$, $t \in \bar{\NodeSubset{A}}$ marking the first time $\Path(i,j)$ entering $\bar{\NodeSubset{A}}$, and $(v,w)\in \EdgeSet$ with $s\in \NodeSubset{A}$, $t \in \bar{\NodeSubset{A}}$ marking the last time[If $\Path(i,j)$  leaves ] of entering $\bar{\NodeSubset{A}}$. We may factor

\begin{equation}
\TSS\nodeid{j,(v,w)} =  \mat{\Gamma}^{j}_{(v,w)} \mat{\Phi}_{(v,w),(s,t)}    \mat{\Psi}^{i}_{(s,t)}  \label{eq:keyproperty}
\end{equation}

\begin{eqnarray*}
\mat{\Psi}^{i}_{(s,t)}   & := & \begin{cases}
\Inp^s_t  & i=s \\
\Trans^s_{t,*} \cdots  \Trans^*_{*,j} \Inp^i_*  & i\ne s
\end{cases},  \\
\mat{\Phi}_{(v,w),(s,t)}    & := & \begin{cases}
\Id & (s,t)=(v,w) \\
\Trans^v_{w,*} \cdots  \Trans^t_{*,s}  &  (s,t) \ne (v,w)
\end{cases}, \\
\mat{\Gamma}^{j}_{(v,w)}   & := & \begin{cases}
\Out^w_v  & j=w \\
\Out^j_* \Trans^*_{j,*} \cdots  \Trans^v_{*,w}  & j\ne t
\end{cases}.
\end{eqnarray*}

Let $\lbrace e_i \rbrace^{\EdgeCount(A)}_{i=1}\subset \EdgeSet$ denote the set of border edges, and

\begin{eqnarray*}
\Phi :=  \begin{bmatrix}
\Phi_{e_1,e_1}  &  \cdots & \Phi_{e_{1},e_{\EdgeCount(A)}}  \\
\vdots &     & \vdots \\
\Phi_{e_{\EdgeCount(A)},e_1}   & \cdots & \Phi_{e_{\EdgeCount(A)},e_{\EdgeCount(A)}}
\end{bmatrix}.
\end{eqnarray*}

Given (<ref>), it becomes evident that we may factor $\TSS\nodeid{\bar{\NodeSubset{A}}, \NodeSubset{A}} = \mat{\Gamma} \Phi \mat{\Psi}$. Thus,

A̅, A = ∑^ (A)_i=1 e_i ≤( A ) ·max_e∈ e.

§.§ The universality theorem

While <Ref> shows that TSS matrices satisfy the GIRS-property, a question arises whether the converse also holds: does every tree-graph-partitioned matrix that satisfies the GIRS-property admit a TSS representation whose rank-profile is bounded by the GIRS constant? This question is intimately tied to whether TSS are universal representations, i.e., if a TSS representation can be found for any graph-partitioned matrix for which the graph is acyclic and connected.

For SSS and HSS matrices both these questions can be answered in the affirmative. Interestingly, it turns out that the same holds for the more general class of TSS matrices.
Given a graph-partitioned matrix $(\TSS,\Graph)$ with $G$ acyclic and connected, the rank-profile of the corresponding TSS representation can be derived from the ranks of Hankel blocks whose edge count is unity. For a tree, these so-called unit Hankel blocks are quite straightforward to enlist as every edge $(i,j)\in \EdgeSet$ can be uniquely paired with one such unit Hankel blocks. Indeed, once a root node $r\in\NodeSet$ for the graph has been picked, it must hold that either $j=\Parent(i)$ or $i=\Parent(j)$ for the corresponding tree $\mathbb{G}(r)$. Let

\begin{equation*}
\NodeSubset{H}_{(i,j)} = \begin{cases}
\Descendants(i) & j=\Parent(i) \\
\NodeSet \, \setminus  \Descendants(j) & i=\Parent(j)
\end{cases}
\end{equation*}

and let $\UnitHankelBlock{(i,j)}$ denote the Hankel block corresponding with subset $\NodeSubset{H}_{(i,j)}$, i.e., $\UnitHankelBlock{(i,j)} = \TSS\nodeid{\NodeSubset{H}_{(i,j)} , \bar{\NodeSubset{H}}}_{(i,j)}$ with $\bar{\NodeSubset{H}}_{(i,j)} = \NodeSet \setminus \NodeSubset{H}_{(i,j)}$. We have the following result.

Let $(\TSS,\Graph)$ be a graph-partitioned matrix with $\Graph$ being acyclic and connected. Then $\TSS\in\field^{M\times N}$ admits an TSS representation with rank-profile

e = e,     e∈.

Furthermore, such a TSS representation is minimal in the sense that any other TSS representation for $\TSS$ with rank-profile $\lbrace \rho'_{e} \rbrace_{e\in\EdgeSet}$ must necessarily satisfy  $\rho'_{e} \geq \weight{e}$ for all $e\in\EdgeSet$.

The proof of <Ref> is postponed to <Ref> where we shall introduce an explicit algorithm to convert a dense matrix into a TSS representation.
<Ref> yields the following corollary.

Let $(\TSS,\Graph)$ be a graph-partitioned matrix with $\Graph$ being acyclic and connected. Then $\TSS\in\field^{M\times N}$ satisfies the GIRS-property for constant $c>0$ if, and only if, $\TSS\in\field^{M\times N}$ admits a TSS representation with rank-profile $\weight{e}\leq c$ for all $e\in \EdgeSet$.

§.§ Sums, products, and inverses of TSS matrices

The algebraic properties of SSS and HSS matrices under addition, multiplication, and inversion generalize to TSS matrices. The following three propositions may be established from <Ref>.

Let $\TSS_1, \TSS_2 \in \field^{M\times N}$, with $M=\sum_{i\in \NodeSet} m_i$ and $N=\sum_{i\in \NodeSet} n_i$, be TSS matrices of rank-profiles  $\lbrace \weight{1,e} \rbrace_{e\in \EdgeSet}$  and
$\lbrace \weight{2,e} \rbrace_{e\in \EdgeSet}$ associated with the acyclic connected graph $\Graph =(\NodeSet,\EdgeSet)$. Then, $\TSS_3 = \TSS_1 + \TSS_2$ is a TSS matrix of rank profile $\lbrace \weight{1,e} + \weight{2,e} \rbrace_{e\in \EdgeSet}$.

Since $\rank \TSS_3\nodeid{\bar{\NodeSubset{A}}, \NodeSubset{A}} \leq \rank \TSS_1\nodeid{\bar{\NodeSubset{A}}, \NodeSubset{A}} +  \rank \TSS_2\nodeid{\bar{\NodeSubset{A}}, \NodeSubset{A}}$  for any Hankel block induced by $\NodeSubset{A}$, the result directly follows from <Ref>.

Let $\TSS_1\in \field^{M\times N}$  and $\TSS_2 \in \field^{N\times P}$, with $M=\sum_{i\in \NodeSet} m_i$,  $N=\sum_{i\in \NodeSet} n_i$, and $P=\sum_{i\in \NodeSet} p_i$, be TSS matrices of rank-profiles  $\lbrace \weight{1,e} \rbrace_{e\in \EdgeSet}$  and
$\lbrace \weight{2,e} \rbrace_{e\in \EdgeSet}$ associated with the acyclic connected graph $\Graph =(\NodeSet,\EdgeSet)$. Then, $\TSS_3 = \TSS_1 \TSS_2$ is a TSS matrix of rank profile $\lbrace \weight{1,e} + \weight{2,e} \rbrace_{e\in \EdgeSet}$.

\begin{eqnarray*}
\rank \TSS_3\nodeid{\bar{\NodeSubset{A}}, \NodeSubset{A}} & = & \rank \TSS_1\nodeid{\bar{\NodeSubset{A}}, \NodeSubset{A}} \TSS_2\nodeid{\NodeSubset{A}, \NodeSubset{A}}  + \TSS_1\nodeid{\bar{\NodeSubset{A}}, \bar{\NodeSubset{A}}} \TSS_2\nodeid{\bar{\NodeSubset{A}}, \NodeSubset{A}}  \\
& \leq & \rank \left( \TSS_1\nodeid{\bar{\NodeSubset{A}}, \NodeSubset{A}} +  \rank \TSS_2\nodeid{\bar{\NodeSubset{A}}, \NodeSubset{A}}\right)
\end{eqnarray*}

for any Hankel block induced by $\NodeSubset{A}$, the result directly follows from <Ref>.

Let $\TSS \in \field^{N\times N}$, with $N=\sum_{i\in \NodeSet} n_i$, be a non-singular TSS matrix of rank-profile  $\lbrace \weight{e} \rbrace_{e\in \EdgeSet}$ associated with the acyclic connected graph $\Graph =(\NodeSet,\EdgeSet)$. Then, $\TSS^{-1}$ is also a TSS matrix of rank profile $\lbrace \weight{e} \rbrace_{e\in \EdgeSet}$.

Since $\rank \TSS^{-1}\nodeid{\bar{\NodeSubset{A}}, \NodeSubset{A}} = \rank \TSS \nodeid{\bar{\NodeSubset{A}}, \NodeSubset{A}}$ for any Hankel block induced by $\NodeSubset{A}$, the result follows from <Ref>.

§ TSS MATRIX CONSTRUCTION

This section discusses the construction of a TSS representation from a dense matrix provided a tree $\Graph(r)$ and an accompanying partitioning of the matrix. In <Ref> we describe the construction on an illustrative example. The general algorithm is described in <Ref>. The presented algorithm will allow us to prove the universality theorem (<ref>). This is done in <Ref>.

§.§ An illustrative example

Before describing the general algorithm, we first illustrate the construction of a TSS representation on an illuminating example. Consider the tree

\begin{equation*}
\mathbb{G}_d(7) = \begin{matrix}
\circ_1 & - & \circ_5  & - &  \bm{\circ_{7}} \\
&   &    |     &   &    |     \\
&   &  \circ_2 &   &   \circ_6 & - & \circ_4 \\
&   &          &   &   |  &  \\
&   &          &   &   \circ_3  &  \\
\end{matrix},
\end{equation*}

with node $7$ picked as the root node. $\mathbb{G}_b(7)$ is a tree of depth 2 and comprises of the levels: $\NodeSet_0 = \lbrace 7 \rbrace$,  $\NodeSet_1 = \lbrace 5,6 \rbrace$, and $\NodeSet_2 = \lbrace 1,2,3,4 \rbrace$   The corresponding spinner tables and TSS form are shown in <Ref>. It turns out that the generating matrices of the TSS representation can be retrieved from computing low-rank factorizations of the unit Hankel blocks $\UnitHankelBlock{(i,j)}$ in a particular sequence.

\begin{equation*}
S^{1} = \begin{blockarray}{ccc}
\mathbf{5} & i & \\
\begin{block}{[cc]c}
\cdot &  \Bmat^{1}_5 & \mathbf{5}\\
\Qmat^{1}_5  & \Dmat^1  & o \\
\end{block}
\end{blockarray}\quad S^{2} = \begin{blockarray}{ccc}
\mathbf{5} & i & \\
\begin{block}{[cc]c}
\cdot &  \Bmat^{2}_5 & \mathbf{5}\\
\Qmat^{2}_5  & \Dmat^2 & o \\
\end{block}
\end{blockarray}\quad S^{3} = \begin{blockarray}{ccc}
\mathbf{6} & i & \\
\begin{block}{[cc]c}
\cdot &  \Bmat^{3}_6 & \mathbf{6}\\
\Qmat^{3}_6  & \Dmat^3 & o \\
\end{block}
\end{blockarray}, \quad S^{4} = \begin{blockarray}{ccc}
\mathbf{6} & i & \\
\begin{block}{[cc]c}
\cdot &  \Bmat^{4}_6 & \mathbf{6}\\
\Qmat^{4}_6  & \Dmat^4 & o \\
\end{block}
\end{blockarray}
\end{equation*}

\begin{equation*}
S^{5} = \begin{blockarray}{ccccc}
1& 2& \mathbf{7} & i & \\
\begin{block}{[cccc]c}
\cdot &    \Vmat^{5}_{1,2}   &   \Wmat^{5}_{1,7}  &  \Pmat^{5}_1   &1\\
\Vmat^{5}_{2,1}    &   \cdot  &   \Wmat^{5}_{2,7}    &   \Pmat^{5}_2 & 2 \\
\Umat^{5}_{7,1}    &   \Umat^{5}_{7,2}    &    \cdot &   \Bmat^5_7  & \mathbf{7} \\
\Cmat^{5}_1  &  \Cmat^{5}_2 &   \Qmat^{5}_7  & \Dmat^5 & o \\
\end{block}
\end{blockarray}, \quad S^{6} = \begin{blockarray}{ccccc}
3& 4& \mathbf{7} & i & \\
\begin{block}{[cccc]c}
\cdot &  \Vmat^{6}_{3,4}   &    \Wmat^{6}_{3,7}  &   \Pmat^{6}_3   & 3 \\
\Vmat^{6}_{4,3}    &    \cdot &   \Wmat^{6}_{4,7}    &     \Pmat^{6}_{4} & 4 \\
\Umat^{6}_{7,3}    & \Umat^{6}_{7,4}    & \cdot &  \Bmat^6_7  & \mathbf{7} \\
\Cmat^{6}_3 &  \Cmat^{6}_4 &   \Qmat^{6}_7  & \Dmat^6 & o \\
\end{block}
\end{blockarray}
\end{equation*}

\begin{equation*}
S^{7} = \begin{blockarray}{ccccc}
5& 6&  i & \\
\begin{block}{[cccc]c}
\cdot &  \Wmat^{7}_{5,6}    &  \Pmat^{7}_5   &5\\
\Wmat^{7}_{6,5}    &    \cdot    &   \Pmat^{7}_6 & 6 \\
\Cmat^{7}_5 &  \Cmat^{7}_6 & \Dmat^7 & o \\
\end{block}
\end{blockarray}
\end{equation*}

$\TSS = \begin{blockarray}{cccccccc}
1 & 2 & 3 & 4 & 5 & 6 & 7 \\
\begin{block}{[ccccccc]c}
\Dmat^1 &   \Qmat^1_5 \Vmat^5_{1,2} \Bmat^2_5 & \Qmat^1_5 \Wmat^5_{1,7} \Vmat^7_{5,6} \Umat^6_{7,3} \Bmat^3_6 & \Qmat^1_5 \Wmat^5_{1,7} \Vmat^7_{5,6} \Umat^6_{7,4} \Bmat^4_6 &  \Qmat^1_5 P^5_1  & \Qmat^1_{5} \Umat^5_{1,7} \Vmat^7_{5,6} \Bmat^6_7  & \Qmat^1_5 \Wmat^5_{1,7} \Pmat^7_5 & 1 \\
\Qmat^2_5 \Vmat^5_{2,1} \Bmat^1_5 & \Dmat^2 &  \Cmat^2_5 \Wmat^5_{2,7} \Vmat^7_{6,5} \Umat^6_{7,3} \Bmat^3_6 &  \Qmat^2_5 \Wmat^5_{1,7} \Vmat^7_{5,6} \Umat^6_{7,4} \Bmat^4_6 &  \Qmat^2_5 \Pmat^5_{2} & \Qmat^2_5 \Wmat^5_{2,7} \Vmat^7_{5,6} \Bmat^6_7 & \Qmat^2_5 \Wmat^5_{2,7} \Pmat^7_5 & 2  \\
\Qmat^3_6 \Wmat^6_{3,7} \Vmat^7_{6,5} \Umat^5_{7,1} \Bmat^1_5 &  \Qmat^3_6 \Wmat^6_{3,7} \Vmat^7_{6,5} \Umat^5_{7,2} \Bmat^2_5 & \Dmat^3 & \Qmat^3_6 \Vmat^6_{3,4} \Bmat^4_6 & \Qmat^3_6 \Wmat^6_{3,7} \Vmat^7_{6,5} \Bmat^5_7 & \Qmat^3_6 \Pmat^6_3 & \Qmat^3_6 \Wmat^6_{3,7} \Pmat^7_{6} & 3 \\
\Qmat^4_6 \Wmat^6_{4,7} \Vmat^7_{6,5} \Umat^5_{7,1} \Bmat^1_5 &    \Qmat^4_6 \Wmat^6_{4,7} \Vmat^7_{6,5} \Umat^5_{7,2} \Bmat^2_5 & \Qmat^4_6 \Vmat^6_{4,3} \Bmat^3_6 & \Dmat^4 & \Qmat^4_6 \Wmat^6_{4,7} \Vmat^7_{6,5} \Bmat^5_{7} &  \Qmat^4_6 \Pmat^6_4 & \Qmat^4_6 \Wmat^6_{1,7} \Pmat^7_6 & 4 \\
\Cmat^5_1 \Bmat^1_5 &  \Cmat^5_2 \Bmat^2_5 &   \Qmat^5_{7} \Vmat^7_{5,6} \Umat^6_{7,3} \Bmat^3_6 &  \Qmat^5_7 \Vmat^7_{5,6} \Umat^6_{7,4} \Bmat^4_6 & \Dmat^5 & \Qmat^5_7 \Vmat^7_{5,6} \Bmat^6_7 &  \Qmat^5_7 \Pmat^7_5 & 5 \\
\Qmat^6_7 \Vmat^7_{6,5} \Umat^5_{7,1} \Bmat^1_5 &    \Qmat^6_7 \Umat^7_{6,5} \Vmat^5_{7,2} \Bmat^2_5 &  \Cmat^6_{3} \Bmat^3_6 & \Cmat^6_4 \Bmat^4_{6} &  \Qmat^6_7 \Vmat^7_{7,5} \Bmat^5_7 & \Dmat^6 & \Qmat^6_7 \Pmat^7_6 & 6 \\
\Cmat^7_5 \Umat^5_{7,1} \Bmat^1_5 & \Cmat^7_5 \Umat^5_{7,2} \Bmat^2_5 & \Cmat^7_{6} \Umat^6_{7,3} \Bmat^3_6 & \Cmat^7_6 \Umat^6_{7,4} \Bmat^4_6 &  \Cmat^7_5 \Bmat^5_7 &  \Cmat^7_6 \Bmat^6_{7} & \Dmat^7 & 7 \\
\end{block}
\end{blockarray}

The spinner tables and TSS form associated with the tree $\Graph_b(7)$

To start, we begin with the unit Hankel blocks associated with the edges at the deepest level of the tree. Specifically, from the low-rank factorizations of the unit Hankel blocks $\UnitHankelBlock{(i,j)}=\Xmat{(i,j)} \Ymat{(i,j)}$ with $i\in \NodeSet_2$ and $j=\Parent(i)\in \NodeSet_1$, we shall be able to obtain the $\Bmat$'s of the spinner tables corresponding to the nodes in $\NodeSet_2$ and the $\Cmat$'s of the spinner tables corresponding to the nodes in $\NodeSet_1$. For example, we may write

(1,5) = ccc[c]
2      (1,5)2

3     (1,5)3

4     (1,5) 4

5     (1,5) 5

6     (1,5) 6

7     (1,5) 7

since we know that $\UnitHankelBlock{(1,5)}$ should factor into

2     ^2_5 ^5_2,1

3     ^3_6 ^6_3,7 ^7_6,5 ^5_7,1

4     ^4_6 ^6_4,7 ^7_6,5 ^5_7,1

5     ^5_1

6     ^6_7 ^7_6,5 ^5_7,1

7     ^7_5 ^5_7,1

we may set $\Cmat^5_1 =  \Xmat{(1,5)}\nodeid{5}\in\field^{m_5
\times \weight{(1,5)}}$ and $B^5_1 = \Ymat{(1,5)}\nodeid{1}\in\field^{\weight{(1,5)} \times n_1}$ with $\weight{(1,5)} = \rank\UnitHankelBlock{(1,5)}$. With similar reasoning, we may set $\Cmat^5_2 = \Xmat{(2,5)} \nodeid{5} \in \field^{m_5 \times \weight{(2,5)}}$, $\Bmat^2_5 = \Ymat{(2,5)}\nodeid{2} \in \field^{\weight{(2,5)} \times n_2}$, $\Cmat^6_{3}=\Xmat{(3,6)}\nodeid{6} \in \field^{m_6 \times \weight{(3,6)}}$, $\Bmat^3_6 = \Ymat{(3,6)}\nodeid{3} \in  \field^{\weight{(3,6)} \times n_3}$, $\Cmat^6_4 = \Xmat{(4,6)} \nodeid{6} \in \field^{ m_6 \times \weight{(4,6)} }$, $\Bmat^4_6=\Ymat{(4,6)}\nodeid{4} \in \field^{ \weight{(4,6)} \times n_4}$ with $\rho_{(2,5)} = \rank \UnitHankelBlock{(2,5)}$, $\rho_{(3,6)} = \rank \UnitHankelBlock{(3,6)}$, and $\rho_{(4,6)} = \rank  \UnitHankelBlock{(4,6)}$.

Next, moving one level up the tree by computing low-rank factorizations $\UnitHankelBlock{(i,j)}=\Xmat{(i,j)} \Ymat{(i,j)}$ with $i\in \NodeSet_1$ and $j=\Parent(i)\in \NodeSet_0$, we can obtain the $\Umat$'s and $\Bmat$'s of the spinner tables corresponding to the nodes in $\NodeSet_1$ and the $\Cmat$'s of the spinner tables corresponding to the nodes in $\NodeSet_0$. For example, with our previously computed factorizations, we may write

(5,7)  =  cccc
3         (1,5) 3      (2,5) 3     3,5

4     (1,5)4      (2,5)  4     4,5

6     (1,5) 6      (2,5)  6     6,5

7     (1,5) 7     (2,5)  7     7,5

(1)        (2)      5

The low-rank factorization $\UnitHankelBlock{(5,7)} = \Xmat{(5,7)} \Ymat{(5,7)}$ can be obtained by compressing the matrix

\begin{multline*}
\begin{blockarray}{cccc}
\begin{block}{c[ccc]}
3 &     \Xmat{(1,5)} \nodeid{3}  & \Xmat{(2,5)} \nodeid{3} & \TSS \nodeid{3,5} \\
4 & \Xmat{(1,5)}\nodeid{4}  & \Xmat{(2,5)}  \nodeid{4} & \TSS\nodeid{4,5}   \\
6 & \Xmat{(1,5)} \nodeid{6} &  \Xmat{(2,5)}  \nodeid{6} & \TSS\nodeid{6,5}  \\
7 & \Xmat{(1,5)} \nodeid{7} & \Xmat{(2,5)}  \nodeid{7} & \TSS\nodeid{7,5} \\
\end{block}
\end{blockarray} =
\begin{blockarray}{cc} \begin{block}{c[c]}
3 &   \Xmat{(5,7)} \nodeid{3}   \\
4 & \Xmat{(5,7)} \nodeid{4}   \\
6 & \Xmat{(5,7)} \nodeid{6}   \\
7 & \Xmat{(5,7)}\nodeid{7} \\
\end{block}
\end{blockarray} \begin{bmatrix}
\Zmat{(5,7)}^{\Descendants(1)}   & \Zmat{(5,7)}^{\Descendants(2)} & \Zmat{(5,7)}^5
\end{bmatrix},
\end{multline*}

which sets

\begin{multline*}
\begin{blockarray}{ccc}
\Descendants(1) & \Descendants(2) & 5 \\
\begin{block}{[ccc]}
\Ymat{(5,7)} \nodeid{\Descendants(1)}  & \Ymat{(5,7)} \nodeid{\Descendants(2)} & \Ymat{(5,7)} \nodeid{5}   \\
\end{block}
\end{blockarray}
\! = \!  \begin{blockarray}{ccc}
\Descendants(1) & \Descendants(2) & 5 \\
\begin{block}{[ccc]}
\Zmat{(5,7)}^{\Descendants(1)} \Ymat{(1,5)}   & \Zmat{(5,7)}^{\Descendants(2)} \Ymat{2,5)} & \Zmat{(5,7)}^5  \\
\end{block}
\end{blockarray}.
\end{multline*}

Since $\Ymat{(1,5)} = \Bmat^1_5$, $\Ymat{(2,5)} = \Bmat^2_5$ and $\UnitHankelBlock{(5,7)}$ should factor into

\begin{eqnarray*}
\begin{blockarray}{cc}
\begin{block}{c[c]}
3 & \Qmat^3_6 \Wmat^6_{3,7} \Vmat^7_{6,5}  \\
4 & \Qmat^4_6 \Wmat^6_{4,7} \Vmat^7_{6,5}  \\
6 & \Qmat^6_7 \Vmat^7_{6,5} \\
7 & \Cmat^7_5 \\
\end{block}
\end{blockarray}   \begin{blockarray}{ccc}
\Descendants(1) & \Descendants(2) & 5 \\
\begin{block}{[ccc]}
\Umat^5_{7,1} \Bmat^1_5 & \Umat^5_{7,2} \Bmat^2_5 & \Bmat^5_7 \\
\end{block}
\end{blockarray},
\end{eqnarray*}

we see that $\Cmat^7_5 = \Xmat{(5,7)} \nodeid{7} \in \field^{m_7 \times \weight{(5,7)}}$, $\Umat^5_{7,1} = \Zmat{(5,7)}^{\Descendants(1)} \in \field^{\weight{(5,7)} \times \weight{(1,5)}}$, $\Umat^5_{7,2} = \Zmat{(5,7)}^{\Descendants(2)} \in \field^{\weight{(5,7)} \times \weight{(2,5)}}$, $\Bmat^5_7 = \Zmat{(5,7)}^5 \in \field^{ \weight{(5,7)} \times n_5}$ with $\weight{(5,7)} = \rank \UnitHankelBlock{(5,7)}$. With similar reasoning, we may set $\Cmat^7_6 = \Xmat{(6,7)}\nodeid{7} \in \field^{  m_7 \times \weight{(6,7)} }$, $\Umat^6_{7,3} = \Zmat{(6,7)}^{\Descendants(3)} \in \field^{ \weight{(6,7)} \times \weight{(3,6)} }$, $\Umat^6_{7,4} = \Zmat{(6,7)}^{\Descendants(4)} \in \field^{ \weight{(6,7)} \times \weight{(4,6)} }$, $\Bmat^6_7 = \Zmat{(6,7)}^6 \in \field^{ \weight{(6,7)} \times n_6}$ with $\weight{(6,7)} = \rank \UnitHankelBlock{(6,7)}$.

By now, we have fully climbed up the tree and arrived at the root node. In this process, we have computed all the $\Bmat$'s, $\Umat$'s, and $\Cmat$'s of the TSS representation. This was done by peeling off the terms from the low-rank factorizations of the unit Hankel blocks. To compute the remaining  $\Pmat$'s, $\Vmat$'s, $\Wmat$'s, and $\Qmat$'s, we proceed in the same way. However, the main difference is that we start at the root and work ourselves down the tree towards the leaves.  To start, through computing the low-rank factorizations $\UnitHankelBlock{(j,i)}=\Xmat{(j,i)} \Ymat{(j,i)}$ with $i\in \NodeSet_1$ and $j=\Parent(i)\in \NodeSet_0$, we will able to retrieve the $\Pmat$'s and $\Vmat$'s of the spinner tables corresponding to the nodes in $\NodeSet_0$ and the $\Qmat$'s of the spinner tables corresponding to the nodes in $\NodeSet_1$. For example, we may write

(7,5)  =  ccc
1         (6,7) 1      1,7

2     (6,7)2       2,7

5     (6,7) 5      5,7

(6)        7

Compressing the matrix

1         (6,7) 1      1,7

2     (6,7)2       2,7

5     (6,7) 5      5,7

= cc c[c]
1       (7,5) 1

2     (7,5) 2

5     (7,5) 5

(7,5)^(6)      (7,5)^7

allows us to produce the  low-rank factorization $\UnitHankelBlock{(7,5)} = \Xmat{(7,5)} \Ymat{(7,5)}$ with

(6)        7

(7,5)(6)     (7,5)7

=   cc
(6)        7

(7,5)^(6) (6,7)     (7,5)^7

Since $\Ymat{(6,7)} = \begin{blockarray}{ccc}
3 & 4 & 6 \\
\begin{block}{[ccc]}
\Umat^6_{7,3} \Bmat^3_6 & \Umat^6_{7,4} \Bmat^4_6 & \Bmat^6_7 \\
\end{block}
\end{blockarray}$ and $\UnitHankelBlock{(7,5)}$ should factor into

1     ^1_5 ^5_1,7

2     ^2_5 ^5_2,7

5      ^5_7

cc (6)     7
[cc]  ^7_5,6
^6_7,3 ^3_6     ^6_7,4 ^4_6     ^6_7

we may set $\Qmat^5_{7} = \Xmat{(7,5)} \nodeid{5} \in \field^{m_5 \times \weight{(7,5)}}$, $\Vmat^7_{5,6}= \Zmat{(7,5)}^{\Descendants(6)}  \in\field^{\weight{(7,5)} \times \weight{(6,7)}}$, $\Pmat^7_5  = \Zmat{(7,5)}^7 \in\field^{\weight{(7,5)} \times n_7}$ with $\weight{(7,5)} = \rank \UnitHankelBlock{(7,5)}$. With similar reasoning, we may set $\Qmat^6_{7} = \Xmat{(7,6)} \nodeid{6} \in \field^{m_6 \times \weight{(7,5)}}$, $\Vmat^7_{5,6}= \Zmat{(7,6)}^{\Descendants(5)} \in\field^{\weight{(7,6)} \times \weight{(5,7)}}$, $\Pmat^7_6  = \Zmat{(7,6)}^7 \in\field^{\weight{(7,6)} \times n_7}$ with $\weight{(7,6)} = \rank \UnitHankelBlock{(7,6)}$.

At last, moving one level down, we reach the bottom of the tree. By computing the low-rank factorizations $\UnitHankelBlock{(i,j)}=\Xmat{(i,j)} \Ymat{(i,j)}$ with $j\in \NodeSet_2$ and $i=\Parent(j)\in \NodeSet_1$, we will be able to compute all the remaining terms of TSS representation. Specifically,  will be able to retrieve all the $\Pmat$'s, $\Wmat$'s, and $\Vmat$'s of the spinner tables corresponding to the nodes in $\NodeSet_1$ and the $\Qmat$'s of the spinner tables corresponding to the nodes in $\NodeSet_2$. For example, we may write

(5,1) = cccc
1     (7,5)1      (2,5)1     1,5

(5)      (2)     5

Compressing the matrix

\begin{multline*}
\begin{blockarray}{cccc}
\begin{block}{c[ccc]}
1 & \Xmat{(7,5)}\nodeid{1} &  \Xmat{(2,5)}\nodeid{1} & \TSS\nodeid{1,5} \\
\end{block}
\end{blockarray}  =  \begin{blockarray}{cc} \begin{block}{c[c]}
1 &   \Xmat{(5,1)} \nodeid{1}   \\
\end{block}
\end{blockarray} \begin{bmatrix}
\Zmat{(5,1)}^{\Descendantscompl(5)}  &  \Zmat{(5,1)}^{\Descendants(2)} & \Zmat{(5,1)}^5
\end{bmatrix}
\end{multline*}

allows us to produce the  low-rank factorization $\UnitHankelBlock{(7,5)} = \Xmat{(7,5)} \Ymat{(7,5)}$ with

\begin{multline*}
\begin{blockarray}{ccc}
\Descendantscompl(5) & \Descendants(2) & 5 \\
\begin{block}{[ccc]}
\Ymat{(5,2)} \! \nodeid{\Descendantscompl(5)}  & \Ymat{(5,2)} \!\nodeid{\Descendants(2)} & \Ymat{(5,2)}\! \nodeid{5}   \\
\end{block}
\end{blockarray}
\! = \!
\begin{blockarray}{ccc}
\Descendantscompl(5) & \Descendants(2) & 5 \\
\begin{block}{[ccc]}
\Zmat{(5,1)}^{\Descendantscompl(5)}  \Ymat{(7,5)}   & \Zmat{(5,1)}^{\Descendants(2)}  \Ymat{(2,5)} & \Zmat{(7,5)}^5 \\
\end{block}
\end{blockarray}.
\end{multline*}

Since $\Ymat{(7,5)} = \begin{bmatrix}
\Vmat^7_{5,6} \Umat^6_{7,3} \Bmat^3_6 &   \Vmat^7_{6,5} \Umat^6_{7,4} \Bmat^4_6 &   \Vmat^7_{5,6} \Bmat^6_7  &   \Pmat^7_5
\end{bmatrix}$, $\Ymat{(2,5)} =\Bmat^2_5$ and   $\UnitHankelBlock{(5,1)}$ should factor into

cc  c[c] 1     ^1_5

(5)      (2)     5

^7_5,6 ^6_7,3 ^3_6       ^7_6,5 ^6_7,4 ^4_6       ^7_5,6 ^6_7        ^7_5
^5_1,2 ^2_5      ^5_1

we see that $\Qmat^1_5  = \Xmat{(5,1)} \nodeid{1} \in \field^{m_1 \times \weight{(5,1)}}$, $\Wmat^5_{1,7} = \Zmat{(5,1)}^{\Descendantscompl(5)} \in \field^{\weight{(5,1)} \times \weight{(7,5)}}$,   $\Vmat^5_{1,2} = \Zmat{(5,1)}^{\Descendants(2)} \in \field^{\weight{(5,1)\times \weight{(2,5)}}}$,  $\Pmat^5_1 = \Zmat{(7,5)}^{5}\in\field^{\weight{(5,1)}\times n_5}$ with $\weight{(5,1)}=\rank \UnitHankelBlock{(5,1)}$. The remaining terms of the TSS representation are obtained in the same way.

§.§ The general construction algorithm

The approach taken for the example of the previous section generalizes for a generic TSS representation. This procedure to convert a dense matrix into TSS form consists of two phases: an upsweep and a downsweep phase. In the upsweep phase, one starts at the leaves of the tree and works up towards the root. In this process, all the $\Bmat$'s, $\Cmat$'s, and $\Umat$'s are computed. In the downsweep phase that follows, one starts at the root of the tree and then works down towards the leaves. In this second leg,  the $\Pmat$'s, $\Qmat$'s, $\Wmat$'s, and $\Vmat$'s are computed.

[TSS construction algorithm]
Let $\Graph(r)$ be a tree with root node $r\in \NodeSet$ and let $\TSS\in \field^{M\times N}$ be the associated graph-partitioned matrix  with  $M=\sum_{i\in \NodeSet} m_i$ and $N=\sum_{i\in \NodeSet} n_i$. A set of generators for the TSS representation of $T$ is obtained by following the steps outlined below.

* Diagonal stage. Set $\Dmat^{i}=\TSS\nodeid{i,i}$ for $i\in \NodeSet$.

* Upsweep stage. For $l=L, L-1, \ldots, 1$ do the following:

* For every $i\in \NodeSet_l$ with parent node $j=\Parent(i) \in \NodeSet_{l-1}$ and children $\Children(i)=\lbrace w_1, w_2,\ldots, w_{\alpha}\rbrace
\subset \NodeSet$, write  $\UnitHankelBlock{(i,j)}=\Fmat{(i,j)}  \Gmat{(i,j)}$, where

\begin{eqnarray*}
\Fmat{(i,j)} & := &  \begin{blockarray}{ccccc} \begin{block}{c[cccc]}
\Descendantscompl(i) &  \Xmat{(w_1,i)}\nodeid{\Descendantscompl(i)} & \cdots & \Xmat{(w_{\alpha},i)}\nodeid{\Descendantscompl(i)} &    \TSS\nodeid{\Descendantscompl(i),i} \\
\end{block}  \end{blockarray},  \\
\Gmat{(i,j)} & := & \begin{blockarray}{cccc}
\Descendants(w_1) & \cdots & \Descendants(w_{\beta}) & i \\
\begin{block}{[cccc]}
\Ymat{(w_1,i)}    &   \\
& \ddots &  \\
&      &  \Ymat{(w_{\beta},i)}  \\
&    &        & \Id \\
\end{block}
\end{blockarray}.
\end{eqnarray*}

* Let $\weight{(i,j)} = \rank \Fmat{(i,j)} =  \rank \UnitHankelBlock{(i,j)} $ and compute the low-rank compression $\Fmat{(i,j)} = \Xmat{(i,j)} \Zmat{(i,j)}$.

* Set

^i_j :=  (i,j)^1,   ^j_i := (i,j)j,   ^i_j,w_t  := (i,j)^(w_t)

for $t=1,2,\ldots,\alpha$.

* Define $\Ymat{(i,j)} =  \Zmat{(i,j)} \Gmat{(i,j)}$ so that $\Xmat{(i,j)} \Ymat{(i,j)}$ is a low-rank factorization for $\UnitHankelBlock{(i,j)}$.

* Downsweep stage. For $l=1, 2, \ldots, L$ do the following:

* For every $i\in \NodeSet_l$ with parent node  $j=\Parent(i)\in \NodeSet_{l-1}$, grandparent node[For $l=1$ there will be no grandparent node, in which case the corresponding terms associated with it can be ignored.] $k= \Parent(i;2) \in \NodeSet_{l-2}$, and siblings $\Siblings(i)=\lbrace v_1, v_2,\ldots, v_{\beta}\rbrace \subset \NodeSet$, write $\UnitHankelBlock{(j,i)}=\Fmat{(j,i)}  \Gmat{(j,i)}$, where

\begin{eqnarray*}
\Fmat{(j,i)} & := &  \begin{blockarray}{cccccc} \begin{block}{c[ccccc]} \Descendants(i) & \Xmat{(k,j)} \nodeid{\Descendants(i)}  &  \Xmat{(v_1,i)} \nodeid{\Descendants(i)} & \cdots & \Xmat{(v_{\beta},i)} \nodeid{\Descendants(i)}   &   \TSS\nodeid{\Descendants(i),j} \\ \end{block}
\end{blockarray}  \\
\Gmat{(j,i)} & := & \begin{blockarray}{ccccc} \Descendantscompl(i) & \Descendants(v_1) & \cdots & \Descendants(v_{\beta}) & i \\
\begin{block}{[ccccc]}  \Ymat{(k,j)}  & & & \\
& \Ymat{(v_1,i)}  &  & \\
&  & \ddots & \\
&  &     & \Ymat{(v_{\beta},i)} \\
&  &     &            & \Id \\
\end{block}
\end{blockarray}
\end{eqnarray*}

* Let $\weight{(j,i)} = \rank \Fmat{(j,i)} =  \rank \UnitHankelBlock{(j,i)}$ and compute the low-rank compression $\Fmat{(j,i)} = \Xmat{(j,i)} \Zmat{(j,i)}$.

* Set

^j_i = (j,i)^i,  ^i_(j,k) = (j,i)^(i) ,  ^i_j = (j,i)i,   ^i_j,v_t = (j,i)^(v_t)

for $t=1,2,\ldots,\beta$.

* Set $\Ymat{(j,i)} =  \Zmat{(j,i)} \Gmat{(j,i)}$ so that $\Xmat{(j,i)} \Ymat{(j,i)}$ is a low-rank factorization for $\UnitHankelBlock{(j,i)}$.

§.§ Proof of the universality theorem

We are now ready to prove <Ref>.

<Ref> presents a constructive proof for the existence of a TSS representation with rank profile $\lbrace \weight{e} := \rank \UnitHankelBlock{e} \rbrace_{ e \in \EdgeSet}$.  The only thing left is to show that the TSS representation produced by <Ref> is minimal. This can be verified by setting up a contradiction.  Suppose there exists a TSS representation with rank-profile $\lbrace \rho'_{e} \rbrace_{e\in\EdgeSet}$  and $\rho'_{e} < \weight{e}$  for some edge $e\in\EdgeSet$, then the unit Hankel $\UnitHankelBlock{e}$  admits a low-rank factorization of rank $\rho'_{e} < \weight{e}$, which is not possible.

§ TSS LINEAR SYSTEMS

In this section, we examine linear systems $\TSS \vect{x} = \vect{b}$, where $\TSS \in \field^{M\times N}$is a TSS matrix on $\Graph=(\NodeSet,\EdgeSet)$  of dimensions  $M=\sum_{i\in \NodeSet} m_i$ by $N=\sum_{i\in \NodeSet} n_i$. By conformally partitioning $\vect{b}
\in \field^{M}$ and  $\vect{x}
\in \field^{N}$ into sub-vectors  $\vect{b}_i \in \field^{m_i}$ and $\vect{x}_i \in \field^{n_i}$, respectively, we first describe in <Ref>  how the matrix-vector product $\vect{b}= \TSS \vect{x}$ is evaluated efficiently. Then, in <Ref>, we proceed and use the relations derived for the matrix-vector product to formulate an efficient method to solve  $\TSS \vect{x} = \vect{b}$ is solved for $\vect{x}$ given $\vect{b}$.

§.§ Evaluation of matrix-vector product

The block entries of a TSS matrix originate from evolving a dynamical system over a graph. In the special case of an SSS matrix, the lower and upper triangular parts of the matrix are the result of running a causal and anti-causal linear time-variant dynamical system. This is exploited in the matrix-vector product. For the general case, the dynamics evolve over a tree, and it is harder to provide a simple characterization. Nonetheless, formulating the “state-space” equations shall yield a fast matrix-vector product algorithm for the general case as well. To do so, associate with each edge $(i,j)\in \EdgeSet$ of the acyclic connected graph $\Graph$ a state vector $\state{(i,j)}\in \field^{\weight{(i,j)}}$. We have the state equations

\begin{equation}
\state{(i,j)} = \sum_{w \in \kNeighbor(i) \setminus \{ j \}}   \Trans^{i}_{j,w} \state{(w,i)}       +     \Inp^{i}_j \vect{x}_i, \qquad  (i,j) \in \EdgeSet, \label{eq:staterel}
\end{equation}

along with the output equations

\begin{equation}
\vect{b}_j = \sum_{i \in \kNeighbor(j)}  \Out^j_i \state{(i,j)}   + \Dmat^j \vect{x}_i,   \qquad   j \in \NodeSet. \label{eq:outputrel}
\end{equation}

By picking a root node $r\in \NodeSet$, the state and output equations for the corresponding tree $\Graph(r)$ may be further refined to

\begin{equation}
\state{(i,j)} = \begin{cases} \displaystyle \sum_{w \in \Children(i)}   \Umat^{i}_{j,w} \state{(w,i)}       +     \Bmat^{i}_j \vect{x}_i, \qquad  & j = \Parent(i) \\
\Wmat^{i}_{j,\Parent(i)} \state{(\Parent(i),i)}  +  \displaystyle   \sum_{w \in \Siblings(j)}   \Vmat^{i}_{j,w} \state{(w,i)}       +     \Pmat^{i}_j \vect{x}_i, \qquad           &  i = \Parent(j)
\end{cases} \label{eq:statefortree}
\end{equation}

\begin{equation}
\vect{b}_j =   \Qmat^j_{\Parent(j)} \state{(\Parent(j),j)}  + \sum_{i \in \Children(j)}  \Bmat^j_i \state{(i,j)}   + \Dmat^j \vect{x}_i.
\end{equation}

A careful examination of (<ref>) reveals a natural causal ordering on the state variables. Specifically, for a leaf $i\in\Leaves(\Graph)$, the state equations are simply $\state{(i,j)} = \Bmat^i_{j} \vect{x}_i$. One may thus start with computing the state vectors at the leaves and then work up towards the interiors of the graph. Once the root node is reached, the reverse process can be initiated using the second  and then flow outwards again down again towards

[TSS matrix-vector product]
Given a TSS matrix $\TSS \in \field^{M\times N}$ on $\Graph(r)$  of dimensions  $M=\sum_{i\in \NodeSet} m_i$ by $N=\sum_{i\in \NodeSet} n_i$, the matrix-vector product $\vect{b}_{i} = \sum_{j\in \NodeSet} \TSS\nodeid{i,j} \vect{x}_j$ for $i\in\NodeSet$ is obtained by following the steps outlined below.

* Diagonal stage. Initialize $\vect{b}_{i} =\Dmat^i \vect{x}_i$ for $i\in \NodeSet$.

* Upsweep stage. For $l=L, L-1, \ldots, 1$ do the following:

* For every $i\in \NodeSet_l$ with parent node $j=\Parent(i) \in \NodeSet_{l-1}$ and children $\Children(i)=\lbrace w_1, w_2,\ldots, w_{\alpha}\rbrace
\subset \NodeSet$, evaluate

(i,j) =  ∑^α_p=1   ^i_j,w_p (w_p,i)       +     ^i_j x_i.

* Update

b_j ←b_j +  ^j_i (i,j).

* Downsweep stage. For $l=1, 2, \ldots, L$ do the following:

* For every $i\in \NodeSet_l$ with parent node  $j=\Parent(i)\in \NodeSet_{l-1}$, grandparent node $k= \Parent(i;2) \in \NodeSet_{l-2}$, and siblings $\Siblings(i)=\lbrace v_1, v_2,\ldots, v_{\beta}\rbrace \subset \NodeSet$, evaluate

(i,j) =  ^i_j,k (k,i)  +  ∑^β_p=1   ^i_j,w_p (w_p,i)       +     ^i_j x_i.

* Update

b_j ←b_j +  ^j_i (i,j).

§.§ Solving linear systems

The linear system $\TSS \vect{x} = \vect{b}$is efficiently solved for $\vect{x}$ given $\vect{b}$ by using the same reasoning introduced in [5]. By treating  $\{\state{e} \}_{e\in\EdgeSet}$ and $\{ \vect{x}_i\}_{i\in\NodeSet}$ as unknowns, and $\{ \vect{b}_i\}_{i\in\NodeSet}$ as knowns, (<ref>) and (<ref>) collectively yield the sparse linear system

\begin{eqnarray}
\state{(i,j)}   - \displaystyle \sum_{w \in \kNeighbor(i) \setminus \{ j \}}   \Trans^{i}_{j,w} \state{(w,i)}       -     \Inp^{i}_j \vect{x}_i &  = & 0,  \qquad  (i,j) \in \EdgeSet \\
\displaystyle \sum_{i \in \kNeighbor(j)}  \Out^j_i \state{(i,j)}   + \Dmat^j \vect{x}_i &  =&   \vect{b}_j, \qquad j \in \NodeSet.
\end{eqnarray}

Particularly, if we let $\kNeighbor(j) = \{ i_1,i_2,\ldots, i_p \}$ and define

_j :=
,     _j =

the adjecency graph of the matrix expression $\Xi \thetavar = \betavar$ that describes (<ref>)  coincides with $\Graph$. That is, $\Xi\nodeid{i,j} \ne 0$ if and only if $(i,j)\in \EdgeSet$. Acyclic graphs are chordal graphs and have a perfect elimination order without any fill-in. Thus, (<ref>) may be efficiently solved with any standard (block-)sparse solver.

§ CONCLUSIONS AND FUTURE WORK

We introduced a new class of representation for rank-structured matrices called tree semi-separable (TSS) matrices. It is shown that TSS matrices unify and generalize SSS and HSS matrices. Furthermore, through deriving a construction algorithm, we showed that these representations are universal. Subsequently, it was shown that TSS inherits many of the well-known characteristics of SSS and HSS matrices concerning matrix-vector multiply, matrix-matrix multiply, matrix-matrix addition, inversion, and solvers.

Future work will be geared towards the efficient implementation and generalization of many of the algorithms that are associated with SSS and HSS matrices. The potential applications of these algorithms and the greater flexibility that they offer will also be explored. Finally, the results associated with TSS form an essential building block for constructing representations associated with more general
non-acyclic graphs [9]. Given that these representations are essentially multi-linear descriptions of linear operators, it is conjectured that descent-based algorithms (such as those used for tensor decompositions) together with the construction procedure of TSS matrices may prove to be a successful strategy in recovering these more complicated representations.

[1]
S. Ambikasaran and E. Darve, An $\mathcal{O} (n \log n)$ fast direct solver for partial hierarchically semi-separable matrices, Journal of Scientific Computing, 57 (2013), pp. 477–501.

[2]
A. Aminfar, S. Ambikasaran, and E. Darve, A fast block low-rank dense solver with applications to finite-element matrices, Journal of Computational Physics, 304 (2016), pp. 170–188.

[3]
T. Bella, Y. Eidelman, I. Gohberg, and V. Olshevsky, Computations with quasiseparable polynomials and matrices, Theoretical Computer Science, 409 (2008), pp. 158–179.

[4]
S. Börm, L. Grasedyck, and W. Hackbusch, Introduction to hierarchical matrices with applications, Engineering Analysis with Boundary Elements, 27 (2003), pp. 405–422.

[5]
S. Chandrasekaran, P. Dewilde, M. Gu, W. Lyons, and T. Pals, A fast solver for hss representations via sparse matrices, SIAM Journal on Matrix Analysis and Applications, 29 (2007), pp. 67–81.

[6]
S. Chandrasekaran, P. Dewilde, M. Gu, T. Pals, X. Sun, A.-J. van der Veen, and D. White, Some fast algorithms for sequentially semiseparable representations, SIAM Journal on Matrix Analysis and Applications, 27 (2005), pp. 341–364.

[7]
S. Chandrasekaran, P. Dewilde, M. Gu, T. Pals, and A.-J. van der Veen, Fast stable solver for sequentially semi-separable linear systems of equations, in International Conference on High-Performance Computing, Springer, 2002, pp. 545–554.

[8]
S. Chandrasekaran, E. N. Epperly, and N. Govindarajan, Graph-induced rank structures and their representations, arXiv preprint arXiv:1911.05858,  (2019).

[9]
S. Chandrasekaran and N. Govindarajan, Graph induced rank structured matrices and their representations.

[10]
S. Chandrasekaran, N. Govindarajan, and A. Rajagopal, Fast algorithms for displacement and low-rank structured matrices, in Proc. of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC '18, New York, NY, USA, 2018, Association for Computing Machinery, p. 17–22.

[11]
S. Chandrasekaran, M. Gu, and T. Pals, A fast ulv decomposition solver for hierarchically semiseparable representations, SIAM Journal on Matrix Analysis and Applications, 28 (2006), pp. 603–622.

[12]
P. Dewilde and A.-J. Van der Veen, Time-Varying Systems and Computations, Springer Science & Business Media, Dordrecht, The Netherlands, 1998.

[13]
Y. Eidelman and I. Gohberg, On a new class of structured matrices, Integral Equations and Operator Theory, 34 (1999), pp. 293–324.

[14]
L. Greengard and V. Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics, 73 (1987), pp. 325–348.

[15]
W. Hackbusch, Hierarchical matrices: algorithms and analysis, vol. 49, Springer, 2015.

[16]
W. Hackbusch and S. Börm, Data-sparse approximation by adaptive $\mathcal{H}^2$-matrices, Computing, 69 (2002), pp. 1–35.

[17]
R. Vandebril, M. Van Barel, and N. Mastronardi, Matrix computations and semiseparable matrices: linear systems, vol. 1, JHU Press, 2008.

[18]
S. Wang, X. S. Li, J. Xia, Y. Situ, and M. V. De Hoop, Efficient scalable algorithms for solving dense linear systems with hierarchically semiseparable structures, SIAM J. Sci. Comput., 35 (2013), pp. C519–C544.

[19]
J. Xia, On the complexity of some hierarchical structured matrix algorithms, SIAM J. Matrix Anal. Appl., 33 (2012), pp. 388–410.

[20]
J. Xia, S. Chandrasekaran, M. Gu, and X. S. Li, Fast algorithms for hierarchically semiseparable matrices, Numerical Linear Algebra with Applications, 17 (2010), pp. 953–976.