La résolution de très grands systèmes linéaires creux est une composante de base algorithmique fondamentale dans de nombreuses applications scientifiques en calcul intensif. La résolution per- formante de ces systèmes passe par la conception, le développement et l'utilisation d'algorithmes parallèles performants. Dans nos travaux, nous nous intéressons au développement et l'évaluation d'une méthode hybride (directe/itérative) basée sur des techniques de décomposition de domaine sans recouvrement. La stratégie de développement est axée sur l'utilisation des machines mas- sivement parallèles à plusieurs milliers de processeurs. L'étude systématique de l'extensibilité et l'efficacité parallèle de différents préconditionneurs algébriques est réalisée aussi bien d'un point de vue informatique que numérique. Nous avons comparé leurs performances sur des systèmes de plusieurs millions ou dizaines de millions d'inconnues pour des problèmes réels 3D .

We present a unified and self-contained treatment of rational Krylov methods for approximating the product of a function of a linear operator with a vector. With the help of general rational Krylov decompositions we reveal the connections between seemingly different approximation methods, such as the Rayleigh–Ritz or shift-and-invert method, and derive new methods, for example a restarted rational Krylov method and a related method based on rational interpolation in prescribed nodes. Various theorems known for polynomial Krylov spaces are generalized to the rational Krylov case. Computational issues, such as the computation of so-called matrix Rayleigh quotients or parallel variants of rational Arnoldi algorithms, are discussed. We also present novel estimates for the error arising from inexact linear system solves and the approximation error of the Rayleigh–Ritz method. Rational Krylov methods involve several parameters and we discuss their optimal choice by considering the underlying rational approximation problems. In particular, we present different classes of optimal parameters and collect formulas for the associated convergence rates. Often the parameters leading to best convergence rates are not optimal in terms of computation time required by the resulting rational Krylov method. We explain this observation and present new approaches for computing parameters that are preferable for computations. We give a heuristic explanation of superlinear convergence effects observed with the Rayleigh–Ritz method, utilizing a new theory of the convergence of rational Ritz values. All theoretical results are tested and illustrated by numerical examples. Numerous links to the historical and recent literature are included.

A precisão e acurácia dos métodos mais utilizados atualmente de processamento de dados de espectroscopia por Ressonância Magnética (MRS), baseados na Transformada de Fourier (FT), requerem supressão apropriada (o que está longe de ser trivial) e aquisições longas para a obtenção de alta resolução espectral. Além disso, a FT tem dificuldades quando faltam dados no domínio de tempo, como, por exemplo, pela redução do tempo de aquisição, e consequente número de pontos adquiridos. Isto pode ocorrer, também, por artefatos na aquisição ou, ainda, seja pela exclusão intencional dos primeiros pontos do sinal para a eliminação de ressonâncias largas que estão distorcendo a linha de base no domínio da frequência. Neste estudo, propomos a utilização do Método de Diagonalização na Base de Krylov (KBDM) como uma alternativa a FT para algumas de suas limitações. O método ajusta sinais de experimentos de Free Induction Decay (FID) por uma soma de funções harmônicas complexas, amortecidas exponencialmente, permitindo uma fácil manipulação dos seus parâmetros de caracterização. O KBDM é numericamente mais efetivo para análise de sinais truncados e tem diversos recursos que possibilitam remover picos de forma mais eficiente, como por exemplo, o pico residual da água. Além disso, foi introduzida a possibilidade de quantificação de dados de MRS com o método. Para avaliar a sensibilidade, eficiência e reprodutibilidade do método para quantificar e analisar sinais truncados, foi proposto fazer simulações de espectros clínicos e experimentos em phantoms que representassem o ambiente metabólico do cérebro, para MRS de próton de diferentes níveis de ruídos e para pequenas variações do N-acetil aspartato (NAA). Com estes estudos pôde se comprovar a viabilidade do método para processar dados de MRS e verificar seu potencial na complementação das técnicas atualmente empregadas, especialmente quando uma resolução espectral e temporal maior que o limite imposto pela Relação de Incerteza do formalismo de Fourier é necessária. Além disso, uma desejável facilidade de manipulação de picos específicos (por exemplo, exclusão e quantificação) é proporcionada pelo método. Como perspectivas animadoras deste trabalho esperamos a introdução do KBDM como uma técnica eficiente e coadjuvante ao Imageamento de Ressonância Magnética funcional (fMRI), auxiliando estudos de funções cerebrais, em sequências de MRS para identificar uma rápida variação das linhas associadas as atividades metabólicas dos cérebros. / The precision and accuracy of the most widely used methods to perform Magnetic Resonance Spectroscopy (MRS) data processing based on the Fourier Transform (FT), require appropriate suppression (which is far from trivial) and long acquisitions to obtain high spectral resolution. Furthermore, FT poses difficulty when there are missing data in the time domain. This occurs because of reduction of the acquisition time and consequently also in the number of acquired points, or because of artifacts during acquisition, or even intentional exclusion of the first signal points for the elimination of broad resonances that are producing the distorted baseline in the frequency domain. In this study, we propose the use of the Krylov Basis Diagonalization Method (KBDM) formalism as an alternative to some of FT limitations. The method adjusts signals of Free Induction Decay (FID) experiments with a sum of complex harmonic functions, exponentially damped, allowing easy manipulation of its characterization parameters. The KBDM is numerically more effective for truncated signal analysis and has several features that make it possible to remove peaks more efficiently, such as the residual water peak. Moreover, we introduced the possibility of quantification of MRS data with the described method. To evaluate the sensitivity, efficiency and reproducibility of the method for quantifying and analyzing truncated signals, and through the clinical spectra simulations and experiments in phantoms that would represent the brain metabolic environment, we proposed to perform proton MRS at different noise levels and with small variations of N- acetyl aspartate (NAA) metabolite. These studies allowed to prove the feasibility of the method to process MRS data and verified its potential in complementing techniques currently employed, especially when a greater temporal and spectral resolution is required, more than the limit imposed by the Uncertainty Relation of FT formalism. Furthermore, it is also a desirable effortless tool of handling specific peaks (e.g., exclusion and quantification). Exciting prospects from this work include the introduction of KBDM as an efficient and adjuvant technique to functional Magnetic Resonance Imaging (fMRI), for studying the brain functions, in MRS sequence to identify rapid variation in spectroscopic lines associated to metabolic activities in the brain.

