**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Preconditioned Low-Rank Riemannian Optimization For Linear Systems With Tensor Product Structure

Abstract

The numerical solution of partial differential equations on high-dimensional domains gives rise to computationally challenging linear systems. When using standard discretization techniques, the size of the linear system grows exponentially with the number of dimensions, making the use of classic iterative solvers infeasible. During the last few years, low-rank tensor approaches have been developed that allow one to mitigate this curse of dimensionality by exploiting the underlying structure of the linear operator. In this work, we focus on tensors represented in the Tucker and tensor train formats. We propose two preconditioned gradient methods on the corresponding low-rank tensor manifolds: a Riemannian version of the preconditioned Richardson method as well as an approximate Newton scheme based on the Riemannian Hessian. For the latter, considerable attention is given to the efficient solution of the resulting Newton equation. In numerical experiments, we compare the efficiency of our Riemannian algorithms with other established tensor-based approaches such as a truncated preconditioned Richardson method and the alternating linear scheme. The results show that our approximate Riemannian Newton scheme is significantly faster in cases when the application of the linear operator is expensive.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related concepts (23)

Tensor

In mathematics, a tensor is an algebraic object that describes a multilinear relationship between sets of algebraic objects related to a vector space. Tensors may map between different objects such

Partial differential equation

In mathematics, a partial differential equation (PDE) is an equation which computes a function between various partial derivatives of a multivariable function.
The function is often thought of as

Numerical analysis

Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathema

Related publications (29)

Loading

Loading

Loading

Daniel Kressner, Michael Maximilian Steinlechner

The numerical solution of partial differential equations on high-dimensional domains gives rise to computationally challenging linear systems. When using standard discretization techniques, the size of the linear system grows exponentially with the number of dimensions, making the use of classic iterative solvers infeasible. During the last few years, low-rank tensor approaches have been developed that allow to mitigate this curse of dimensionality by exploiting the underlying structure of the linear operator. In this work, we focus on tensors represented in the Tucker and tensor train formats. We propose two preconditioned gradient methods on the corresponding low-rank tensor manifolds: A Riemannian version of the preconditioned Richardson method as well as an approximate Newton scheme based on the Riemannian Hessian. For the latter, considerable attention is given to the efficient solution of the resulting Newton equation. In numerical experiments, we compare the efficiency of our Riemannian algorithms with other established tensor-based approaches such as a truncated preconditioned Richardson method and the alternating linear scheme. The results show that our approximate Riemannian Newton scheme is significantly faster in cases when the application of the linear operator is expensive.

Modeling wave propagation in highly heterogeneous media is of prime importance in engineering applications of diverse nature such as seismic inversion, medical imaging or the design of composite materials. The numerical approximation of such multiscale physical models is a mathematical challenge. Indeed, to reach an acceptable accuracy, standard numerical methods require the discretization of the whole medium at the microscopic scale, which leads to a prohibitive computational cost. Homogenization theory ensures the existence of a homogenized wave equation, obtained from the original problem by a limiting process. As this equation does not depend on the microscopic scale, it is a good target for numerical methods. Unfortunately, for general media, the homogenized equation may not be unique and no formulas are available for its effective data. %Diverse numerical strategies have been developed to approximate a homogenized solution. Nevertheless, such formulas are known for media described by a locally periodic tensor. In that case, or more generally for problems with scale separation, methods such as the finite element heterogeneous multiscale method (FE-HMM) are proved to efficiently approximate the homogenized solution. For wave propagation in heterogeneous media, however, it is known that at large timescales the homogenized solution fails to describe the dispersive behavior of the original wave. Hence, a new equation that captures this dispersion is needed. In this thesis, we study such effective equations for long time wave propagation in heterogeneous media. The first result that we present holds in periodic media. Using the technique of asymptotic expansion, we obtain the characterization of a whole family of equations that describes the long time dispersive effects of the oscillating wave. The validity of our derivation is ensured by rigorous a priori error estimates. We also derive a numerical procedure for the computation of the tensors involved in the first order effective equations. This leads to a numerical homogenization method for long time wave propagation in periodic media. The second result that we present generalizes the procedure for deriving effective equations to arbitrary timescales. This generalization is also useful, for example, for the homogenization of the wave equation with high frequency initial data. We also provide a numerical procedure allowing to compute effective tensors of arbitrary order. The third result is the generalization of the family of first order effective equations from periodic to locally periodic media. A rigorous a priori error analysis is also derived in this situation. This constitutes the first analysis of effective models for the long time approximation of the wave equation in locally periodic media. In a second part of the thesis, we derive numerical homogenization methods for the long time approximation of the wave equation in locally periodic media. In one dimension, we analyze a modification of the FE-HMM called the FE-HMM-L. In higher dimensions, we design a spectral homogenization method. For both methods, we prove error estimates valid for large timescales and in arbitrarily large spatial domains. In particular, we show that these numerical homogenization methods converge to effective solutions that approximate the highly oscillatory wave equation over long time.

Several computational challenges arise when evaluating the failure probability of a given system in the context of risk prediction or reliability analysis. When the dimension of the uncertainties becomes high, well established direct numerical methods can not be employed because of the "curse-of-dimensionality". Many surrogate models have been proposed with the aim of reducing computational effort. However, most of them fail in computing an accurate failure probability when the limit state surface defined by the failure event in the probability space lacks smoothness. In addition, for a stochastic system modeled by partial differential equations (PDEs) with random input, only a limited number of the underlying PDEs (order of a few tens) are affordable to solve in practice due to the considerable computational effort, therefore preventing the application of many numerical methods especially for high dimensional random inputs. In this work we develop hybrid and goal-oriented adaptive reduced basis methods to tackle these challenges by accurately and efficiently computing the failure probability of a stochastic PDE. The curse-of-dimensionality is significantly alleviated by reduced basis approximation whose bases are constructed by goal-oriented adaptation. Moreover, an accurate evaluation of the failure probability for PDE system with solution of low regularity in probability space is guaranteed by the certified a posteriori error bound for the output approximation error. At the end of this paper we suitably extend our proposed method to deal with more general PDE models. Finally we perform several numerical experiments to illustrate its computational accuracy and efficiency. (C) 2013 Elsevier B.V. All rights reserved.