Добірка наукової літератури з теми "Algèbre linéaire et multilinéaire numérique"

Cette thèse présente de nouveaux algorithmes numériques et effectue une étude approfondie de certaines méthodes numériques existantes pour relever les défis de haute dimension résultant de la résolution de l'équation de Schrödinger électronique en chimie quantique. En se concentrant sur deux problèmes spécifiques, notre approche implique l'identification et l'exploitation des symétries et des structures de rang faible au sein de matrices et de tenseurs. Le premier problème abordé dans cette thèse concerne l'évaluation numérique efficace de la composante à longue portée du potentiel de Coulomb à séparation de portée et des intégrales à deux électrons à longue portée, un tenseur du quatrième ordre qui intervient dans de nombreuses méthodes de chimie quantique. Nous présentons deux nouvelles méthodes d'approximation. Cela est réalisé en s'appuyant sur l'interpolation Chebyshev, des règles de quadrature Gaussienne combinées à des approximations de rang faible ainsi que des méthodes rapides multipolaires (FMM). Ce travail offre une explication détaillée de ces approches et algorithmes introduits, accompagnée d'une comparaison approfondie entre les méthodes nouvellement proposées. Le deuxième problème abordé concerne l'exploitation des symétries et des structures de rang faible pour dériver des représentations efficaces en train de tenseurs des opérateurs impliqués dans l'algorithme DMRG. Cet algorithme est une méthode d'optimisation itérative précise utilisée pour résoudre numériquement l'équation de Schrödinger indépendante du temps. Ce travail vise à comprendre et interpréter les résultats obtenus par les communautés de physique et de chimie, et cherche à offrir des perspectives théoriques nouvelles qui, selon nos connaissances, n'ont pas reçu une attention significative auparavant. Nous menons une étude approfondie et fournissons des démonstrations, si nécessaire, pour explorer l'existence d'une représentation particulière en train de tenseurs, creuse par blocs, de l'opérateur Hamiltonien et de sa fonction d'onde associée. Cela est réalisé tout en maintenant les lois de conservation physiques, manifestées sous forme de symétries de groupe dans les tenseurs, telles que la conservation du nombre de particules. La troisième partie de ce travail est dédiée à la réalisation d'une bibliothèque prototype en Julia, pour l'implémentation de DMRG qui est conçue pour le modèle d'opérateur Hamiltonien de la chimie quantique. Nous exploitons ici la représentation en train de tenseurs, creuse par blocs, de l'opérateur et de la fonction d'onde (fonction propre). Avec ces structures, notre objectif est d'accélérer les étapes les plus coûteuses de la DMRG, y compris les contractions de tenseurs, les opérations matrice-vecteur, et la compression de matrices par décomposition en valeurs singulières tronquée. De plus, nous fournissons des résultats issus de diverses simulations moléculaires, tout en comparant les performances de notre bibliothèque avec la bibliothèque ITensors de pointe, où nous démontrons avoir atteint une performance similaire
This thesis presents novel numerical algorithms and conducts a comprehensive study of some existing numerical methods to address high-dimensional challenges arising from the resolution of the electronic Schrödinger equation in quantum chemistry. Focusing on two specific problems, our approach involves the identification and exploitation of symmetries and low-rank structures within matrices and tensors, aiming to mitigate the curse of dimensionality. The first problem considered in this thesis is the efficient numerical evaluation of the long-range component of the range-separated Coulomb potential and the long-range two-electron integrals 4th-order tensor which occurs in many quantum chemistry methods. We present two novel approximation methods. This is achieved by relying on tensorized Chebyshev interpolation, Gaussian quadrature rules combined with low-rank approximations as well as Fast Multipole Methods (FMM). This work offers a detailed explanation of these introduced approaches and algorithms, accompanied by a thorough comparison between the newly proposed methods. The second problem of interest is the exploitation of symmetries and low-rank structures to derive efficient tensor train representations of operators involved in the Density Matrix Renormalization Group (DMRG) algorithm. This algorithm, referred to as the Quantum Chemical DMRG (QC-DMRG) when applied in the field of quantum chemistry, is an accurate iterative optimization method employed to numerically solve the time-independent Schrödinger equation. This work aims to understand and interpret the results obtained from the physics and chemistry communities and seeks to offer novel theoretical insights that, to the best of our knowledge, have not received significant attention before. We conduct a comprehensive study and provide demonstrations, when necessary, to explore the existence of a particular block-sparse tensor train representation of the Hamiltonian operator and its associated eigenfunction. This is achieved while maintaining physical conservation laws, manifested as group symmetries in tensors, such as the conservation of the particle number. The third part of this work is dedicated to the realization of a proof-of-concept Quantum Chemical DMRG (QC-DMRG) Julia library, designed for the quantum chemical Hamiltonian operator model. We exploit here the block-sparse tensor train representation of both the operator and the eigenfunction. With these structures, our goal is to speed up the most time-consuming steps in QC-DMRG, including tensor contractions, matrix-vector operations, and matrix compression through truncated Singular Value Decompositions (SVD). Furthermore, we provide empirical results from various molecular simulations, while comparing the performance of our library with the state-of-the-art ITensors library where we show that we attain a similar performance