[ES] El objetivo de esta tesis es el desarrollo de algoritmos e implementaciones innovadoras de altas prestaciones (HPC) para la computación de funciones de matrices basadas en series de polinomios matriciales. En concreto, se desarrollarán algoritmos para el cálculo de las funciones matriciales más utilizadas: la exponencial, el seno y el coseno. El estudio de los polinomios ortogonales matriciales es un campo emergente cuyo avance está alcanzando importantes resultados tanto desde el punto de vista teórico como práctico. Las ¿últimas investigaciones realizadas por el doctorando, junto a los miembros del grupo de investigación al que está vinculado, High Performance Scientific Computing (HiPerSC), revelan por qué los polinomios matriciales desempeñan un papel fundamental en la aproximación de funciones de matrices, proporcionando propiedades muy interesantes. En esta tesis se han desarrollado nuevos algoritmos de alto rendimiento basados en series polinomiales matriciales. En particular, se han implementado algoritmos para el cálculo de la exponencial, el seno y el coseno de una matriz usando las series matriciales polinomiales de Taylor y de Hermite. Además, se han proporcionado cotas del error cometido en las aproximaciones calculadas, proporcionando además los parámetros teóricos y experimentales óptimos de dichas aproximaciones. Los algoritmos finales han sido comparados con otras implementaciones del estado del arte para probar la mejora que presentan en cuanto a eficiencia y prestaciones. Los resultados obtenidos a lo largo de la investigación y presentados en esta memoria han sido publicados en varias revistas de alto nivel y se han presentado como ponencias en diversas ediciones del congreso internacional Mathematical Modelling in Engineering & Human Behaviour para dotarlas de la mayor difusión posible. Por otra parte, los códigos informáticos implementados han sido puestos a disposición de la comunidad científica internacional a través de nuestra página web http://hipersc.blogs.upv.es. / [CAT] L'objectiu d'aquesta Tesi és el desenvolupament d'algoritmes i implementacions innovadores d'altes prestacions (HPC) per a la computació de funcions de matrius basades en sèries de polinomis matricials. En concret, es desenvoluparan algoritmes per al càlcul de les funcions matricials més emprades: l'exponencial, el sinus i el cosinus. L'estudi dels polinomis ortogonals matricials és un camp emergent, el creixement del qual està aconseguint importants resultats tant des del punt de vista teòric com pràctic. Les últimes investigacions realitzades pel doctorand junt amb els membres del grup d'investigació on està vinculat, High Performance Scientific Computing (HiPerSC), revelen per què els polinomis matricials exerceixen un paper fonamental en l'aproximació de funcions de matrius, proporcionant propietats molt interessants. En aquesta Tesi s'han desenvolupat nous algoritmes d'alt rendiment basats en sèries polinomials matricials. En particular, s'han implementat algoritmes per al càlcul de l'exponencial, el sinus i el cosinus d'una matriu usant les sèries matricials polinomials de Taylor i d'Hermite. A més, s'han proporcionat cotes de l'error comès en les aproximacions calculades, proporcionant a més els paràmetres teòrics i experimentals òptims d'aquestes aproximacions. Els algoritmes finals han estat comparats amb altres implementacions de l'estat de l'art per a provar la millora que presenten en termes d'eficiència i prestacions. Els resultats obtinguts al llarg de la investigació i presentats en aquesta memòria han estat publicats en diverses revistes d'alt nivell i s'han presentat com a ponències en diferents edicions del congrés internacional Mathematical Modelling in Engineering \& Human Behaviour per a dotar-les de la major difusió possible. D'altra banda, s'han posat els codis informàtics implementats a disposició de la Comunitat Científica Internacional mitjançant la nostra pàgina web http://hipersc.blogs.upv.es. / [EN] The aim of this thesis is the development of high performance computing (HPC) innovative algorithms and implementations for computing matrix functions based on matrix polynomials series. Specifically, algorithms for the calculation of the most commonly-used functions, the exponential, sine and cosine have been developed. The study of orthogonal matrix polynomials is an emerging field whose growth is achieving important results both theoretically and practically. The last investigations made by the doctoral student, together with the members of the research group, High Performance Scientific Computing (HiPerSC), he is linked, reveal why the matrix polynomials play a fundamental role in the approximation of matrix functions, providing very interesting properties.In this thesis new high-performance algorithms based on matrix polynomial series have been developed. In particular, algorithms for computing the exponential, sine and cosine of a matrix using Taylor and Hermite matrix polynomial series have been implemented.In addition, the error bounds for the approximations calculated have been provided and optimal theoretical and experimental parameters for such approximations have also been provided. Final algorithms have been compared to other state of the art implementations to test the improvement obtained in terms of efficiency and performance. The results obtained during the investigation and presented in this memory have been published in several high-level journals and presented as papers at various editions of the International Congress Mathematical Modelling in Engineering & Human Behaviour to give them the widest possible distribution. On the other hand, implemented computer codes have been made freely available to the international scientific community at our web page http://hipersc.blogs.upv.es. / Ruiz Martínez, PA. (2020). Nuevos métodos y algoritmos de altas prestaciones para el cálculo de funciones de matrices [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/137035 / TESIS

