# Clarification on DMRG computational complexity

I was reading a paper on the density matrix renormalization group (https://arxiv.org/abs/1008.3477). In DMRG, we gradually grow a chain by inserting a unit cell at the center of the chain (for simplicity, assume the unit cell is two sites) and absorbing the sites into larger “blocks.” In this paper’s notation, each step involves moving from a structure A * * B (block A, two sites, block B) to A’ * * B’ (block A’, two sites, block B’), where A’ and B’ each have one more site than A and B respectively. Looking at Equations 6 and 7, which are

$$\newcommand{\Ket}[1]{\left|#1\right>}$$ Equation 7 is a restatement of Equation 6, which is meant to describe how to represent operators in a block basis. In other words, if we have a representation of an operator $$O$$ that acts on site $$\ell + 1$$, and assume that site $$\ell + 1$$ will be absorbed on the left into block A, then the matrix elements of $$O$$ in the block basis in terms of the matrix elements in the previous, smaller block basis are given by Equation 6 ($$\Ket{a_{\ell}}$$ describes a basis vector of the block of size $$\ell$$).

The author argues that factoring a term, as in Equation 7, can reduce the computational complexity of Equation 6 from $$O(D^4d)$$ to $$O(D^3d)$$. In these expressions, D is the cutoff dimension of the Hilbert space of the left and right blocks in the DMRG algorithm (usually referred to as $$\chi$$ in the literature), and $$d$$ is the dimension of the local Hilbert space of a site (so the dimensions of the basis sets $$\Ket{a}$$ and $$\Ket{\sigma}$$ are $$D$$ and $$d$$ respectively).

I understand how we arrive at $$O(D^4d)$$ for Equation 6 -- we sum over $$D^2 d$$ terms, and the complexity of the term is $$O(D^2)$$. I don't see how we reduce the computational complexity of evaluating the expression in Equation (7), though. It seems that you still sum over $$Dd$$ terms, and the complexity of the term in large brackets is $$O(D^3)$$, since we sum over $$D$$ terms of complexity $$O(D^2)$$.

Later in the same paper, at Equation 11

The author claims that the complexity of this expression is $$O(D^2d^3)$$. There seem to be $$O(D^2d^3)$$ terms, but the complexity of each term is $$O(D^2)$$ due to the expectation value, so I'm confused at why we don't arrive at $$O(D^4 d^3)$$.

There are a few other similar instances throughout this paper, but I feel like I'm completely misinterpreting how the complexity of these expressions should be calculated. Could someone explain where I've gone wrong?

• Do you mind providing some details as to what D and d are in the formulas in your screenshots? – Norbert Schuch Sep 5 '19 at 14:15
• D is the cutoff dimension of the left and right Hilbert spaces as they expand throughout the DMRG process (so after we absorb the site into the left environment since the bond dimension grows, we take the D largest singular values), and d is the dimension of the local Hilbert space at a site. For that reason (and I might be wrong on this), I interpreted $\{|a_l>\}$ to have size D, and $\{|\sigma>\}$ to have size d. – user147177 Sep 5 '19 at 16:12
• I think it would be important if you both understand and explain the formulas you ask about. Right now, your comment sounds that you are just guessing something about those formulas, yet your questions does say anything like that. And you don't explain the things you ask about in your formula. I think it would be good if you try to improve the question. – Norbert Schuch Sep 5 '19 at 16:56
• I believe that I understand the formulas; my uncertainty in my previous comment referred to the fact that the issue I raised in my question (that of understanding where the computational complexity came from) seemed inconsistent with my understanding of what the expressions referred to. I’ve updated the question with more exposition on what the formulas refer to, I think you’re right that they weren’t well explained). – user147177 Sep 5 '19 at 21:29
• My point wasn't so much that you don't explain these things, but that a to-the-point answer would likely not be valuable to future visitors of this site without these details. – Norbert Schuch Sep 6 '19 at 6:05