Approximating the trace of iterative solutions at the interfaces with Nonuniform Fourier transform and singular value decomposition for cost-effectively accelerating the convergence of Schwarz domain decomposition

University of Lyon, University Lyon1 CNRS Institut Camille Jordan UMR5208, 43 Bd du 11 Novembre 1918, F-69150 Villeurbanne cedex, France

Abstract

This paper deals with the representation of the trace of iterative Schwarz solutions at the interfaces of domain decomposition to approximate adaptively the interface error operator. This allows to build a cost-effectively accelerating of the convergence of the iterative method by extending to the vectorial case the Aitken’s accelerating convergence technique. The first representation is based on the building of a nonuniform discrete Fourier transform defined on a non-regular grid. We show how to construct a Fourier basis of dimension N+1 on this grid by building numerically a sesquilinear form, its exact accuracy to represent trigonometric polynomials of degree N / 2, and its spectral approximation property that depends on the continuity of the function to approximate. The decay of Fourier-like modes of the approximation of the trace of the iterative solution at the interfaces provides an estimate to adaptively select the modes involved in the acceleration. The drawback of this approach is to be dependent on the continuity of the trace of the iterated solution at the interfaces. The second representation, purely algebraic, uses a singular value decomposition of the trace of the iterative solution at the interfaces to provide a set of orthogonal singular vectors of which the associated singular values provide an estimate to adapt the acceleration. The resulting Aitken-Schwarz methodology is then applied to large scale computing on 3D linear Darcy flow where the permeability follows a log normal random distribution.

Résumé

Cet acte traite de la représentation des solutions itérées aux interfaces de la méthode de décomposition de domaine de type Schwarz afin d’approximer de manière adaptative son opérateur d’erreur aux interfaces des sous domaines. Ceci permet de construire de manière économique l’accélération de la convergence de la méthode itérative en étendant la technique d’accélération de la convergence de Aitken au cas vectoriel. La première représentation est fondée sur la construction d’une transformée de Fourier discrète non uniforme définie sur un maillage non régulier. Nous montrons comment construire une base de Fourier de dimension N+1 sur ce maillage à partir de la construction numérique d’une forme sesquilinéaire, son exactitude pour les polynômes trigonométriques de degré N/2, et numériquement sa capacité d’approximation spectrale dépendante de la continuité de la fonction à approximer. La décroissance des modes de Fourier de la trace de la solution itérée aux interfaces nous fournis une estimation pour sélectionner de manière adaptive les modes intervenant dans l’accélération. Le défaut de cette approche est d’être dépendant de la continuité de la solution itérée aux interfaces. La deuxième représentation, purement algébrique, utilise une décomposition en valeurs singulières des solutions itérées aux interfaces pour fournir un ensemble de vecteurs singuliers orthogonaux dont les valeurs singulières associées fournissent une estimation pour adapter l’accélération. La méthode Aitken-Schwarz résultante est ensuite appliquée au calcul à grande échelle pour résoudre un écoulement 3D en milieu poreux modélisé par l’équation de Darcy linéaire où la perméabilité suit une distribution aléatoire log-normale.