Linear and nonlinear substructured Restricted Additive Schwarz iterations and preconditioning

Iterative substructuring Domain Decomposition (DD) methods have been extensively studied, and they are usually associated with nonoverlapping decompositions. It is less known that classical overlapping DD methods can also be formulated in substructured form, i.e., as iterative methods acting on variables defined exclusively on the interfaces of the overlapping domain decomposition. We call such formulations substructured domain decomposition methods. We introduce here a substructured version of Restricted Additive Schwarz (RAS) which we call SRAS. We show that RAS and SRAS are equivalent when used as iterative solvers, as they produce the same iterates, while they are substantially different when used as preconditioners for GMRES. We link the volume and substructured Krylov spaces and show that the iterates are different by deriving the least squares problems solved at each GMRES iteration. When used as iterative solvers, SRAS presents computational advantages over RAS, as it avoids computations with matrices and vectors at the volume level. When used as preconditioners, SRAS has the further advantage of allowing GMRES to store smaller vectors and perform orthogonalization in a lower dimensional space. We then consider nonlinear problems, and we introduce SRASPEN (Substructured Restricted Additive Schwarz Preconditioned Exact Newton), where SRAS is used as a preconditioner for Newton’s method. In contrast to the linear case, we prove that Newton’s method applied to the preconditioned volume and substructured formulation produces the same iterates in the nonlinear case. Next, we introduce two-level versions of nonlinear SRAS and SRASPEN. Finally, we validate our theoretical results with numerical experiments.

Dictionary Learning for Two-Dimensional Kendall Shapes

Julien René Fageot, Anna You-Lai Song, Virginie Sophie Uhlmann, Michaël Unser

We propose a novel sparse dictionary learning method for planar shapes in the sense of Kendall, namely configurations of landmarks in the plane considered up to similitudes. Our shape dictionary method provides a good trade-off between algorithmic simplicity and faithfulness with respect to the nonlinear geometric structure of Kendall's shape space. Remarkably, it boils down to a classical dictionary learning formulation modified using complex weights. Existing dictionary learning methods extended to nonlinear spaces map the manifold either to a reproducing kernel Hilbert space or to a tangent space. The first approach is unnecessarily heavy in the case of Kendall's shape space and causes the geometrical understanding of shapes to be lost, while the second one induces distortions and theoretical complexity. Our approach does not suffer from these drawbacks. Instead of embedding the shape space into a linear space, we rely on the hyperplane of centered configurations, including preshapes from which shapes are defined as rotation orbits. In this linear space, the dictionary atoms are scaled and rotated using complex weights before summation. Furthermore, our formulation is more general than Kendall's original one: it applies to discretely defined configurations of landmarks as well as continuously defined interpolating curves. We implemented our algorithm by adapting the method of optimal directions combined to a Cholesky-optimized order recursive matching pursuit. An interesting feature of our shape dictionary is that it produces visually realistic atoms, while guaranteeing reconstruction accuracy. Its efficiency can mostly be attributed to a clear formulation of the framework with complex numbers. We illustrate the strong potential of our approach for the characterization of datasets of shapes up to similitudes and the analysis of patterns in deforming two-dimensional shapes.

SIAM PUBLICATIONS2020

Reduced order modeling techniques for numerical homogenization methods applied to linear and nonlinear multiscale problems

Yun Bai

The characteristic of effective properties of physical processes in heterogeneous media is a basic modeling and computational problem for many applications. As standard numerical discretization of such multiscale problems (e.g. with classical finite element method (FEM)) is often computationally prohibitive, there is a need for a novel computational algorithm able to capture the effective behavior of the physical system without resolving the finest scale in the system on the whole computational domain. In this thesis we propose and analyze a new class of numerical methods that combine the so-called finite element heterogeneous multiscale method (FE-HMM) with reduced order modeling techniques for linear and nonlinear multiscale problems. In the first part of the thesis we generalize the FE-HMM to elliptic problems with an arbitrary number of well-separated scales. We provide a rigorous a priori error analysis of this method that generalizes previous work restricted to two-scale problems. In the second part of the thesis, we develop our new reduced order multiscale method that combines the FE-HMM with reduced basis (RB) method. This method, the reduced basis finite element heterogeneous multiscale method (RB-FE-HMM) provides a significant improvement in computational efficiency compared to the FE-HMM, specially for high dimensional problems or high order methods. A priori and a posteriori error analyses are derived for linear elliptic problems, as well as goal oriented adaptivity techniques. The RB-FE-HMM is then generalized to a class of nonlinear elliptic and parabolic problems. A priori error analysis and extensive computational results for nonlinear problems are also provided.

EPFL2013

Reduced order modelling numerical homogenization

Assyr Abdulle, Yun Bai

A general framework to combine numerical homogenization and reduced-order modelling techniques for partial differential equations (PDEs) with multiple scales is described. Numerical homogenization methods are usually efficient to approximate the effective solution of PDEs with multiple scales. However, classical numerical homogenization techniques require the numerical solution of a large number of so-called microproblems to approximate the effective data at selected grid points of the computational domain. Such computations become particularly expensive for high-dimensional, time-dependent or nonlinear problems. In this paper, we explain how numerical homogenization method can benefit from reduced-order modelling techniques that allow one to identify offline and online computational procedures. The effective data are only computed accurately at a carefully selected number of grid points (offline stage) appropriately ‘interpolated’ in the online stage resulting in an online cost comparable to that of a single-scale solver. The methodology is presented for a class of PDEs with multiple scales, including elliptic, parabolic, wave and nonlinear problems. Numerical examples, including wave propagation in inhomogeneous media and solute transport in unsaturated porous media, illustrate the proposed method.

Royal Soc2014

Dictionary Learning for Two-Dimensional Kendall Shapes

Julien René Fageot, Anna You-Lai Song, Virginie Sophie Uhlmann, Michaël Unser

SIAM PUBLICATIONS2020