Le problème de Zolotarev pour des ensembles discrets apparaît pour décrire le taux de convergence de la méthode ADI, dans l'approximation de certaines fonctions matricielles ou encore pour quantifier le taux de décroissance des valeurs singulières de certaines matrices structurées. De plus, la réduction de modèle constitue un enjeu important en théorie du contrôle linéaire, et on peut prédire la qualité de l'approximation d'un système dynamique linéaire continu stationnaire de grande dimension donné grâce à la résolution approchée d'une équation de Sylvester. Après avoir prouvé l'existence d'un minimiseur pour le troisième problème de Zolotarev pour des ensembles discrets, on détermine dans cette thèse le comportement asymptotique faible de ce problème sous certaines hypothèses de régularité. Pour mener cette étude, on considère un problème de minimisation d'énergie sous contraintes pour des mesures signées en théorie du potentiel logarithmique. On discute également la précision de nos résultats asymptotiques pour des ensembles discrets généraux du plan complexe, et une formule intégrale explicite est établie dans le cas particulier de deux sous-ensembles discrets de l'axe réel symétriques par rapport à l'origine. L'impact de nos résultats théoriques pour l'analyse du taux de convergence de la méthode ADI appliquée pour la résolution approchée d'une équation de Lyapounov est estimé à l'aide de plusieurs exemples numériques après avoir exposé l'algorithme nous permettant d'obtenir les paramètres utilisés.

Mes travaux peuvent se diviser en deux thèmes : L'algèbre linéaire numérique. La théorie des opérateurs intégraux. L'algèbre linéaire numérique fut le cadre de ma thèse de doctorat, dédiée aux propriétés spectrales des opérateurs de Sylvester, endomorphismes d'espaces matriciels. J'ai tout naturellement utilisé mes connaissances, mes compétences et mon savoir faire, développés pendant ces années de formation par la recherche, pour attaquer un nouveau problème li e a une notion apparue dans les années 1990 et qui a connu un grand succès dans la communauté de l'algèbre linéaire numérique. Cette notion est celle des pseudospectres qui généralise celle des spectres dans le cadre de la théorie des perturbations. A cette notion est liée celle de rayon de stabilité. Suite a ces travaux sur les pseudospectres et ayant constat e que pour certaines matrices pathologiques, la détermination du pseudospectre était couteuse et entachées d'erreurs importantes, nous avons cherché si l'on ne pouvait pas définir d'autres généralisations du spectre plus facilement calculables. Nous avons étudié un ensemble du plan complexe, contenant les valeurs propres d'une matrice, défini comme un -voisinage des racines du polynome caractéristique. Je me suis ensuite tout naturellement tournée vers un nouveau chalenge, celui du problème polynomial de valeurs propres. Ce sujet s'est développé très récemment. Il y a des questions propres aux problèmes polynomiaux de valeurs propres qui n'ont ete posées qu' a partir des années 2000 et qui n'ont trouvées de premières réponses que cinq ans plus tard. Le domaine des problèmes polynomiaux de valeurs propres est en pleine expansion et beaucoup de problèmes restent a résoudre dans l'avenir. Parallèlement et plus directement li e aux équations matricielles, je me suis intéressée a la notion de stabilité de Lyapunov, tr es utile dans la communauté de la théorie du contrôle. Mon autre domaine de recherche concerne les équations intégrales du point de vue de l'approximation. Des méthodes de discrétisation conduisant a des matrices diagonales sont intéressantes. Ces considérations m'ont conduite à étudier l'approximation d'un équation d'opérateur intégral par une méthode d'ondelettes-vaguelettes. La difficulté de la mise en œuvre numérique m'a dirigée vers l' étude d'autres méthodes.

