Full-memory and limited-memory storage costs

Each dense matrix contains $n^2={1000}^2=\mathrm{1,000,000}$ real entries. The paired state in [F3] therefore stores $2n^2=\mathrm{2,000,000}$ matrix entries; a one-matrix implementation stores $n^2=\mathrm{1,000,000}$.

The L-BFGS pair list contains at most $2mn=2\cdot 10\cdot 1000=\mathrm{20,000}$ real coordinates, plus $O(n+m)$ temporary vectors and scalars.

In exact inverse-matrix mode, computing $p=-Hg$ uses one dense matrix-vector product and costs $O(n^2)$ scalar operations. For the direct update, first compute $u:=Bs$ with one dense matrix-vector product; since $B$ is symmetric, $Bs{s}^{T}B=u{u}^T$. Then form $B^{+}=B-u{u}^T\mathrm{/}(s^{T}u)+y{y}^T\mathrm{/}(s^{T}y)$ using two outer products and an entrywise matrix update, which costs $O(n^2)$. For the inverse update, first compute $v:=Hy$ with one dense matrix-vector product and expand [F4] using symmetry of $H$ to obtain $H^{+}=H-\rho (s{v}^T+v{s}^T)+(\rho +{\rho }^2{y}^{T}v)s{s}^T\mathrm{.}$ This uses a constant number of outer-product updates and also costs $O(n^2)$. Thus the dense direction and the paired BFGS updates use $O(n^2)$ work per iteration. By [F1], the two-loop recursion uses $O(mn)$ scalar work. Here $mn=\mathrm{10,000}$ while $n^2=\mathrm{1,000,000}$; the paired representation uses 100 times as many matrix entries as correction-pair coordinates, and a one-matrix representation uses 50 times as many. These are storage comparisons, not exact operation totals.