Research reports

Years: 2024 2023 2022 2021 2020 2019 2018 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)

Abstract
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

@Techreport{KORS16_643,
  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 = {https://www.sam.math.ethz.ch/sam_reports/reports_final/reports2016/2016-06.pdf },
  year = {2016}
}

Disclaimer
© Copyright for documents on this server remains 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 (SAM) accept any liability in this respect. The most recent version of a SAM report may differ in formatting and style from published journal version. Do reference the published version if possible (see SAM Publications).