Les travaux présentés dans cette thèse portent sur la stabilité et la précision de certains algorithmes numériques. Les contributions de cette thèse se situent à quatre niveaux : 1) Amélioration de la précision : on propose un algorithme de Horner compensé qui calcule un résultat avec la même précision que si il avait été calculé par le schéma de Horner classique, mais avec une précision interne doublée. 2) Applications des pseudozéros : on propose des application de pseudozéros en calcul formel (primalité approchée) et en théorie du contrôle (rayon de stabilité et pseudoabscisses). 3) Prise en compte des perturbations réelles : on donne des formules calculables pour le conditionnement réel et l'erreur inverse réelle pour des problèmes de l'évaluation polynomiale et le calcul de racines. Nous montrons qu'il y a peu de différences entre le conditionnement réel et le conditionnement classique. Néanmoins, nous montrons que l'erreur inverse réelle peut être significativement plus grande que l'erreur inverse classique. 4) Perturbations matricielles structurées : nous étudions la notion de pseudospectre structuré pour les matrices Toeplitz, circulantes et Hankel. Nous montrons qu'il n'y a pas de différence entre le pseudospectre structuré et le pseudospectre classique. Nous étudions aussi des conditionnements pour les systèmes linéaires et l'inversion matricielle pour des structures dérivant d'algèbres de Lie et de Jordan. Nous étudions pour quelles sous-classes de ces structures il n'y a pas ou peu de différences entre les conditionnements structurés et non structurés
The result summarized in the document deal with the stability and accuracy of some numerical algorithms. The contributions of this work are divided into four levels : 1) Improvement of the accuracy : we prensent a compensated Horner scheme that computes a result as if computed in twice the working précision. 2) Applications of pseudozero set : we propose some applications of pseudozeros in computer algebra (approximate coprimeness) and in control theory (stability radius and pseudoabscissa). 3) Real perturbations : we give computable formulas for the real condition number and real backward error for the problem of polynomial evaluation and the computation of zeros. We show that there is little difference between the real and complex condition numbers. On the contrary, we show that the real backward error can be significantly larger than the complex one. 4) Structured matrix perturbation : we study the notion of structured pseudospectra for Toeplitz, Hankel and circulant matrices. We show for this structures there is no difference between the structured and the unstructured pseudospectra. We also study structured condition number for linear systems, inversions and distance to singularity for structures deriving from Lie and Jordan algebras. We show that under mild assumptions there is little or no difference between the structured and the unstructured condition numbers

Dans la realisation de circuits integres a application specifique, l'interfacage avec le milieu exterieur est realise par des convertisseurs qui determinent en grande partie les caracteristiques de surface, vitesse et precision, donc le cout de l'application consideree. Dans ce memoire, nous presentons l'etude et la realisation de convertisseurs adaptes a la technologie cmos. Plusieurs structures ont ete realisees et comparees: convertisseurs tension-courant (cti) utilisant les caracteristiques quadratiques des transistors mos, oscillateur controle en tension (vco) lineaire et stable en temperature, derive d'une structure bipolaire, application aux structures a retard programmable: convertisseur temps-numerique autocalibre

Cette thèse est constituée de deux parties. La première traite de la méthode QR pour le calcul de valeurs propres de matrices quelconques, de tailles modérées. Les contributions originales à ce sujet sont a) une preuve rigoureuse de sa stabilité inverse, b) un nouveau critère d'arrêt justifié par une analyse mathématique. La seconde partie traite de la méthode de Yau et Lu pour le calcul de valeurs propres de matrices symétriques réelles de grandes tailles. Les contributions dans ce travail à ce sujet sont a) une compréhension mathématique accrue de la méthode, b) sa validation numérique, c) une proposition de parallélisation