<ol>
<li><p>It's safe to assume the input was given to you, so whatever input you started with, you automatically needed that much memory anyway. Note that, if each wire in the ladder is <span class="math-container">$d$</span>-dimensional, then each 3-tensor (node that isn't an endpoint of the ladder) only needs <span class="math-container">$d^3$</span> numbers to describe it, so the total input size for a <span class="math-container">$2 \times w$</span> grid (aka ladder of width <span class="math-container">$w$</span>) would only be <span class="math-container">$2(w-2)d^3 + 4d^2 \leq 2wd^3$</span>, which grows linearly with <span class="math-container">$w$</span>, compared to the <span class="math-container">$d^w$</span> memory needed in the computation with the first strategy.</p>
</li>
<li><p>Each individual contraction you do is essentially a matrix multiplication (where the tensors themselves are suitably flattened). If you are contracting over <span class="math-container">$k$</span> indices simultaneously (and, again, assuming each wire correspond to a <span class="math-container">$d$</span>-dimensional space), then you are multiplying matrices whose size is ~<span class="math-container">$d^k$</span>. In practice, memory and communication requirements are the bottleneck for multiplying matrices. In theory, one can count arithmetic operations. Your matrices will likely be rectangular, e.g. here are the sizes for the matrices that would appear in the steps of method 2:</p>
</li>
</ol>
<p>Step 0 <span class="math-container">$d \times d$</span> (for A) times <span class="math-container">$d \times d$</span> (for F)</p>
<p>Step 1 <span class="math-container">$d \times d$</span> (for <span class="math-container">$Y^0$</span>) times <span class="math-container">$d \times d^2$</span> (for B, where the <span class="math-container">$d^2$</span> arises b/c the two indices of <span class="math-container">$B$</span> not being contracted over are flattened in this view)</p>
<p>Step 2 <span class="math-container">$d \times d^2$</span> by <span class="math-container">$d^2 \times d$</span> etc.</p>
<p>For multiplying square <span class="math-container">$d \times d$</span> matrices, the naive algorithm uses <span class="math-container">$O(d^3)$</span> arithmetic operations, but the exponent of matrix multiplication is known to be quite a bit smaller (albeit by theoretical algorithms that, at the moment, are not practical at exponents below ~2.7). For multiplying non-square matrices, sometimes better can be done, e.g. <a href="https://people.csail.mit.edu/virgi/6.890/papers/legallurrutia.pdf" rel="nofollow noreferrer">https://people.csail.mit.edu/virgi/6.890/papers/legallurrutia.pdf</a> implies you can multiply a <span class="math-container">$d^2 \times d$</span> by a <span class="math-container">$d \times d^2$</span> matrix in times <span class="math-container">$O(d^{2.04...})$</span>.</p>
<ol start="3">
<li>I think they are using the phrase &quot;ladder-shaped&quot; informally to mean, in your terminology, a ladder of height 2.</li>
</ol>

