Efficient algorithm for finding the numerical solution of elliptic differential equations using QTT format and z-kron

This paper presents the approach of finding a numerical solution of the elliptical differential equation that uses quantised tensor train decomposition (QTT) as the main data structure. The QTT-format allows storing multidimensional arrays in a low amount of memory. This format has efficient implementations of basic math operations like summation, multiplication by a scalar and a vector, etc., which is a big advantage. Additionally, iterative solvers that store the coefficients matrix and the solution in the QTT format are implemented. For example AMEN solver and TT-GMRES solver. Both of them are used in the present work. To avoid exponential rank growth in QTT-representation, the z-permutation of rows and columns is used. The iterative Dirichlet method is used for finding a solution. This method iteratively searches for the solution on each subdomain separately, then it refines a solution on borders between subdomains. This approach allows calculating the solution on each subdomain in parallel on many computation units. As a result the iterative algorithm for finding the solution of the elliptical differential equation is given. This algorithm results in the implementation of the necessary approach. The number of iterations of the algorithm for searching the solution is restricted by constant.The algorithmic complexity of the presented approach is O (︀nr2)︀, where r is a rank of QTT-representation n - the number of nodes in a discretization grid.