Savostyanov D.V., Tyrtyshnikov E.E., Zamarashkin N.L. Fast truncation of mode ranks for bilinear tensor operations, Numerical Linear Algebra with Applications, 18 (6), p. 103-111, 2011.

We propose a fast algorithm for mode rank truncation of the result of a bilinear operation on 3-tensors given in the Tucker or canonical form. If the arguments and the result have mode sizesnand mode ranksr, the computation costsO(nr3+r4). The algorithm is based on the cross approximation of Gram matrices, and the accuracy of the resulted Tucker approximation is limited by square root of the machine precision. We apply the proposed algorithms for the evaluation of the Hadamard square of the electron density and demonstrate that it outperforms previously used methods for this purpose. We also check the accuracy of the resulted Tucker approximation and show that one iteration of the Tucker-ALS method improves it almost up to the machine precision.

: multidimensional arrays; structured tensors; Tucker approximation; fast compression; cross approximation