CC BY-SA 4.0
2022-05-11T13:32:58.733Z
Thank you very much for your answer. I feedback on it this week.
Marco Fellous-Asiani
CC BY-SA 4.0
2022-05-13T13:43:26.513Z
Great answer, you clarified my main issue. For the memory issue, in summary, we need a memory that grows linearly with $w$ to described all the tensors. When we are doing contraction however, depending on how we do it, we might have to store in memory something that grows exponentially with $w$ (with method 1). The "intuition" behind it is that "conceptually" the problem can be described with a linear number of parameters, but depending on how we proceed at intermediate steps we might have to store in memory un-necessary large tensors. Thanks a lot.
Marco Fellous-Asiani
CC BY-SA 4.0
2022-05-09T18:11:12.133Z
2022-05-09T18:11:12.133Z
Joshua Grochow
<p>I am learning the very basics of tensor network theory and I am trying to understand why some ways to contract tensors are better than others in terms of computational complexity. Knowing in which order we should contract the tensor is known as &quot;bubbling&quot;.</p>
<p>As a reference, I am following <a href="https://arxiv.org/pdf/1603.03039.pdf" rel="nofollow noreferrer">this paper</a>, bubbling is described on page 7 (my background is quantum information, I need to understand how tensor networks are used to represent entangled quantum states).</p>
<p>I am following the examples on page 7 of this paper and for that I consider a ladder-shaped network. I put some notations first (don't pay attention to the dotted circle on this first image).</p>
<p><a href="https://i.sstatic.net/5prAN.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5prAN.png" alt="enter image description here" /></a></p>
<p>As a reminder, what this graph means is basically the number:</p>
<p><span class="math-container">$$N=\sum_{ijklmno} A_{ni} B_{ijo} C_{jk} D_{kl} E_{lmo} F_{mn}$$</span></p>
<p>Where, <span class="math-container">$A$</span>, <span class="math-container">$B$</span>,... are tensors of rank given by the number of indices they have. The principle of &quot;bubbling&quot; is to try a way to compute it in the most &quot;efficient&quot; manner from a computational perspective. To do it, we can either contract the tensor network through the first manner (below):</p>
<p><a href="https://i.sstatic.net/Fym6C.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Fym6C.png" alt="enter image description here" /></a></p>
<p>Or the second one:</p>
<p><a href="https://i.sstatic.net/9VXsR.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/9VXsR.png" alt="enter image description here" /></a></p>
<p>For the first approach, what we will have are the following steps in the computation:</p>
<p><span class="math-container">$$\text{Step 0: }X^0_{njo}=\sum_{i} A_{ni} B_{ijo} $$</span>
<span class="math-container">$$\text{Step 1: }X^1_{nok}=\sum_j X^0_{njo} C_{jk} $$</span>
<span class="math-container">$$\text{Step 2: }X^2_{nol}=\sum_k X^1_{nok} D_{kl} $$</span>
<span class="math-container">$$\text{Step 3: }X^3_{nm}=\sum_{lo} X^2_{nol} E_{lmo} $$</span>
<span class="math-container">$$\text{Step 4: }X^4=N=\sum_{nm} X^3_{nm} F_{nm}$$</span></p>
<p>For the second approach, we will have the following:</p>
<p><span class="math-container">$$\text{Step 0: }Y^0_{im}=\sum_{n} A_{ni} F_{mn} $$</span>
<span class="math-container">$$\text{Step 1: }Y^1_{mjo}=\sum_{i} Y^0_{im} B_{ijo} $$</span>
<span class="math-container">$$\text{Step 2: }Y^2_{jl}=\sum_{mo} Y^1_{mjo} E_{lmo} $$</span>
<span class="math-container">$$\text{Step 3: }Y^3_{lk}=\sum_{j} Y^2_{jl} C_{jk} $$</span>
<span class="math-container">$$\text{Step 4: }Y^4=N=\sum_{lk} Y^3_{lk} D_{lk}$$</span></p>
<h2>My current understanding</h2>
<p>Those explanations are what I understood from the paper linked.</p>
<p>It is not completely apparent because we fixed <span class="math-container">$w=3$</span> in this example, but in the first approach, for a ladder of width <span class="math-container">$w$</span> (and height <span class="math-container">$2$</span>), during the computation, we will have <span class="math-container">$w$</span> links in memory. This is apparent for instance at step <span class="math-container">$2$</span> of the first approach, we see that <span class="math-container">$X^2_{nol}$</span> (it depends on three indices here and for the general case it will depend on <span class="math-container">$w$</span> indices). Because of that, if each link has a dimension <span class="math-container">$d$</span>, we will have <span class="math-container">$d^w$</span> elements to keep in memory.</p>
<p>In the second approach, we will never have more than <span class="math-container">$3$</span> links in memory. Hence, we say that it is less memory expensive. This is because of the way we contract the tensor network, we always make sure to never have more than <span class="math-container">$3$</span> links that are not summed.</p>
<p>As here <span class="math-container">$w=3$</span> the difference is probably not so clear with this specific value of <span class="math-container">$w$</span> (but this is the example taken in the paper, I hope it will be clear enough for the readers)</p>
<h2>What disturbs me - my questions.</h2>
<p><strong>First question:</strong></p>
<p>I am not sure to fully understand the logic. Even though the &quot;actual&quot; computation we are doing requires <span class="math-container">$d^w$</span> terms in memory for the first approach but a number that doesn't grow with <span class="math-container">$w$</span> in the second one, we need &quot;anyway&quot; to keep in memory the tensors that we are not summing. For instance at a given step <span class="math-container">$n_0$</span> of the calculation, maybe some tensors haven't played any role yet (they will be summed in the future), but I have to have them in memory somewhere. If we take this into account, wouldn't it imply that both approach are actually similar in terms of memory consumption?</p>
<p><strong>Second question:</strong></p>
<p>Here, I mainly talked about the memory consumption of the two approaches. What about the number of calculations to be done? Could I have an explanation telling me why the second approach is &quot;better&quot;?</p>
<p><strong>Third question:</strong></p>
<p>This question is simply to check that a &quot;ladder-shaped&quot; network is a network in which the width grows with some parameter <span class="math-container">$w$</span> while the height is constant. In the paper they actually don't give a precise definition of what it is.</p>

<graph-theory><optimization>
Tensor network contraction "bubbling": why are some approaches more computationally efficient than others (question from a beginner)
Marco Fellous-Asiani
# Tensor network contraction "bubbling": why are some approaches more computationally efficient than others (question from a beginner)

(Asked by: username_0 on 2022-05-01)

I am learning the very basics of tensor network theory and I am trying to understand why some ways to contract tensors are better than others in terms of computational complexity. Knowing in which order we should contract the tensor is known as "bubbling".

As a reference, I am following [this paper](https://arxiv.org/pdf/1603.03039.pdf), bubbling is described on page 7 (my background is quantum information, I need to understand how tensor networks are used to represent entangled quantum states).

I am following the examples on page 7 of this paper and for that I consider a ladder-shaped network. I put some notations first (don't pay attention to the dotted circle on this first image).

[![enter image description here](https://i.sstatic.net/5prAN.png)](https://i.sstatic.net/5prAN.png)

As a reminder, what this graph means is basically the number:

$$N=\sum\_{ijklmno} A\_{ni} B\_{ijo} C\_{jk} D\_{kl} E\_{lmo} F\_{mn}$$

Where, $A$, $B$,... are tensors of rank given by the number of indices they have. The principle of "bubbling" is to try a way to compute it in the most "efficient" manner from a computational perspective. To do it, we can either contract the tensor network through the first manner (below):

[![enter image description here](https://i.sstatic.net/Fym6C.png)](https://i.sstatic.net/Fym6C.png)

Or the second one:

[![enter image description here](https://i.sstatic.net/9VXsR.png)](https://i.sstatic.net/9VXsR.png)

For the first approach, what we will have are the following steps in the computation:

$$\text{Step 0: }X^0\_{njo}=\sum\_{i} A\_{ni} B\_{ijo} $$
$$\text{Step 1: }X^1\_{nok}=\sum\_j X^0\_{njo} C\_{jk} $$
$$\text{Step 2: }X^2\_{nol}=\sum\_k X^1\_{nok} D\_{kl} $$
$$\text{Step 3: }X^3\_{nm}=\sum\_{lo} X^2\_{nol} E\_{lmo} $$
$$\text{Step 4: }X^4=N=\sum\_{nm} X^3\_{nm} F\_{nm}$$

For the second approach, we will have the following:

$$\text{Step 0: }Y^0\_{im}=\sum\_{n} A\_{ni} F\_{mn} $$
$$\text{Step 1: }Y^1\_{mjo}=\sum\_{i} Y^0\_{im} B\_{ijo} $$
$$\text{Step 2: }Y^2\_{jl}=\sum\_{mo} Y^1\_{mjo} E\_{lmo} $$
$$\text{Step 3: }Y^3\_{lk}=\sum\_{j} Y^2\_{jl} C\_{jk} $$
$$\text{Step 4: }Y^4=N=\sum\_{lk} Y^3\_{lk} D\_{lk}$$

## My current understanding

Those explanations are what I understood from the paper linked.

It is not completely apparent because we fixed $w=3$ in this example, but in the first approach, for a ladder of width $w$ (and height $2$), during the computation, we will have $w$ links in memory. This is apparent for instance at step $2$ of the first approach, we see that $X^2\_{nol}$ (it depends on three indices here and for the general case it will depend on $w$ indices). Because of that, if each link has a dimension $d$, we will have $d^w$ elements to keep in memory.

In the second approach, we will never have more than $3$ links in memory. Hence, we say that it is less memory expensive. This is because of the way we contract the tensor network, we always make sure to never have more than $3$ links that are not summed.

As here $w=3$ the difference is probably not so clear with this specific value of $w$ (but this is the example taken in the paper, I hope it will be clear enough for the readers)

## What disturbs me - my questions.

**First question:**

I am not sure to fully understand the logic. Even though the "actual" computation we are doing requires $d^w$ terms in memory for the first approach but a number that doesn't grow with $w$ in the second one, we need "anyway" to keep in memory the tensors that we are not summing. For instance at a given step $n\_0$ of the calculation, maybe some tensors haven't played any role yet (they will be summed in the future), but I have to have them in memory somewhere. If we take this into account, wouldn't it imply that both approach are actually similar in terms of memory consumption?

**Second question:**

Here, I mainly talked about the memory consumption of the two approaches. What about the number of calculations to be done? Could I have an explanation telling me why the second approach is "better"?

**Third question:**

This question is simply to check that a "ladder-shaped" network is a network in which the width grows with some parameter $w$ while the height is constant. In the paper they actually don't give a precise definition of what it is.

**Tags:** graph-theory, optimization


---

## 1 answers

### Answer by username_1 on 2022-05-09. Score: 1 | Accepted answer

1. It's safe to assume the input was given to you, so whatever input you started with, you automatically needed that much memory anyway. Note that, if each wire in the ladder is $d$-dimensional, then each 3-tensor (node that isn't an endpoint of the ladder) only needs $d^3$ numbers to describe it, so the total input size for a $2 \times w$ grid (aka ladder of width $w$) would only be $2(w-2)d^3 + 4d^2 \leq 2wd^3$, which grows linearly with $w$, compared to the $d^w$ memory needed in the computation with the first strategy.
2. Each individual contraction you do is essentially a matrix multiplication (where the tensors themselves are suitably flattened). If you are contracting over $k$ indices simultaneously (and, again, assuming each wire correspond to a $d$-dimensional space), then you are multiplying matrices whose size is ~$d^k$. In practice, memory and communication requirements are the bottleneck for multiplying matrices. In theory, one can count arithmetic operations. Your matrices will likely be rectangular, e.g. here are the sizes for the matrices that would appear in the steps of method 2:

Step 0 $d \times d$ (for A) times $d \times d$ (for F)

Step 1 $d \times d$ (for $Y^0$) times $d \times d^2$ (for B, where the $d^2$ arises b/c the two indices of $B$ not being contracted over are flattened in this view)

Step 2 $d \times d^2$ by $d^2 \times d$ etc.

For multiplying square $d \times d$ matrices, the naive algorithm uses $O(d^3)$ arithmetic operations, but the exponent of matrix multiplication is known to be quite a bit smaller (albeit by theoretical algorithms that, at the moment, are not practical at exponents below ~2.7). For multiplying non-square matrices, sometimes better can be done, e.g. <https://people.csail.mit.edu/virgi/6.890/papers/legallurrutia.pdf> implies you can multiply a $d^2 \times d$ by a $d \times d^2$ matrix in times $O(d^{2.04...})$.

3. I think they are using the phrase "ladder-shaped" informally to mean, in your terminology, a ladder of height 2.

> **Comments:**
> **username_0**: Thank you very much for your answer. I feedback on it this week.  
> **username_0**: Great answer, you clarified my main issue. For the memory issue, in summary, we need a memory that grows linearly with $w$ to described all the tensors. When we are doing contraction however, depending on how we do it, we might have to store in memory something that grows exponentially with $w$ (with method 1). The "intuition" behind it is that "conceptually" the problem can be described with a linear number of parameters, but depending on how we proceed at intermediate steps we might have to store in memory un-necessary large tensors. Thanks a lot.  

---

