QTT-isogeometric solver in two dimensions

L. Markeeva, I. Tsybulin, I. Oseledets

Research output: Contribution to journalArticlepeer-review


Elliptical PDEs are at the core of many computational problems. Sometimes it is necessary to solve them on fine meshes, which entail huge memory footprints and low computational speeds. We provide a method to solve elliptical PDEs on fine grids with lowered memory consumption and improved convergence. This paper considers one typical elliptical PDE – the Poisson equation on various polygonal domains with Dirichlet boundary conditions. The Finite Element Method (FEM) is used for numerical solution. FEM approximates a two-dimensional PDE as a system of linear equations Au=f. For an n-by-n mesh grid the sparse representation of A has the size of O(n2). We replace the sparse matrix representation with a Quantized Tensor Train (QTT) representation to obtain O((log⁡n)α) time and memory complexity to construct both A and f. This is ensured by constant-bounded QTT approximation ranks. AMEn solver is used on the final linear system, and its iterations are faster for low rank QTT approximation. To avoid rank growth caused by the intrinsic structure of A we introduce a new operation z-kron which constructs a matrix with rows and columns permuted into so called z-order. An algorithm to construct A in z-order directly in QTT with O(1) ranks w.r.t. n is provided. The proposed method is used to solve the Poisson equation on two different polygonal domains. Experiments show that our approach significantly improves memory consumption and speed over classical sparse-matrix based partial differential equation solvers like FEniCS.

Original languageEnglish
Article number109835
JournalJournal of Computational Physics
Publication statusPublished - 1 Jan 2021


  • Elliptic partial differential equation
  • Finite element method
  • Quantized tensor train
  • Tensor train
  • z-curve
  • z-kron


Dive into the research topics of 'QTT-isogeometric solver in two dimensions'. Together they form a unique fingerprint.

Cite this