No description available.

This dissertation concerns the model reduction of linear periodic descriptor systems both in continuous and discrete-time case. In this dissertation, mainly the projection based approaches are considered for model order reduction of linear periodic time varying descriptor systems. Krylov based projection method is used for large continuous-time periodic descriptor systems and balancing based projection technique is applied to large sparse discrete-time periodic descriptor systems to generate the reduce systems. For very large dimensional state space systems, both the techniques produce large dimensional solutions. Hence, a recycling technique is used in Krylov based projection methods which helps to compute low rank solutions of the state space systems and also accelerate the computational convergence. The outline of the proposed model order reduction procedure is given with more details. The accuracy and suitability of the proposed method is demonstrated through different examples of different orders. Model reduction techniques based on balance truncation require to solve matrix equations. For periodic time-varying descriptor systems, these matrix equations are projected generalized periodic Lyapunov equations and the solutions are also time-varying. The cyclic lifted representation of the periodic time-varying descriptor systems is considered in this dissertation and the resulting lifted projected Lyapunov equations are solved to achieve the periodic reachability and observability Gramians of the original periodic systems. The main advantage of this solution technique is that the cyclic structures of projected Lyapunov equations can handle the time-varying dimensions as well as the singularity of the period matrix pairs very easily. One can also exploit the theory of time-invariant systems for the control of periodic ones, provided that the results achieved can be easily re-interpreted in the periodic framework. Since the dimension of cyclic lifted system becomes very high for large dimensional periodic systems, one needs to solve the very large scale periodic Lyapunov equations which also generate very large dimensional solutions. Hence iterative techniques, which are the generalization and modification of alternating directions implicit (ADI) method and generalized Smith method, are implemented to obtain low rank Cholesky factors of the solutions of the periodic Lyapunov equations. Also the application of the solvers in balancing-based model reduction of discrete-time periodic descriptor systems is discussed. Numerical results are given to illustrate the effciency and accuracy of the proposed methods.

We present a unified and self-contained treatment of rational Krylov methods for approximating the product of a function of a linear operator with a vector. With the help of general rational Krylov decompositions we reveal the connections between seemingly different approximation methods, such as the Rayleigh–Ritz or shift-and-invert method, and derive new methods, for example a restarted rational Krylov method and a related method based on rational interpolation in prescribed nodes. Various theorems known for polynomial Krylov spaces are generalized to the rational Krylov case. Computational issues, such as the computation of so-called matrix Rayleigh quotients or parallel variants of rational Arnoldi algorithms, are discussed. We also present novel estimates for the error arising from inexact linear system solves and the approximation error of the Rayleigh–Ritz method. Rational Krylov methods involve several parameters and we discuss their optimal choice by considering the underlying rational approximation problems. In particular, we present different classes of optimal parameters and collect formulas for the associated convergence rates. Often the parameters leading to best convergence rates are not optimal in terms of computation time required by the resulting rational Krylov method. We explain this observation and present new approaches for computing parameters that are preferable for computations. We give a heuristic explanation of superlinear convergence effects observed with the Rayleigh–Ritz method, utilizing a new theory of the convergence of rational Ritz values. All theoretical results are tested and illustrated by numerical examples. Numerous links to the historical and recent literature are included.

No description available.