How Competitive is the ADI for Tensor Structured Equations?

In [1] we presented an extension of the alternating direction implicit (ADI) method for the solution of Lyapunov equations 1$$FX + XF^{T} = -GG^{T}$$ to higher dimensional problems. The vectorized form of the Lyapunov equation is$$\left( I \otimes F + F \otimes I \right) {\rm vec}\left(X\right) = {\rm vec}\left(B\right).$$ We considered the generalization of this equation of the form 2$$A{\rm vec}(X) = \left( I \otimes \cdots \otimes I \otimes A_{1} + \dots + A_{d} \otimes I \otimes \cdots \otimes I \right) = {\rm vec}(B).$$ The tensor train structure is one possible generalization of the low rank factorization we find in the right hand side of (1). Therefor we assume B to be of tensor train structure. We showed that in analogy to the low rank ADI case the solution X can be generated in tensor train structure, too. Further we provided an algorithm that computes X using a generalization of the ADI method. Here we compare our new tensor ADI method with an density matrix renormalization group (DMRG) solver for tensor train matrix equations and with matrix equation solvers to investigate the competitiveness of our new solver. (© 2012 Wiley‐VCH Verlag GmbH & Co. KGaA, Weinheim)