Research reports

Main content

Years: 2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  1995  1994  1993  1992  1991 

QTT-Finite-Element Approximation For Multiscale Problems

by V. Kazeev and I. Oseledets and M. Rakhuba and Ch. Schwab

(Report number 2016-06)

Tensor-compressed numerical solution of elliptic multiscale-diffusion and high frequency scattering problems is considered. For either problem class, solutions exhibit multiple length scales governed by the corresponding scale parameter: the scale of oscillations of the diffusion coefficient or smallest wavelength, respectively. As is well-known, this imposes a scale-resolution requirement on the number of degrees of freedom required to accurately represent the solutions in standard finite-element (FE) discretizations. Low-order FE methods are by now generally perceived unsuitable for high-frequency diffusion coefficients and high wavenumbers, and special techniques have been proposed instead (such as numerical homogenization, heterogeneous multiscale method, oversampling, etc.). They require, in some form, a-priori information on the microstructure of the solution. We propose the use of tensor-structured compressed first-order FE methods for scale resolution without a-priori information. The FE methods are based on principal components dynamically extracted from the FE solution by non-linear, quantized tensor train (QTT) decomposition of the system matrix, load and solution vectors. For prototypical model problems, we prove that this approach identifies effective degrees of freedom from a uniform ``virtual'' (i.e. never directly accessed) mesh and its corresponding degrees of freedom (whose number may be prohibitively large). Precisely, solutions of model elliptic homogenization and high frequency acoustic scattering problems are proved to admit QTT-formatted approximations whose number of effective degrees of freedom is robust in the scale parameter and polylogarithmic with respect to the reciprocal of the target Sobolev-norm accuracy. No a-priori information on the nature of the problems and intrinsic length scales of the solution is required in the proposed approach. As a corollary of our analysis, we prove that the Kolmogorov \(n\)-widths of solutions sets are exponentially small for analytic data, independent of the problems' scale parameters. That implies, in particular, robust exponential convergence of reduced basis and MOR techniques. Detailed numerical experiments confirm the theoretical bounds.

Keywords: multiscale problems, Helmholtz equation, homogenization, scale resolution, exponential convergence, tensor decompositions, quantized tensor trains

  author = {V. Kazeev and I. Oseledets and M. Rakhuba and Ch. Schwab},
  title = {QTT-Finite-Element Approximation For Multiscale Problems},
  institution = {Seminar for Applied Mathematics, ETH Z{\"u}rich},
  number = {2016-06},
  address = {Switzerland},
  url = { },
  year = {2016}

© The copyright for the following documents lies with the authors. Copies of these documents made by electronic or mechanical means including information storage and retrieval systems, may only be employed for personal use. The administrators respectfully request that authors inform them when any paper is published to avoid copyright infringement. Note that unauthorised copying of copyright material is illegal and may lead to prosecution. Neither the administrators nor the Seminar for Applied Mathematics accept any liability in this respect.

Page URL:
Tue Jun 27 17:28:40 CEST 2017
© 2017 Eidgenössische Technische Hochschule Zürich