Randomized linear algebra for model order reduction

Solutions to high-dimensional parameter-dependent problems are in great demand in the contemporary applied science and engineering. The standard approximation methods for parametric equations can require computational resources that are exponential in the dimension of the parameter space, which is typically refereed to as the curse of dimensionality. To break the curse of dimensionality one has to appeal to nonlinear methods that exploit the structure of the solution map, such as projection-based model order reduction methods. This thesis proposes novel methods based on randomized linear algebra to enhance the efficiency and stability of projection-based model order reduction methods for solving parameter-dependent equations. Our methodology relies on random projections (or random sketching). Instead of operating with high-dimensional vectors we first efficiently project them into a low-dimensional space. The reduced model is then efficiently and numerically stably constructed from the projections of the reduced approximation space and the spaces of associated residuals. Our approach allows drastic computational savings in basically any modern computational architecture. For instance, it can reduce the number of flops and memory consumption and improve the efficiency of the data flow (characterized by scalability or communication costs). It can be employed for improving the efficiency and numerical stability of classical Galerkin and minimal residual methods. It can also be used for the efficient estimation of the error, and post-processing of the solution of the reduced order model. Furthermore, random sketching makes computationally feasible a dictionary-based approximation method, where for each parameter value the solution is approximated in a subspace with a basis selected from a dictionary of vectors. We also address the efficient construction (using random sketching) of parameter-dependent preconditioners that can be used to improve the quality of Galerkin projections or for effective error certification for problems with ill-conditioned operators. For all proposed methods we provide precise conditions on the random sketch to guarantee accurate and stable estimations with a user-specified probability of success. A priori estimates to determine the sizes of the random matrices are provided as well as a more effective adaptive procedure based on a posteriori estimates.Cette thèse introduit des nouvelles approches basées sur l’algèbre linéaire aléatoire pour améliorer l’efficacité et la stabilité des méthodes de réduction de modèles basées sur des projections pour la résolution d’équations dépendant de paramètres. Notre méthodologie repose sur des techniques de projections aléatoires ("random sketching") qui consistent à projeter des vecteurs de grande dimension dans un espace de faible dimension. Un modèle réduit est ainsi construit de manière efficace et numériquement stable à partir de projections aléatoires de l’espace d’approximation réduit et des espaces des résidus associés. Notre approche permet de réaliser des économies de calcul considérables dans pratiquement toutes les architectures de calcul modernes. Par exemple, elle peut réduire le nombre de flops et la consommation de mémoire et améliorer l’efficacité du flux de données (caractérisé par l’extensibilité ou le coût de communication). Elle peut être utilisée pour améliorer l’efficacité et la stabilité des méthodes de projection de Galerkin ou par minimisation de résidu. Elle peut également être utilisée pour estimer efficacement l’erreur et post-traiter la solution du modèle réduit. De plus, l’approche par projection aléatoire rend viable numériquement une méthode d’approximation basée sur un dictionnaire, où pour chaque valeur de paramètre, la solution est approchée dans un sous-espace avec une base sélectionnée dans le dictionnaire. Nous abordons également la construction efficace (par projections aléatoires) de préconditionneurs dépendant de paramètres, qui peuvent être utilisés pour améliorer la qualité des projections de Galerkin ou des estimateurs d’erreur pour des problèmes à opérateurs mal conditionnés. Pour toutes les méthodes proposées, nous fournissons des conditions précises sur les projections aléatoires pour garantir des estimations précises et stables avec une probabilité de succès spécifiée par l’utilisateur. Pour déterminer la taille des matrices aléatoires, nous fournissons des bornes a priori ainsi qu’une procédure adaptative plus efficace basée sur des estimations a posterior