QTT-isogeometric solver in two dimensions

Larisa Markeeva, I. V. Tsybulin, Ivan OseledetsJournal of Computational Physics 2018

TL;DR

This paper introduces a novel numerical algorithm for solving 2D elliptic partial differential equations using Quantized Tensor Train (QTT) decomposition and isogeometric analysis. The method efficiently constructs the global stiffness matrix in QTT format, leading to significantly reduced memory consumption and improved computational performance compared to traditional finite element methods.

What Problem Does This Paper Address?

Solving partial differential equations (PDEs) on complex geometries often requires computationally intensive methods. Traditional Finite Element Methods (FEM) can lead to large, dense matrices that are memory-hungry and slow to solve. While tensor methods, specifically Tensor Train (TT) and its quantized variant (QTT), offer a way to represent large matrices with low-rank approximations, efficiently constructing these QTT representations for the global stiffness matrix of a PDE solver has been a challenge. Existing approaches either require transforming a pre-computed dense matrix into QTT format (which defeats the purpose of low-rank representation) or struggle with maintaining low ranks for complex geometries. This paper addresses the need for an "on-the-fly" construction of QTT-formatted stiffness matrices for 2D elliptic PDEs on polygonal domains, aiming for both memory efficiency and computational speed.

Methods

The core of this work lies in a novel discretization scheme that leverages isogeometric analysis and QTT decomposition. The domain is first decomposed into adjacent quadrangles. Each quadrangle is then meshed, and a local stiffness matrix is constructed. The key innovation is how these local matrices are assembled into a global QTT-formatted stiffness matrix. This is achieved through:

  • Isogeometric Analysis: Using basis functions derived from the geometry itself, which can lead to more accurate approximations.
  • Quantized Tensor Train (QTT) Decomposition: Representing the large stiffness matrix as a low-rank tensor, drastically reducing memory requirements.
  • Z-ordering: A specific ordering of mesh nodes that helps to keep the TT-ranks low during the construction process. This is a crucial departure from standard ordering.
  • Z-kron Operation: A new operation designed to efficiently build QTT matrices in z-order, particularly useful when matrices can be expressed as Kronecker products.
  • "On-the-fly" Construction: The algorithm builds the QTT representation of the stiffness matrix directly, without first forming a dense matrix, which is critical for efficiency.
  • Concatenation Scheme: A method to handle the continuity and boundary conditions between adjacent subdomains, expressed in a way that is amenable to TT representation.

Datasets

Not discussed in the paper. The paper focuses on a numerical method and its evaluation on synthetic domains.

Key Insights and Ideas

  • Z-ordering is Key for Low Ranks: The paper highlights that a standard row-by-row ordering of unknowns leads to high TT-ranks, making the method impractical. Introducing a z-order traversal of nodes is essential for keeping the ranks manageable.
  • "On-the-Fly" QTT Construction is Crucial: Transforming a dense matrix into QTT format is computationally expensive and memory-intensive. Building the QTT representation directly during the discretization process is a significant advantage.
  • Z-kron Operation Simplifies QTT Matrix Assembly: This new operation provides an elegant way to combine QTT matrices in a z-ordered fashion, which is fundamental to the proposed algorithm.
  • Isogeometric Analysis Enhances Accuracy: Combining isogeometric analysis with QTT offers a powerful approach for solving PDEs, potentially leading to better accuracy with fewer degrees of freedom.
  • Memory Savings are Substantial: The QTT representation, especially with z-ordering, leads to dramatic reductions in memory consumption compared to traditional FEM solvers.

Key Results

The paper demonstrates that the proposed QTT-isogeometric solver achieves:

  • Second-order convergence: The numerical solutions exhibit second-order accuracy with respect to the mesh refinement.
  • Significantly reduced memory consumption: The QTT approach offers substantial memory savings compared to FEniCS, a standard FEM solver. For instance, Figure 6 shows that for a triangle domain, the peak memory consumption for the QTT solver is considerably lower than FEniCS across various vertex counts.
  • Slow erank growth: The "effective rank" (erank) of the QTT matrices grows slowly with the number of vertices, indicating the efficiency of the QTT representation.
  • Upper bound for solution energy: The algorithm provides an upper bound for the solution energy, which is a desirable property in some applications.
  • Logarithmic complexity: The discretization scheme for constructing the global stiffness matrix in QTT-format has O(log n) complexity, where n is related to the number of nodes per quadrangle side.

Limitations and Future Work

  • Limitations: The paper focuses on 2D elliptic PDEs. Extending the method to higher dimensions or other types of PDEs (e.g., parabolic, hyperbolic) would be a natural next step. The current implementation might also have limitations in handling very complex geometries that are difficult to decompose into quadrangles.
  • Future Work: The authors suggest exploring the application of their method to more complex problems and geometries. Further investigation into optimizing the QTT operations and exploring different discretization schemes could also be beneficial. The paper also implicitly suggests that further research into the theoretical properties of the z-order and z-kron operations in the context of QTT could yield additional insights.

Summary updated

Abstract

The goal of this paper is to develop a numerical algorithm that solves a two-dimensional elliptic partial differential equation in a polygonal domain using tensor methods and ideas from isogeometric analysis. The proposed algorithm is based on the Finite Element (FE) approximation with Quantized Tensor Train decomposition (QTT) used for matrix representation and solution approximation. In this paper we propose a special discretisation scheme that allows to construct the global stiffness matrix in the QTT-format. The algorithm has $O(\log n)$ complexity, where $n=2^d$ is the number of nodes per quadrangle side. A new operation called z-kron is introduced for QTT-format. It makes it possible to build a matrix in z-order if the matrix can be expressed in terms of Kronecker products and sums. An algorithm for building a QTT coefficient matrix for FEM in z-order "on the fly", as opposed to the transformation of a calculated matrix into QTT, is presented. This algorithm has $O(\log n)$ complexity for $n$ as above.
BibTeX
@article{markeeva2018qtt,
  author = {Larisa Markeeva and I. V. Tsybulin and Ivan Oseledets},
  title = {{QTT-isogeometric solver in two dimensions}},
  journal = {Journal of Computational Physics},
  year = {2018},
}
Figure